Turing Machine

See plato.stanford.edu for a full description, or On Computable Numbers for the original paper.

One of the Models Of Computation, a Gedanken Experiment of Alan Turing, (i.e. they don't really exist), a Turing Machine 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 Karl Scherer at www.mathematik.uni-heidelberg.de built a Turing Machine 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 Turing Machine which could take input allowing it to simulate any other (i.e. a program - on a 'Universal' Turing Machine). The Church Turing Thesis is essentially that anything we could reasonably call computable can be expressed as input to a universal Turing Machine, and indeed Alonzo Church's Lambda Calculus and Turing's Machines are equivalent in this way.

Didn't somebody else discover the thesis independently of Church and Turing?

According to Roger Penrose in The Emperors New Mind an American-Polish logician called Emil Post 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 Post Machines , other in Godels or Church work, other with Turing Machine. 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 Goedels Incompleteness Theorem

There are some key things about Turing Machines that make them interesting.

There exists a way of representing any Turing Machine (TM) as data for a special purpose Universal Turing Machine. This UTM then acts as an interpreter and simulates the TM perfectly.

There exist simple-to-state requirements that no Turing Machine 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...

Turing Machines and their properties can be encoded as formulae and equations. Hence there are equations that can not be solved by any Turing Machine.

Turing Machines can be encoded in Game Of Life 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:-

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. -- Sean Palmer

Can anyone write a UTM in Python? How about a TM in RDF?

No but here's a TM in XSLT www.unidex.com also Prolog www.donotenter.com and one in Java Script that can be run online www.turing.org.uk 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:mathworld.wolfram.com

(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). -- Karl Knechtel

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 Countably Infinite.

Formally a Turing Machine 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:

A transition can also be written as a list

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:

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 Lambda Calculus) is

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 Turing Machines 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? What Does Halting Mean discusses the possibility of feeding an infinite input program to the Universal Turing Machine. 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 Universal Turing Machine won't halt trying to simulate it. Since the Universal Turing Machine is supposed to be able to handle all cases, then we cannot use infinite non-blank input.

A lot of skepticism here. I guess Real Programmers don't believe in Turing Machines, or at least consider them to be a theoretical Rat Dance. A Turing Tarpit 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 Turing Machine may be an example of how Technology Enables Theory: could Turing have envisaged it if the tickertape had not been invented? Come to that, could Newtonian Mechanics have been envisaged if clockwork had not been invented? - David Wright.

Actually Alan Turing s impetus for envisioning TMs was to investigate Goedels Incompleteness Theorem. 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 (Ticker Tape) 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

See original on c2.com