A basic Turing machine is a model for studying computation. Turing machines can solve decision problems and compute results based on inputs. When studying computation we usually restrict our attention to integers. Since a real number has infinitely many fraction digits we can not compute a real number in a finite time. Rational numbers a approximations to real numbers are equivalent and can be put in one-to-one correspondence with the integers.
Programming a Turing machine is tedious and thus much work at higher levels of abstraction make the reasonable assumption that any completely defined algorithm or computer program could be implemented by a Turing machine.
There are a lot of possible Turing machines, TM, and a useful technique
is to code Turing machines as binary integers.
Universal Turing Machine, UTM, takes an encoded Turing machine on its input tape followed by normal Turing machine input data on that same input tape. The Universal Turing Machine first reads the description of the Turing machine on the input tape and uses this description to simulate the Turing machines actions on the following input data. Of course a UTM is a TM and can thus be encoded as a binary integer, so a UTM can read a UTM from the input tape, read a TM from the input tape, then read the input data from the input tape and proceed to simulate the UTM that is simulating the TM. Etc. Etc.
I suggest taking a look at Recursion Theory, for example the book by Hartley Rogers. Recursive Functions are on integers and they are equivalent to Turing Machines. Of course, you can also use TMs directly, by putting the input on the tape and for example by equipping them with a separate output tape. When the machine stops in a final state, the output tape represents the function value. Here deterministic TMs should be used, otherwise there might be several outputs for a given input.
A basic Turing machine is a model for studying computation. Turing machines can solve decision problems and compute results based on inputs. When studying computation we usually restrict our attention to integers. Since a real number has infinitely many fraction digits we can not compute a real number in a finite time. Rational numbers a approximations to real numbers are equivalent and can be put in one-to-one correspondence with the integers.
Programming a Turing machine is tedious and thus much work at higher levels of abstraction make the reasonable assumption that any completely defined algorithm or computer program could be implemented by a Turing machine.
There are a lot of possible Turing machines, TM, and a useful technique
is to code Turing machines as binary integers.
Universal Turing Machine, UTM, takes an encoded Turing machine on its input tape followed by normal Turing machine input data on that same input tape. The Universal Turing Machine first reads the description of the Turing machine on the input tape and uses this description to simulate the Turing machines actions on the following input data. Of course a UTM is a TM and can thus be encoded as a binary integer, so a UTM can read a UTM from the input tape, read a TM from the input tape, then read the input data from the input tape and proceed to simulate the UTM that is simulating the TM. Etc. Etc.
This is a good question.
The importance of Turing machines is highlighted in
A. Nerode, Musings in Turings Thesis, Cornell University (see page 3):
http://msor.victoria.ac.nz/foswiki/pub/Courses/MATH335_2014T1/WebHome/nerode.pdf
More to the point is
B.A. Burd, The speed of an infinite computation, M.Sc. thesis, The State Univ. of New Jersey, 1984:
http://users.drew.edu/bburd/BarryBurd_infiniteTimeTuringMachines.pdf
- Badges
- Science topic
- Similar topics
- Computer Science and Engineering
- Algorithms