Turing Machine Synopsis

11-14-2008

Sören Wellhöfer Turing Machine Structure and Operational Functionality

1. History 2. Structure and Definition 3. Samples

4. Varieties 5. Computability 6. References

1. History

Time frame:  

Reduction of all math to fundamental logic Arithmetic computations by means of automatic formal system

Turing's achievements presented in his 1936 paper:

  →

Proof of the possibility of a symbol-processing machine operating on formal system All computations according to rules logically feasible (Turing-computability) Fundamental for computer science as Turing Machines provide theoretical grounding for any modern algorithm

2. Structure and Definition Def.: A Turing machine is a class of finite state machines, meaning that at any time it is in any one of a finite number of states. Operational

instructions consist of conditions under which the machine transitions between states until a final configuration is reached, that is, the computation is finished.

   



M=〈 S, Γ , b , Σ , δ , s0 , F 〉

Infinite one-dimensional tape of cells (containing b) Read/Write Head, initially in state s0 over single cell Head reads current cell symbol, acts according to δ Instruction (5-tuple): when in state si reading symbol aj ; write new symbol aj1 ; move into direction dk k ∈{L,R } and change head's state to si1 TM has unlimited storage and time to finish computation

b

b

b

a j1

a0

a2

b

S .. . set of states

s 0 ∈S .. . initial state

Γ . .. set of symbols b∈Γ . . . blank symbol F⊆Q . . . set of final states Σ⊆  ∖{ b } . . . input symbols

δ : S ×Γ × { L, R } is the transition function Quintuple instruction of δ: s i a j  si1 a j1 d k

b

si

3. Samples I. Unary number addition machine:

II. Complement machine:

S= { 0,1,HALT } ; s =0; Γ= { B,X,+ } ; b= B; F= { HALT } ; Σ= { X,+ } 0

S= { 0,HALT } ; s =0; Γ= { B, 0,1 } ; b= B; F= { HALT } ; Σ= { 0,1 } 0

δ

s i =0

s i =1

δ

s i =0

a j= X

s i1=0; a j1=X; d k =R

s i1=HALT; a j1=B; d k =R

a j =0

s i1=0; a j1=1; d k =R

a j =

s i1=0; a j1=X; d k =R

-

a j =1

s i1=0; a j1=0; d k =R

a j=B

s i1=1; a j1=B; d k =L

-

a j= B

s i1=HALT; a j1=B; d k =R

4. Varieties  Provably equivalent variations: arbitrary/no head movement; multiple heads; two-way infinite tape; two-dimensional tape; nondeterministic Turing-Machines; etc.  4-tuple representation as a state digram (see figure): a s  s d d... action: either write a symbol or move right/left i i1





Universal Turing Machine (UTM):  Action table δ of other Turing Machines can be encoded on tape  UTM can simulate other TMs: similar to von Neumann architecture  A machine is said to be Turing-complete when able to act as UTM Instantaneous description of a computation by three facts: current state, symbols on tape, cell where head is over State diagram: Get successor of unary number represented by 1s

5. Computability  Any number is Turing-computable if there exists a TM being able to compute an arbitrarily precise approximation  Algebraic functions are Turing-computable if there exists a TM being able to to compute them  Decision/Halting problem: No general way to determine whether any arbitrary algorithm A with a specific input I will halt eventually → h(A, I) said to be be incomputable  “Busy beaver” function Σ(n), defined as maximum number computable by an n-state TM, is incomputable 6. References http://www.intelligentedu.com/turing_machines_examples.html, Turing Machines: Examples, Jaime Soffer, 2005 http://plato.stanford.edu/entries/turing-machine, Turing Machines, Stanford Encyclopedia of Philosophy, D. Barker-Plummer, 2004 The Universal Turing Machine: A Half-Century Survey, R. Herken, New York: Oxford University Press, 1988 http://en.wikipedia.org/wiki, Turing Machine, Busy Beaver, Computability, Turing-completeness, Entscheidungsproblem 11-03-2008