Turing Machines

"People think - most people think - that in mathematics we always know what is right and what is wrong. Not so. Not anymore." - Alan Turing.

Introduction

In the mid 1930's, Alan Turing, one of the significant figures at Bletchley Park, wanted to continue the work of Kurt Gödel’s computational decidability. Although, Turing did not directly answer Gödel's question regarding exact decidability, Turing came up with a computational model called a Turing machine (abbreviated TM). The TM resulted in a working definition of what can and cannot be computable as per the Church-Turing thesis. In fact, Turing was able to formally describe Church's recursive functions, in terms of machines. TM's have virtually unrestricted and unlimited amount of memory, unlike other computation models such as a finite automata or pushdown-stack automata. Furthermore, no other computation model shows greater capability than the TM.

Composition & Function.

There are essentially two parts to a TM:

(1) A control unit that consists of a table of transition functions δ, or a statechart diagram representing the transitions. The control unit operates a read/write head on (2) one or more tapes consisting of blank cells or squares which may contain a finite sequence of non-blank cells and can be infinitely long in either direction.

The read/write head, sometimes called a position marker, moves back and forth on the tape depending on the instructions of the TM. The TM can store information on one or more tapes, as well and the number of states of a TM are finite. It's not difficult to see the similarities between the components of a TM and a modern day digital computer. The TM tape(s) can be equivalent to computer memory and the control unit, consisting of the TM's instructions, are like computer programs. On a more historical note, the sequential access to memory is what most impressed Turing about computation. There are three outcomes of a TM computation at a given input: (1) Accepts and halts, (2) Rejects and halts or (3) computes indefinitely. A TM that is "computable" is one that halts.

Preliminary Definitions.

The following are some important definitions for understanding the computation of a TM:

Alphabet - A finite set of symbols for instance ∑ = {a, b} and ∑* is the set of all finite strings from ∑, including the empty string ε.

Language - A language L over ∑ is a subset of ∑*.

Decision Problem - A decision problem is a problem where all the answers are YES or NO, hence the criteria for decidability.

Decider - A decider TM halts on every input string for a given language L, resulting in either acceptance or rejection.

Language Acceptance - The TM halts in an accepting state.

Language Recognition

- The TM halts in an accepting state for elements of the language L - or -
- Halts in a rejecting state for all other elements not in L - or -
- The TM loops indefinitely

Unrecognizable Language

- A language L that is not decidable is not recognizable or its complement is not recognizable.

Formal Definition.

The transition function δ describes the dynamics of a TM. A δ function has the following form:

δ(q, n) = (r, m, R)

such that the TM is in state q and the read/write head is at a tape square containing the symbol n. The TM overwrites the symbol n by writing the symbol m and then traverses to state r. The R signifies moving the read/write head to the right where as an L would be to the left. A Turing Machine is formally defined as: a 5-tuple (Q, Σ, Γ, δ, q₀) such that:

Q = a nonempty finite set of states.
Σ = finite set input alphabet not containing the blank symbol B.
Γ = finite set tape alphabet, which includes B, and Σ Í Γ.
δ = transition function Q x Γ → Q x Γ x {L, R}.
q₀ = initial state where q₀ Î Q.

Computational Paradigms.

1. Language acceptance (recognition): TM halts in an accepting state or outputs a 1 on the tape, on an input within the specified language.
2. Functional computation: TM computes a number theoretic function, given some input and the resulting output on the tape.
3. Transduction: TM changes the input string to another string, such as in a palindrome.

Example.

B:1

B:1,R

The following TM computes a number-theoretic function f(n) = n + 2. We use unary notation for representing positive integers. For instance, 1 is 0, 11 is 1, 111 is 2, 1111 is 3, and so forth and so on:

Figure 1, Basic TM that computes f(n) = n + 2.

The above TM can also be represented by the following set of transition δ functions:

δ(q₀, 1) = (q₀, 1, R)
δ(q₀, B) = (q₁, 1, R)
δ(q₁, B) = (q₂, 1)

Figure 2, The tape configurations at the end of each state.

Variant Turing Machines.

There are many forms of Turing machines, such as a multi-tape TM, a TM that accept by terminal state, multiple read/write heads and even nondeterministic TM's. Restriction on the tape to be one-way infinite for instance, is yet another variation of a TM. Regardless of the type of TM, the capability of any kind of TM never increases nor decreases. In other words, they are all computationally equivalent. A nondeterministic TM allows for alternative parallel paths of execution. Either a choice of two or more instructions given the same initial condition is chosen or the NTM runs all possibilities in parallel. A deterministic TM is a special case of a nondeterministic TM. In fact, any NTM has an equivalent DTM. Lastly, any multi-tape TM has an equivalent single-tape TM. The following are some general types of Turing machines:

Oracle TM - This is a kind of TM that consists of an extra tape and three additional states q_?, q_y, q_n. Upon entering state q_? an oracle is consulted to produce an answer in a single step to a given input on the tape. If the input is in the oracle set then control goes to state q_y, otherwise it goes to q_n.

Alternating TM - A nondeterministic TM, which consists of universal states. The idea is that if all possible transitions from a universal state leads to an acceptance then the TM accepts.

Probabilistic TM - This type of TM consists of randomly chosen transitions.

Universal TM - A UTM has the ability to simulate another TM by using its encoding.

Links.

http://www.hypercomputation.net/
http://www.alanturing.net/
http://www.turing.org.uk/turing/scrapbook/tmjava.html
http://waste.informatik.hu-berlin.de/WW2/turing_e.html
http://www.ics.uci.edu/~savoiu/dem/