11-14-2008 Sören Wellhöfer
Turing Machine
Structure and Operational Functionality
1. History 4. Varieties
2. Structure and Definition 5. Computability
3. Samples 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.
Infinite one-dimensional tape of cells (containing b) M=〈 S, Γ , b , Σ , δ , s0 , F 〉
Read/Write Head, initially in state s0 over single cell S .. . set of states s 0 ∈S .. . initial state
Head reads current cell symbol, acts according to δ
Instruction (5-tuple): when in state si reading symbol aj ; Γ . .. set of symbols b∈Γ . . . blank symbol
write new symbol aj1 ; move into direction dk k ∈{L,R } and F⊆Q . . . set of final states
change head's state to si1 Σ⊆ ∖{ b } . . . input symbols
TM has unlimited storage and time to finish computation
δ : S ×Γ × { L, R } is the transition function
b b b a j1 a0 a2 b b Quintuple instruction of δ: s i a j si1 a j1 d k
si
3. Samples
I. Unary number addition machine: II. Complement machine:
S= { 0,1,HALT } ; s =0; Γ= { B,X,+ } ; b= B; F= { HALT } ; Σ= { X,+ } S= { 0,HALT } ; s =0; Γ= { B, 0,1 } ; b= B; F= { HALT } ; Σ= { 0,1 }
0 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; non-
deterministic 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
[Link] Turing Machines: Examples, Jaime Soffer, 2005
[Link] 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
[Link] Turing Machine, Busy Beaver, Computability, Turing-completeness, Entscheidungsproblem 11-03-2008