L6 - Self-interpreter for WHILE Flashcards
1
Q
What is a Universal WHILE program?
A
A WHILE program that can take another WHILE program tree as input
2
Q
How is the UWP similar to the UTM?
A
Both take programs of same language as input.
3
Q
What is the goal of having a self-interpreter in WHILE?
A
To solve the halting problem by determining if the program halts on an input.
4
Q
Define the Halting Problem…
A
Is there an algorithm that can determine whether another program if given some input will terminate in finite time.
5
Q
What are the rules for encoding WHILE programs as syntax tree lists?
A
…
6
Q
List all the atoms in the extended WHILE language as well as their list notation?
A
:=
nil
while
quote
cons
hd
tl
var
