Church-Turing Thesis

**Turing Machines**

-Formal Definition of a Turing Machine

A Turing machine is a theoretical device that manipulates symbols contained on a strip of tape. Despite its simplicity, a Turing machine can be adapted to simulate the logic of any computer algorithm, and is particularly useful in explaining the functions of a CPU inside of a computer. The "Turing" machine was described by Alan Turing in 1937,[1] who called it an "a(utomatic)-machine". Turing machines are not intended as a practical computing technology, but rather as a thought experiment representing a computing machine. They help computer scientists understand the limits of mechanical computation. Turing gave a succinct definition of the experiment in his 1948 essay, "Intelligent Machinery". Referring to his 1936 publication, Turing wrote that the Turing machine, here called a Logical Computing Machine, consisted of: ...an infinite memory capacity obtained in the form of an infinite tape marked out into squares, on each of which a symbol could be printed. At any moment there is one symbol in the machine; it is called the scanned symbol. The machine can alter the scanned symbol and its behavior is in part determined by that symbol, but the symbols on the tape elsewhere do not affect the behavior of the machine. However, the tape can be moved back and forth through the machine, this being one of the elementary operations of the machine. Any symbol on the tape may therefore eventually have an innings[2]. (Turing 1948, p. 61)
A Turing machine that is able to simulate any other Turing machine is called a Universal Turing machine (UTM, or simply a universal machine). A more mathematically-oriented definition with a similar "universal" nature was introduced by Alonzo Church, whose work on lambda calculus intertwined with Turing's in a formal theory of computation known as the Church–Turing thesis. The thesis states that Turing machines indeed capture the informal notion of effective method in logic and mathematics, and provide a precise definition of an algorithm or 'mechanical procedure'.

Hopcroft and Ullman (1979, p. 148) formally define a (one-tape) Turing machine as a 7-tuple where Q is a finite set of states Γ is a finite set of the tape alphabet/symbols is the blank symbol (the only symbol allowed to occur on the tape infinitely often at any step during the computation) is the set of input symbols is a partial function called the transition function, where L is left shift, R is right shift. (A relatively uncommon variant allows "no shift", say N, as a third element of the latter set.) is the initial state is the set of final or accepting states. Anything that operates according to these specifications is a Turing machine. The 7-tuple for the 3-state busy beaver looks like this (see more about this busy beaver at Turing machine examples):
Q = { A, B, C, HALT }
Γ = { 0, 1 }
b = 0 = "blank"
Σ = { 1 }
δ = see state-table below
q0 = A = initial state
F = the one element set of final states {HALT}

-Examples of Turing machines

Example 1: Complement function

Symbols = {0, 1} and {B}States = {0, 1}End States = {1} 00 01R; When reading a "0" write a "1", move ahead01 00R; When reading a "1" write a "0", move ahead0B 1BS; When reading a blank (end of the string) change state to an End State. That’s all, the head travels through the tape turning each “0″ it finds to “1″ and each “1″ to “0″, Once it reads a blank the state changes to “finalize”.

Example 2: Marbles addition

The model input chain will be “11….111+111….1111″ and the result will have to be the addition of both sides of the “+” symbol. It’s equivalent to having two bowls filled with marbles, and having to determine the total number by placing all of them together. It’s quite simple too. Symbols = {1, +} and {B}States = {0, 1, 2}End States = {2} 01 01R; As long as there are only “1″ move to the right, don’t change anything0+ 01R; Found the sign, set it to “1″ (dirty trick)0B 1BR; Finished travelling the string; let’s erase the last “1″ because it was lent at the sign11 2BS; At state “1″ we know the end was already reached. When we find the first “1″ we delete it and set an End State (we’re done).

Example 3: Identify a pattern

This function is what is known as “decision”; it should set an end state if what was asked resulted true, and a different one if it was false. In this case the function will answer the question, “Does the input string has a pattern formed by a number of a symbol “0″ and exactly the same number of “1″ following it”?; for example, “0011″ returns “yes”, “0100″ returns “no”, “11110000″ returns “no”, etc.

Symbols = {0, 1, x, y, z} and {B}

