Turing Machine

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.

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.

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:

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

EditText of this page (last edited November 21, 2014) or FindPage with title or text search