L9 - Turing Church Thesis Flashcards
Define the Turing-Church thesis…
Any real world problem can be translated into an equivalent computation via Turing Machine or Lambda Calculus.
Define Turing Completeness…
A set of data manipulation rules that can be used to simulate any Turing Machine
What is a synonym for Turing Completeness?
Universally computational
What is a Machine Program?
A program that has a set of labelled instructions.
How does the Machine Program repeat code blocks?
Instruction jumps.
What are some Machine Program languages?
Turing Machine
Register Machine
WHILE
GOTO
How are instructions labelled?
P(2) : Instruction 2
The execution of instructions of a machine program is a…
Transition between states.
What is the store of Turing Machine?
Tape
What are the tape head positions for Readin and Readout operations on TM?
Readin -> Tape head is positioned to the left of the first input.
Readout -> To the right of the current head.
Give examples of the TM functions:
Right
Left
Write
If-goto-else
How is the Turing Machine semantically represented?
Tuple
(L, alphabet)
L = Instruction function
Why is WHILE more flexible than GOTO?
In GOTO, arguments of hd, tl and cons can only be variables.
In WHILE they can be other expressions.
What data type does GOTO operate on?
Binary trees