States = {0, 1, 2, 3, 4, YES, NO}

End States = {YES, NO}

; Initial functions

00 1xR; Replace “0″ by “x” as a mark, move ahead01 NO;

the string begins with a “1″… Can’t match, end right away

; Move functions

10 10R; Found a “0″ right after another, keep travelling right until finding a “1″1y 1yR; Found a “y” after a “0″, it’s an already marked “1″, skip2y 2yL; Same as “1y”, but we’re travelling to the left in state 2 (see “11″)3y 3yR; Same as “1y”40 40L; See “20″, just go on to find the corner and the first “0″.

; Misc.

11 2yL; Found the first “1″ available when going to the right, mark it, turn around2x 3xR; Got an “x” mark when going to the left; turn around (it’s as good as the left side limit of the string)20 40L; Found the first “0″ while traveling to the left. Just go on until finding an “x” mark.4x 0xR; Just like on “00″, but after a few turns.

; End conditions

3B YES; The whole string is marked, get here from natural “10″, “1y” and “3y” conditions.31

NO; We found a “1″ when looking for a “0″, there are more “1″ than “0″ or the string is interleaved.01 NO; The string begins with a “1″, see above in “initial functions”.

How does it work: Find a “0″, mark it “x”; find a “1″, mark it “y”; repeat the process until running out of “0″, in that case, if there’s still a “1″ unmarked, answer “NO”; if we run out of “1″ first, we find that the program is incomplete (tee hee - not my program…); if only marks or a B can be found, answer “YES”.

**Variants of Turing Machine**

-Multitape Turing Machine

In practical analysis, various types of multi-tape Turing machines are often used. Multi-tape machines are similar to single-tape machines, but there is some constant k number of independent tapes. The TABLE has full independent control over all the heads, any of all of which move and print/erase their own tapes (cf Aho-Hopcroft-Ullman 1974 p. 26). Most models have tapes with left ends, right ends unbounded. This model intuitively seems much more powerful than the single-tape model, but any multi-tape machine, no matter how large the k, can be simulated by a single-tape machine using only quadratically more computation time (Papadimitriou 1994, Thrm 2.1). Thus, multi-tape machines cannot calculate any more functions than single-tape machines, and none of the robust complexity classes (such as polynomial time) are affected by a change between single-tape and multi-tape machines.

-Nondeterministic Turing Machine

A non-deterministic Turing machine (NTM), by contrast, may have a set of rules that prescribes more than one action for a given situation. For example, a non-deterministic Turing machine may have both "If you are in state 2 and you see an 'A', change it to a 'B' and move left" and "If you are in state 2 and you see an 'A', change it to a 'C' and move right" in its rule set. An ordinary (deterministic) Turing machine (DTM) has a transition function that, for a given state and symbol under the tape head, specifies three things: the symbol to be written to the tape, the direction (left or right) in which the head should move, and the subsequent state of the finite control. For example, an X on the tape in state 3 might make the DTM write a Y on the tape, move the head one position to the right, and switch to state 5. A non-deterministic Turing machine (NTM) differs in that the state and tape symbol no longer uniquely specify these things; rather, many different actions may apply for the same combination of state and symbol. For example, an X on the tape in state 3 might now allow the NTM to write a Y, move right, and switch to state 5 or to write an X, move left, and stay in state 3.

-Enumerators

Enumerators is a Turing Machine with an output printer. The Turing Machine can use the printer as an output device to print strings.

-Equivalence with Other Models

Many machines that might be thought to have more computational capability than a simple universal Turing machine can be shown to have no more power (Hopcroft and Ullman p. 159, cf Minsky). They might compute faster, perhaps, or use less memory, or their instruction set might be smaller, but they cannot compute more powerfully (i.e. more mathematical functions). (Recall that the Church-Turing thesis hypothesizes this to be true: that anything that can be “computed” can be computed by some Turing machine.)

While none of the following models have been shown to have more power than the single-tape, one-way infinite, multi-symbol Turing-machine model, their authors defined and used them to investigate questions and solve problems more easily than they could have if they had stayed with Turing's a-machine model.