See
http://plato.stanford.edu/entries/turing-machine/ for a full description, or
OnComputableNumbers for the original paper.
One of the
ModelsOfComputation, a
GedankenExperiment of
AlanTuring, (i.e. they don't really exist), a
TuringMachine is an abstract computing device, traditionally a (finite state) machine reading and writing marks on an infinite paper tape.
- Not so fast: Turing machines have been implemented as toys, and KarlScherer? at http://www.mathematik.uni-heidelberg.de/index_en.html built a TuringMachine from wood and metal, using ballBearings to record states on its "tape."
- If it can be built, it probably doesn't have an infinite tape. If it doesn't have an infinite tape, it's not really a Turing machine.
Turing went on to show that you could create a
TuringMachine which could take input allowing it to simulate any other (i.e. a program - on a 'Universal'
TuringMachine). The
ChurchTuringThesis is essentially that anything we could reasonably call computable can be expressed as input to a universal Turing Machine, and indeed
AlonzoChurch's
LambdaCalculus and Turing's Machines are equivalent in this way.
Didn't somebody else discover the thesis independently of Church and Turing?
According to
RogerPenrose in
TheEmperorsNewMind an American-Polish logician called
EmilPost made an important independent contribution, and Stephen Kleene had a key role in helping Church.
I remember studying in a book with a chapter on
PostMachine
?s , other in Godels or Church work, other with
TuringMachine. Can someone name this book?
Real Software Engineers admire Turing machines for the clarity and orthogonality of their instruction set. It's just too bad they're so poor at I/O. Hmm, of what other paradigm does this remind us?
Whaddya mean? They do *LOTS* of I/O! ;->
Actually a kind of Programmable Logic Array plugged into I/O
See also
GoedelsIncompletenessTheorem
There are some key things about
TuringMachines that make them interesting.
- There exists a way of representing any TuringMachine (TM) as data for a special purpose UniversalTuringMachine. This UTM then acts as an interpreter and simulates the TM perfectly.
- There exist simple-to-state requirements that no TuringMachine can meet without error or endlessly looping.
- Computable numbers are defined by there existing a TM that when it is given a description of the desired accuracy it will calculate the number to that accuracy. This allows us to claim that pi is computable (but has infinite digits) for example. On the other hand it indicates that there is an uncountable set of numbers that can not be computed by any algorithm/program/TM (as Turing machines are countable).
- Turing Machines are surprisingly simple, despite their power, and many other systems are equivalent to them. Conclusions about Turing Machines can be applied to those systems. For example...
- TuringMachines and their properties can be encoded as formulae and equations. Hence there are equations that can not be solved by any TuringMachine.
- Turing Machines can be encoded in GameOfLife positions. Hence there are questions about Life which cannot be solved by any Turing Machine (eg whether an arbitrary position will ever "settle down").
Here's a simple Turing Machine in Python:-
def go(t, s, p):
if s == 0 and t[p] == 0:
t[p] = 1
go(t, s, p)
if s == 0 and t[p] == 1:
t[p] = 0
go(t, s, p)
t, s, p = [0], 0, 0
go(t, s, p)
Where "t" is the tape, s is the status, and p is the position. All it does is alternate a number between "0" and "1" continually. --
SeanPalmer
Can anyone write a UTM in Python? How about a TM in RDF?
No but here's a TM in XSLT http://www.unidex.com/turing/utm.htm also Prolog http://www.donotenter.com/resume/pub/tm2.htm and one in JavaScript that can be run online http://www.turing.org.uk/turing/scrapbook/tmjava.html You mean "No-one has written one
yet (and that's probably wrong as well).
What Turing originally invented was a machine consisting of an infinitely long tape divided into cells.
On each cell one of a finite number of symbols can be written.
The head that reads and writes on the tape moves one cell to the left or to the right in each time step. The machine itself is in one of a finite number of states. The state the machine is in determines what the machine should do in each time step via a state transition table.
see:
http://mathworld.wolfram.com/TuringMachine.html
(as Turing machines are countable).
That doesn't sound right to me. My understanding of a Turing machine is that it can be encoded as tape data, and therefore the set of Turing machines maps to the set of all possible tape data, which is uncountable (more than one symbol ^ unbounded length). --
KarlKnechtel
As you say, any Turing machine may be encoded by a string of symbols taken from a finite alphabet. The set of all these strings is countable since you can enumerate all strings: There are only finitely many strings of a given length. Now you first write down all strings of length zero, then those of length one, then those of length two, etc. So the strings are in one-to-one correspondence to the natural numbers and therefore countable. See CountablyInfinite.
Formally a
TuringMachine is a quintuple M = (Q, Sigma, Tau, Epsilon, q0) where:
- Q is a finite set of states, q0 being the starting state
- Tau is a finite set (called the tape alphabet) containing a special symbol called B (blank)
- Sigma is a subset of Tau-{B} called the input alphabet
- Epsilon is a partial function from (Q x Tau) to (Q x Tau x {L, R}). In other words this is the transition table which, given an internal state in Q and the symbol under the reading head, selects a new state, a new symbol to write at the head, and a 'move left' or 'move right' command.
A transition is written as Epsilon(qi,x) = [qj,y,d] where d belongs to {L,R}. It can be drawn as a state diagram with edges looking like:
qi---x/y d--->qj (The edges can loop back to the same node ie when qi=qj).
A transition can also be written as a list
qi x y d qj
Some books write this as two instructions qi x y qi, qi x d qj only allowing one operation per step (either change symbol or move L or R per step).
Epsilon can also be thought of as a set of instructions. Each time through the loop, the machine reads a symbol on the tape and compares the current (state, symbol) pair with the instruction set. If a match is found the machine transitions into a new state specified by the right hand side of the function. If no match is found the machine simply halts. It halts when no match is found. An example computation might that accepts a language (a union)*aa(a union b)* below. TM not specified it would be 5 instructions long but to give an idea of what "running one" looks like:
q0BaabbB
|-Bq1aabbB
|-Baq2abbB
|-Baaq3bbB
Numeric functions can be specified using a base 1 (unary) representation ie to compute f(2,1) start with Bq0111B11B. B separates arguments instead of "," which is not in the machine's alphabet. An example TM for the succ function s(n)=n+1 (compare the one in
LambdaCalculus) is
q0 B B R q1
q1 1 1 R q1
q1 B 1 L qf
qf 1 1 L qf
To run it on s(2) we would start with tape Bq0111B. It would terminate with Bqf1111B = 3 base 1. Non numeric functions can also be specified. A TM T2 can be simulated on a TM T1 also by encodings similar to above.
Let's see if I understand...
The succ function didn't set the element at the right of (q1, B) blank, so I assume that every cell whose value is not specified has the value "blank". If their content was simply "undefined", then some
TuringMachines may not work, although they could probably be rewritten in a way which would work. But in the way the definition stands now, the tape's content is defined not by explicitly writing its content but by a rule: "all cells are blank except for those, which have such and such values".
Could we use another rule, like "every odd cell has such value", which would use an infinite portion of the tape, or is this forbidden?
WhatDoesHaltingMean discusses the possibility of feeding an infinite input program to the
UniversalTuringMachine. However that very same machine works by writing down the "complete configuration" of the machine it emulates, and this configuration includes the content of the tape. There are machines which could halt even given infinite non-blank input, but the
UniversalTuringMachine won't halt trying to simulate it. Since the
UniversalTuringMachine is supposed to be able to handle all cases, then we cannot use infinite non-blank input.
A lot of skepticism here. I guess
RealProgrammers don't believe in
TuringMachines, or at least consider them to be a theoretical
RatDance. A
TuringTarpit if you will.
It's just self-selection bias: a page like this will be of lesser interest to many who consider it an old known topic, but will attract skeptics, so naturally you see skeptical posts.
I was kind of staggered a few years ago, working with some junior programmers with CS degrees, who had never heard of Turing nor Turing machines. Turns out their bachelor's programs, in the country they came from, were primarily general engineering, and included only 3 actual CS courses. The rest of the CS courses were to be taken by Master's candidates. Different system. But it made me realize why such a large percentage of people from that country that I'd previously worked with usually have a Master's degree, whether from back home or from the mid-western U.S.
The
TuringMachine may be an example of how TechnologyEnablesTheory
?: could Turing have envisaged it if the tickertape had not been invented? Come to that, could NewtonianMechanics
? have been envisaged if clockwork had not been invented? -
DavidWright.
Actually AlanTuring s impetus for envisioning TMs was to investigate GoedelsIncompletenessTheorem. No real machine at the time was adequate but he imagined a hypothetical one with infinite tape. Obviously influenced by what was around him at the time (TickerTape?) but also workings of biological cells and other phenomena, he was motivated by something completely abstract. Later on when he worked on decrypting the Enigma codes he was able to create real machines to assist with the calculations, so inventions were the result of his envisionings as much as the other way around. Thereby saving lives although in some cases Churchill had to let bombings take place so as not to divulge the results of Turings real Machines to the enemy