File:2.zip

Alan Turing (as played by Brother Cadfael or the Emperor Claudius) mathematician, logician, cryptanalyst, Street Acts offender, suicide (as played by Snow White).

Devised a conceptual machine to compute all computable functions. Formalized by Church and shown (Church's Theorem) to be equivalent to lambda calculus, recursive arithmetic, abaci, and eventually everything else that has been proposed as computing all computable functions. So it probably does compute all computable functions (Church's Thesis)

The easiest version (equipollent to the fancier versions but messier) is a reader/writer on an indefinitely extendable inscribable tape, marked into segments. It can: move left a segment, move right a segment, change its internal state, print a mark in a segment, print a blank in a segment, stop. It contains a program (for a given function) which tells it what to do in a given situation, i.e., when in a given state, scanning a chracter (mark or blank), it moves or writes and goes into a (usually new) state. Each instruction is a quad <state1, character, action, state2>, with the usual restrictions -- no two quads with the same <state1, character>.

A function is calculable if there is a program of this sort (a set of such quads) such that, when the machine is started on the square immediately to the left of a representation of the argument(s -- representations separated by a single blank if more than one argument) of the function on an otherwise blank tape, it will stop after a finite number of moves on a blank square immediately to the left of a representation of the value of the function for the given argument(s)on an otherwise blank tape. Numbers are represnted in 1+ notation: n by n+1 consecutive marks.

Example: a+b <1,0,R,2>, <2,1,R,2>, <2,0,1,3>, <3,1,L,3>, <3,0,R,4>, <4,1,0,4>, <4,0,R,5> <5,1,0,5>, <5,0,stop,6> (can be optimized, probably)

It is worth noting that an equally powerful but more convinent, and still easy to describe Turing machine is one which can write arbitrary symbols (defined by the state machine attached to it) to the tape, rather than just ones and zeros. (Note: such a machine can't do anything more than the above described, it is just easier to think about.)