Week 3 - Turing-Church Thesis Flashcards
TRUE OR FALSE: There is such thing as a multi-tape Turing machine.
TRUE, there can be more than one tape, each with their one unique tape head.
How does a multi-tape turing machine transition?
It has to read the symbols in each tape at each corresponding tape head, and with those symbols it decides what state to transition to. It then will decide to write a symbol to any number of those tapes at the tape head, and can decide for each tape if their tape head moves left or right.
T(q, a, b, c) = (q1, d, e, f, R, L, L)
Where a is the symbol read from the first tape, b from the 2nd tape and c from the 3rd.
TRUE OR FALSE: Every multi-tape turing machine has an equivalent single-tape turing machine.
TRUE.
TRUE OR FALSE: A Turing machine can be nondeterministic.
TRUE.
TRUE OR FALSE: Every nondeterministic turing machine has an equivalent deterministic turing machine.
TRUE.
What is a prevalent conjecture/metastatement about turing machines that is theorised but not yet proven?
All conceivable extensions of turing machines are equivalent.
What is an algorithm?
A process of finite instructions followed to carry out some task.
What is the Turing-church thesis?
The concept of algorithm defined in λ-calculus (Church) coincides with the concept of algorithm encoded by a Turing machine.
What is Hilbert’s tenth problem?
Devise an algorithm that tests whether a polynomial has an integral root.
Is Hilbert’s tenth problem decidable?
No.
Is Hilbert’s tenth problem solveble?
Yes, by a turing machine.
What are the ways to describe a turing machine?
Formal Description - Full description of all states and transisiton functions. Lowest level of description, and can be very complex.
Implementation Description - Using english to describe the TM and how it works. It describes who the tape is used and how it interacts with it. Does not give details about states or transition functions.
High-level Description - Using english to desribe an algorithm of the TM at the highest level. Does not give details about the machine like the tape, states, tape head or transitions. It describes the steps of the TM.
TRUE OR FALSE: The input to a TM is always a string.
TRUE.
How do we provide a polynomial as input to a TM for Hilbert’s tenth problem?
We encode the polynomial as a string.
