Universal Turing Machine Flashcards
Universal Turing Machine
A Turing machine capable of computing any computable sequence
a UTM has 3 bits of info for the machine M
a basic description of the machine, the contents of the machine tape, the internal state of the machine
How a UTM works
Looks at the input on the tape and the state of the machine then controls it by changing its state based off input
UTM examples
Interpreters llike JVM and Python implementations. Virutal Machines like VMWare or VirtualBox
The power of Turing Machines
A Turing machine can simulate any computer algorithm, no matter how complicated it is
Church Turing thesis
States that a function on natural numbers can be calculated by an effective method if and only if it is computable by a Turing machine
The Halting Problem
Whether the program is going to run forever or not
The undecidability of the halting problem is a statement about Turing
machines, it is not applicable to real computers. TRUE/FALSE
False
The Turing machine is a universal model of computation: with a Turing
machine we can solve any decision problem that can be solved with a Laptop
or PC running Linux\Windows. TRUE/FALSE
True
A problem that cannot be solved by a Turing Machine
Undecidable problem
One machine can do any computational task
Turing machine
Anything computable in this universe can be computed by a Turing machine
Church-Turing thesis
A simple, universal, model of computation
Turing machine
