Turing Machine: Structure And Operational Functionality
This document was uploaded by user and they confirmed that they have the permission to share it. If you are author or own the copyright of this book, please report to us by using this DMCA report form. Report DMCA
Overview
Download & View Turing Machine: Structure And Operational Functionality as PDF for free.
More details
- Words: 4,610
- Pages: 83
Structure and Operational Functionality of
The Turing Machine 11 — 13 — 2008
¨ ren Wellho ¨ fer So
History Structure and Definition Samples Varieties Computability References
Table of Contents 1 History 2 Structure and Definition 3 Samples 4 Varieties 5 Computability 6 References S¨ oren Wellh¨ ofer
Structure and Operational Functionality of The Turing Machine
History Structure and Definition Samples Varieties Computability References
Time frame — The 20th century
What were mathematicians working on? • Rediscover Theory of Numbers • Reduction of all math to fundamental logic
S¨ oren Wellh¨ ofer
Structure and Operational Functionality of The Turing Machine
History Structure and Definition Samples Varieties Computability References
Time frame — The 20th century
What were mathematicians working on? • Rediscover Theory of Numbers • Reduction of all math to fundamental logic • Arithmetics/computations by means of automatic formal
system
S¨ oren Wellh¨ ofer
Structure and Operational Functionality of The Turing Machine
History Structure and Definition Samples Varieties Computability References
Time frame — The 20th century
What were mathematicians working on? • Rediscover Theory of Numbers • Reduction of all math to fundamental logic • Arithmetics/computations by means of automatic formal
system
S¨ oren Wellh¨ ofer
Structure and Operational Functionality of The Turing Machine
History Structure and Definition Samples Varieties Computability References
Time frame — The 20th century
What were mathematicians working on? • Rediscover Theory of Numbers • Reduction of all math to fundamental logic • Arithmetics/computations by means of automatic formal
system
S¨ oren Wellh¨ ofer
Structure and Operational Functionality of The Turing Machine
History Structure and Definition Samples Varieties Computability References
What does it mean to be computable?
Turing’s achievements • Proof of the possibility of a symbol-processing machine • Simple operations according to rules
S¨ oren Wellh¨ ofer
Structure and Operational Functionality of The Turing Machine
History Structure and Definition Samples Varieties Computability References
What does it mean to be computable?
Turing’s achievements • Proof of the possibility of a symbol-processing machine • Simple operations according to rules • Instruction tables for machine’s moves = formal system
S¨ oren Wellh¨ ofer
Structure and Operational Functionality of The Turing Machine
History Structure and Definition Samples Varieties Computability References
What does it mean to be computable?
Turing’s achievements • Proof of the possibility of a symbol-processing machine • Simple operations according to rules • Instruction tables for machine’s moves = formal system • All computations logically feasible!
S¨ oren Wellh¨ ofer
Structure and Operational Functionality of The Turing Machine
History Structure and Definition Samples Varieties Computability References
What does it mean to be computable?
Turing’s achievements • Proof of the possibility of a symbol-processing machine • Simple operations according to rules • Instruction tables for machine’s moves = formal system • All computations logically feasible!
→ wrote first programmes
S¨ oren Wellh¨ ofer
Structure and Operational Functionality of The Turing Machine
History Structure and Definition Samples Varieties Computability References
What does it mean to be computable?
Turing’s achievements • Proof of the possibility of a symbol-processing machine • Simple operations according to rules • Instruction tables for machine’s moves = formal system • All computations logically feasible!
→ wrote first programmes
S¨ oren Wellh¨ ofer
Structure and Operational Functionality of The Turing Machine
History Structure and Definition Samples Varieties Computability References
General Structure Formal definition Action table
Elements of the Turing Machine • Read/Write Head • Infinetly long tape • Divided into cells • Cells containing symbols
S¨ oren Wellh¨ ofer
Structure and Operational Functionality of The Turing Machine
History Structure and Definition Samples Varieties Computability References
General Structure Formal definition Action table
Elements of the Turing Machine • Read/Write Head • Infinetly long tape • Divided into cells • Cells containing symbols • Action table = the program
S¨ oren Wellh¨ ofer
Structure and Operational Functionality of The Turing Machine
History Structure and Definition Samples Varieties Computability References
General Structure Formal definition Action table
Elements of the Turing Machine • Read/Write Head • Infinetly long tape • Divided into cells • Cells containing symbols • Action table = the program
S¨ oren Wellh¨ ofer
Structure and Operational Functionality of The Turing Machine
History Structure and Definition Samples Varieties Computability References
General Structure Formal definition Action table
The Turing Machine
1 0
1 0
1 0
0
0
0
0
1 0
1 0
1 0
Infinetly long ... S¨ oren Wellh¨ ofer
Structure and Operational Functionality of The Turing Machine
History Structure and Definition Samples Varieties Computability References
General Structure Formal definition Action table
The Turing Machine
Tape
1 0
1 0
1 0
0
0
0
0
1 0
1 0
1 0
Infinetly long ... S¨ oren Wellh¨ ofer
Structure and Operational Functionality of The Turing Machine
History Structure and Definition Samples Varieties Computability References
General Structure Formal definition Action table
The Turing Machine
Tape
1 0
1 0
1 0
0
0
0
0
1 0
1 0
1 0
Infinetly long ... S¨ oren Wellh¨ ofer
Structure and Operational Functionality of The Turing Machine
History Structure and Definition Samples Varieties Computability References
General Structure Formal definition Action table
The Turing Machine
Tape
1 0
1 0
1 0
0
0
0
0
1 0
1 0
1 0
Infinetly long ... S¨ oren Wellh¨ ofer
Structure and Operational Functionality of The Turing Machine
History Structure and Definition Samples Varieties Computability References
General Structure Formal definition Action table
The Turing Machine
Tape
1 0
1 0
1 0
0
0
0
0
1 0
1 0
1 0
Infinetly long ... S¨ oren Wellh¨ ofer
Structure and Operational Functionality of The Turing Machine
History Structure and Definition Samples Varieties Computability References
General Structure Formal definition Action table
The Turing Machine Read/Write Head
Tape
1 0
1 0
1 0
0
0
0
0
1 0
1 0
1 0
Infinetly long ... S¨ oren Wellh¨ ofer
Structure and Operational Functionality of The Turing Machine
History Structure and Definition Samples Varieties Computability References
General Structure Formal definition Action table
The Turing Machine Read/Write Head
Tape
1 0
1 0
1 0
0
0
0
0
1 0
1 0
1 0
Infinetly long ... S¨ oren Wellh¨ ofer
Structure and Operational Functionality of The Turing Machine
History Structure and Definition Samples Varieties Computability References
General Structure Formal definition Action table
The Turing Machine Read/Write Head
Tape
A
1 0
1 0
1 0
0
0
0
0
1 0
1 0
1 0
Infinetly long ... S¨ oren Wellh¨ ofer
Structure and Operational Functionality of The Turing Machine
History Structure and Definition Samples Varieties Computability References
General Structure Formal definition Action table
The Turing Machine Read/Write Head
Tape Machine’s State
A
1 0
1 0
1 0
0
0
0
0
1 0
1 0
1 0
Infinetly long ... S¨ oren Wellh¨ ofer
Structure and Operational Functionality of The Turing Machine
History Structure and Definition Samples Varieties Computability References
General Structure Formal definition Action table
The Turing Machine Read/Write Head
Tape Machine’s State
A
1 0
1 0
1 0
0
0
0
0
1 0
1 0
1 0
Infinetly long ... S¨ oren Wellh¨ ofer
Structure and Operational Functionality of The Turing Machine
History Structure and Definition Samples Varieties Computability References
General Structure Formal definition Action table
The Turing Machine Read/Write Head
Now action according to state table
Machine’s State
A
1 0
1 0
1 0
0
0
S¨ oren Wellh¨ ofer
0
0
1 0
1 0
1 0
Structure and Operational Functionality of The Turing Machine
History Structure and Definition Samples Varieties Computability References
General Structure Formal definition Action table
The Turing Machine State table might say: When in state A reading 0: write 1, move right, change state to B.
Read/Write Head
Machine’s State
A
1 0
1 0
1 0
0
0
S¨ oren Wellh¨ ofer
0
0
1 0
1 0
1 0
Structure and Operational Functionality of The Turing Machine
History Structure and Definition Samples Varieties Computability References
General Structure Formal definition Action table
The Turing Machine State table might say: When in state A reading 0: write 1, move right, change state to B.
Read/Write Head
Machine’s State
A
1 0
1 0
1 0
0
1
S¨ oren Wellh¨ ofer
0
0
1 0
1 0
1 0
Structure and Operational Functionality of The Turing Machine
History Structure and Definition Samples Varieties Computability References
General Structure Formal definition Action table
The Turing Machine State table might say: When in state A reading 0: write 1, move right, change state to B.
Read/Write Head
Machine’s State
A
Move right
1 0
1 0
1 0
0
1
S¨ oren Wellh¨ ofer
0
0
1 0
1 0
1 0
Structure and Operational Functionality of The Turing Machine
History Structure and Definition Samples Varieties Computability References
General Structure Formal definition Action table
The Turing Machine State table might say: When in state A reading 0: write 1, move right, change state to B.
A
Move right
1 0
1 0
1 0
0
1
S¨ oren Wellh¨ ofer
0
0
1 0
1 0
1 0
Structure and Operational Functionality of The Turing Machine
History Structure and Definition Samples Varieties Computability References
General Structure Formal definition Action table
The Turing Machine State table might say: When in state A reading 0: write 1, move right, change state to B.
New state B
1 0
1 0
1 0
0
B
1
S¨ oren Wellh¨ ofer
0
0
1 0
1 0
1 0
Structure and Operational Functionality of The Turing Machine
History Structure and Definition Samples Varieties Computability References
General Structure Formal definition Action table
The Turing Machine
Now read again, etc ... ... until final configuration.
B
1 0
1 0
1 0
0
1
S¨ oren Wellh¨ ofer
0
0
1 0
1 0
1 0
Structure and Operational Functionality of The Turing Machine
History Structure and Definition Samples Varieties Computability References
General Structure Formal definition Action table
Formal definition — 7-tupel M = hS, Γ, b, Σ, δ, s0 , F i S
Finite set of states
S¨ oren Wellh¨ ofer
Structure and Operational Functionality of The Turing Machine
History Structure and Definition Samples Varieties Computability References
General Structure Formal definition Action table
Formal definition — 7-tupel M = hS, Γ, b, Σ, δ, s0 , F i S Γ
Finite set of states Finite set of symbols
S¨ oren Wellh¨ ofer
Structure and Operational Functionality of The Turing Machine
History Structure and Definition Samples Varieties Computability References
General Structure Formal definition Action table
Formal definition — 7-tupel M = hS, Γ, b, Σ, δ, s0 , F i S Γ b∈Γ
Finite set of states Finite set of symbols Blank symbol
S¨ oren Wellh¨ ofer
Structure and Operational Functionality of The Turing Machine
History Structure and Definition Samples Varieties Computability References
General Structure Formal definition Action table
Formal definition — 7-tupel M = hS, Γ, b, Σ, δ, s0 , F i S Γ b∈Γ Σ ⊆ Γ \ {b}
Finite set of states Finite set of symbols Blank symbol Input symbols
S¨ oren Wellh¨ ofer
Structure and Operational Functionality of The Turing Machine
History Structure and Definition Samples Varieties Computability References
General Structure Formal definition Action table
Formal definition — 7-tupel M = hS, Γ, b, Σ, δ, s0 , F i S Γ b∈Γ Σ ⊆ Γ \ {b} δ : S × Γ × {L, R}
S¨ oren Wellh¨ ofer
Finite set of states Finite set of symbols Blank symbol Input symbols Finite set of states
Structure and Operational Functionality of The Turing Machine
History Structure and Definition Samples Varieties Computability References
General Structure Formal definition Action table
Formal definition — 7-tupel M = hS, Γ, b, Σ, δ, s0 , F i S Γ b∈Γ Σ ⊆ Γ \ {b} δ : S × Γ × {L, R} s0 ∈ S
S¨ oren Wellh¨ ofer
Finite set of states Finite set of symbols Blank symbol Input symbols Finite set of states Initial state
Structure and Operational Functionality of The Turing Machine
History Structure and Definition Samples Varieties Computability References
General Structure Formal definition Action table
Formal definition — 7-tupel M = hS, Γ, b, Σ, δ, s0 , F i S Γ b∈Γ Σ ⊆ Γ \ {b} δ : S × Γ × {L, R} s0 ∈ S F ⊆S
S¨ oren Wellh¨ ofer
Finite set of states Finite set of symbols Blank symbol Input symbols Finite set of states Initial state Accepting states
Structure and Operational Functionality of The Turing Machine
History Structure and Definition Samples Varieties Computability References
General Structure Formal definition Action table
Formal definition — 7-tupel M = hS, Γ, b, Σ, δ, s0 , F i S Γ b∈Γ Σ ⊆ Γ \ {b} δ : S × Γ × {L, R} s0 ∈ S F ⊆S
S¨ oren Wellh¨ ofer
Finite set of states Finite set of symbols Blank symbol Input symbols Finite set of states Initial state Accepting states
Structure and Operational Functionality of The Turing Machine
History Structure and Definition Samples Varieties Computability References
General Structure Formal definition Action table
Formal definition — 7-tupel M = hS, Γ, b, Σ, δ, s0 , F i S Γ b∈Γ Σ ⊆ Γ \ {b} δ : S × Γ × {L, R} s0 ∈ S F ⊆S
S¨ oren Wellh¨ ofer
Finite set of states Finite set of symbols Blank symbol Input symbols Finite set of states Initial state Accepting states
Structure and Operational Functionality of The Turing Machine
History Structure and Definition Samples Varieties Computability References
General Structure Formal definition Action table
Action table/Transition function δ — Quintupel
si aj −→ si1 aj1 dk When in state si reading symbol aj :
S¨ oren Wellh¨ ofer
Structure and Operational Functionality of The Turing Machine
History Structure and Definition Samples Varieties Computability References
General Structure Formal definition Action table
Action table/Transition function δ — Quintupel
si aj −→ si1 aj1 dk When in state si reading symbol aj : • write symbol aj1
S¨ oren Wellh¨ ofer
Structure and Operational Functionality of The Turing Machine
History Structure and Definition Samples Varieties Computability References
General Structure Formal definition Action table
Action table/Transition function δ — Quintupel
si aj −→ si1 aj1 dk When in state si reading symbol aj : • write symbol aj1 • move into dk , k ∈ {L, R}
S¨ oren Wellh¨ ofer
Structure and Operational Functionality of The Turing Machine
History Structure and Definition Samples Varieties Computability References
General Structure Formal definition Action table
Action table/Transition function δ — Quintupel
si aj −→ si1 aj1 dk When in state si reading symbol aj : • write symbol aj1 • move into dk , k ∈ {L, R} • change state to si1
S¨ oren Wellh¨ ofer
Structure and Operational Functionality of The Turing Machine
History Structure and Definition Samples Varieties Computability References
General Structure Formal definition Action table
Action table/Transition function δ — Quintupel
si aj −→ si1 aj1 dk When in state si reading symbol aj : • write symbol aj1 • move into dk , k ∈ {L, R} • change state to si1
S¨ oren Wellh¨ ofer
Structure and Operational Functionality of The Turing Machine
History Structure and Definition Samples Varieties Computability References
General Structure Formal definition Action table
Action table/Transition function δ — Quintupel
si aj −→ si1 aj1 dk When in state si reading symbol aj : • write symbol aj1 • move into dk , k ∈ {L, R} • change state to si1
S¨ oren Wellh¨ ofer
Structure and Operational Functionality of The Turing Machine
History Structure and Definition Samples Varieties Computability References
Addition Class activity Complement
Unary Numbers
n−→u 1−→X 5−→XXXXX
S¨ oren Wellh¨ ofer
n=m u... number of Xs n... natural number
Structure and Operational Functionality of The Turing Machine
History Structure and Definition Samples Varieties Computability References
Addition Class activity Complement
Unary Number Addition — Self-performed
Simulating a Turing Machine:
Now it’s your turn!
S¨ oren Wellh¨ ofer
Structure and Operational Functionality of The Turing Machine
History Structure and Definition Samples Varieties Computability References
Addition Class activity Complement
Unary Number Addition Machine
S ={0, 1, HALT} F ={HALT}
S¨ oren Wellh¨ ofer
Γ={B, X, +} Σ={X, +}
Structure and Operational Functionality of The Turing Machine
History Structure and Definition Samples Varieties Computability References
Addition Class activity Complement
Unary Number Addition Machine
S ={0, 1, HALT} F ={HALT} s0 =0
S¨ oren Wellh¨ ofer
Γ={B, X, +} Σ={X, +} b=B
Structure and Operational Functionality of The Turing Machine
History Structure and Definition Samples Varieties Computability References
Addition Class activity Complement
Unary Number Addition Machine
S ={0, 1, HALT} F ={HALT} s0 =0 Action table δ
si = 0
S¨ oren Wellh¨ ofer
Γ={B, X, +} Σ={X, +} b=B si = 1
Structure and Operational Functionality of The Turing Machine
History Structure and Definition Samples Varieties Computability References
Addition Class activity Complement
Unary Number Addition Machine
S ={0, 1, HALT} F ={HALT} s0 =0 Action table δ
aj = X
Γ={B, X, +} Σ={X, +} b=B
si = 0 si1 = 0; aj1 = X; dK = R
S¨ oren Wellh¨ ofer
si = 1 si1 = HALT; aj1 = B; dK = R
Structure and Operational Functionality of The Turing Machine
History Structure and Definition Samples Varieties Computability References
Addition Class activity Complement
Unary Number Addition Machine
S ={0, 1, HALT} F ={HALT} s0 =0 Action table δ
aj = X aj = +
Γ={B, X, +} Σ={X, +} b=B
si = 0 si1 = 0; aj1 = X; dK = R si1 = 0; aj1 = X; dK = R
S¨ oren Wellh¨ ofer
si = 1 si1 = HALT; aj1 = B; dK = R —
Structure and Operational Functionality of The Turing Machine
History Structure and Definition Samples Varieties Computability References
Addition Class activity Complement
Unary Number Addition Machine
S ={0, 1, HALT} F ={HALT} s0 =0 Action table δ
aj = X aj = + aj = B
Γ={B, X, +} Σ={X, +} b=B
si = 0 si1 = 0; aj1 = X; dK = R si1 = 0; aj1 = X; dK = R si1 = 1; aj1 = B; dK = L
S¨ oren Wellh¨ ofer
si = 1 si1 = HALT; aj1 = B; dK = R — —
Structure and Operational Functionality of The Turing Machine
History Structure and Definition Samples Varieties Computability References
Addition Class activity Complement
Unary Number Addition Machine
S ={0, 1, HALT} F ={HALT} s0 =0 Action table δ
aj = X aj = + aj = B
Γ={B, X, +} Σ={X, +} b=B
si = 0 si1 = 0; aj1 = X; dK = R si1 = 0; aj1 = X; dK = R si1 = 1; aj1 = B; dK = L
S¨ oren Wellh¨ ofer
si = 1 si1 = HALT; aj1 = B; dK = R — —
Structure and Operational Functionality of The Turing Machine
History Structure and Definition Samples Varieties Computability References
Addition Class activity Complement
A Complement Machine
S ={0, HALT} F ={HALT}
S¨ oren Wellh¨ ofer
Γ={B, 0, 1} Σ={0, 1}
Structure and Operational Functionality of The Turing Machine
History Structure and Definition Samples Varieties Computability References
Addition Class activity Complement
A Complement Machine
S ={0, HALT} F ={HALT} s0 =0
S¨ oren Wellh¨ ofer
Γ={B, 0, 1} Σ={0, 1} b=B
Structure and Operational Functionality of The Turing Machine
History Structure and Definition Samples Varieties Computability References
Addition Class activity Complement
A Complement Machine
S ={0, HALT} F ={HALT} s0 =0 Action table δ
S¨ oren Wellh¨ ofer
Γ={B, 0, 1} Σ={0, 1} b=B si = 0
Structure and Operational Functionality of The Turing Machine
History Structure and Definition Samples Varieties Computability References
Addition Class activity Complement
A Complement Machine
S ={0, HALT} F ={HALT} s0 =0 Action table δ
aj = 0
Γ={B, 0, 1} Σ={0, 1} b=B si = 0 si1 = 0; aj1 = 1; dK = R
S¨ oren Wellh¨ ofer
Structure and Operational Functionality of The Turing Machine
History Structure and Definition Samples Varieties Computability References
Addition Class activity Complement
A Complement Machine
S ={0, HALT} F ={HALT} s0 =0 Action table δ
aj = 0 aj = 1
Γ={B, 0, 1} Σ={0, 1} b=B si = 0 si1 = 0; aj1 = 1; dK = R si1 = 0; aj1 = 0; dK = R
S¨ oren Wellh¨ ofer
Structure and Operational Functionality of The Turing Machine
History Structure and Definition Samples Varieties Computability References
Addition Class activity Complement
A Complement Machine
S ={0, HALT} F ={HALT} s0 =0 Action table δ
aj = 0 aj = 1 aj = B
Γ={B, 0, 1} Σ={0, 1} b=B si = 0 si1 = 0; aj1 = 1; dK = R si1 = 0; aj1 = 0; dK = R si1 = HALT; aj1 = B; dK = R
S¨ oren Wellh¨ ofer
Structure and Operational Functionality of The Turing Machine
History Structure and Definition Samples Varieties Computability References
Addition Class activity Complement
A Complement Machine
S ={0, HALT} F ={HALT} s0 =0 Action table δ
aj = 0 aj = 1 aj = B
Γ={B, 0, 1} Σ={0, 1} b=B si = 0 si1 = 0; aj1 = 1; dK = R si1 = 0; aj1 = 0; dK = R si1 = HALT; aj1 = B; dK = R
S¨ oren Wellh¨ ofer
Structure and Operational Functionality of The Turing Machine
History Structure and Definition Samples Varieties Computability References
Variations 4-tupel State diagrams Instantaneous description Universal Turing Machine
Variations of the TMs ...
... provably equivalent • Two-way infinite tapes • Arbitrary movement of the head • Arbitrary numbers of read-write heads • Arbitrary finite alphabet
S¨ oren Wellh¨ ofer
Structure and Operational Functionality of The Turing Machine
History Structure and Definition Samples Varieties Computability References
Variations 4-tupel State diagrams Instantaneous description Universal Turing Machine
Variations of the TMs ...
... provably equivalent • Two-way infinite tapes • Arbitrary movement of the head • Arbitrary numbers of read-write heads • Arbitrary finite alphabet
S¨ oren Wellh¨ ofer
Structure and Operational Functionality of The Turing Machine
History Structure and Definition Samples Varieties Computability References
Variations 4-tupel State diagrams Instantaneous description Universal Turing Machine
4-tupel representation
asi −→ si1 dk When in state si reading symbol a:
S¨ oren Wellh¨ ofer
Structure and Operational Functionality of The Turing Machine
History Structure and Definition Samples Varieties Computability References
Variations 4-tupel State diagrams Instantaneous description Universal Turing Machine
4-tupel representation
asi −→ si1 dk When in state si reading symbol a: • change state to si1
S¨ oren Wellh¨ ofer
Structure and Operational Functionality of The Turing Machine
History Structure and Definition Samples Varieties Computability References
Variations 4-tupel State diagrams Instantaneous description Universal Turing Machine
4-tupel representation
asi −→ si1 dk When in state si reading symbol a: • change state to si1 • Take action d: move right/left or
write
S¨ oren Wellh¨ ofer
Structure and Operational Functionality of The Turing Machine
History Structure and Definition Samples Varieties Computability References
Variations 4-tupel State diagrams Instantaneous description Universal Turing Machine
4-tupel representation
asi −→ si1 dk When in state si reading symbol a: • change state to si1 • Take action d: move right/left or
write
S¨ oren Wellh¨ ofer
Structure and Operational Functionality of The Turing Machine
History Structure and Definition Samples Varieties Computability References
Variations 4-tupel State diagrams Instantaneous description Universal Turing Machine
State diagram: successor of a unary number
S¨ oren Wellh¨ ofer
Structure and Operational Functionality of The Turing Machine
History Structure and Definition Samples Varieties Computability References
S¨ oren Wellh¨ ofer
Variations 4-tupel State diagrams Instantaneous description Universal Turing Machine
Structure and Operational Functionality of The Turing Machine
History Structure and Definition Samples Varieties Computability References
Variations 4-tupel State diagrams Instantaneous description Universal Turing Machine
Instantaneous description
A Turing Machine in an instantaneous state.
S¨ oren Wellh¨ ofer
Structure and Operational Functionality of The Turing Machine
History Structure and Definition Samples Varieties Computability References
Variations 4-tupel State diagrams Instantaneous description Universal Turing Machine
Universal Turing Machine
Features • Emulates δ of other Turing Machines • Von Neumann architecture
S¨ oren Wellh¨ ofer
Structure and Operational Functionality of The Turing Machine
History Structure and Definition Samples Varieties Computability References
Variations 4-tupel State diagrams Instantaneous description Universal Turing Machine
Universal Turing Machine
Features • Emulates δ of other Turing Machines • Von Neumann architecture • Turing-completeness
S¨ oren Wellh¨ ofer
Structure and Operational Functionality of The Turing Machine
History Structure and Definition Samples Varieties Computability References
Variations 4-tupel State diagrams Instantaneous description Universal Turing Machine
Universal Turing Machine
Features • Emulates δ of other Turing Machines • Von Neumann architecture • Turing-completeness
... 010110101111 00 101011011 00 110110110111 00 11010111011110 ...
S¨ oren Wellh¨ ofer
Structure and Operational Functionality of The Turing Machine
History Structure and Definition Samples Varieties Computability References
Variations 4-tupel State diagrams Instantaneous description Universal Turing Machine
Universal Turing Machine
Features • Emulates δ of other Turing Machines • Von Neumann architecture • Turing-completeness
... 010110101111 00 101011011 00 110110110111 00 11010111011110 ...
S¨ oren Wellh¨ ofer
Structure and Operational Functionality of The Turing Machine
History Structure and Definition Samples Varieties Computability References
Computability
Computable • Any number if
TM-representable √ (π, e, ) • Numerical functions
(+, −, × , ÷)
S¨ oren Wellh¨ ofer
Structure and Operational Functionality of The Turing Machine
History Structure and Definition Samples Varieties Computability References
Computability
Computable
Incomputable
• Any number if
• Entscheidungsproblem: Will
TM-representable √ (π, e, ) • Numerical functions
any algorithm A with arbitrary input I halt? h(A, I ) is incomputable
(+, −, × , ÷)
S¨ oren Wellh¨ ofer
Structure and Operational Functionality of The Turing Machine
History Structure and Definition Samples Varieties Computability References
Computability
Computable
Incomputable
• Any number if
• Entscheidungsproblem: Will
TM-representable √ (π, e, ) • Numerical functions
(+, −, × , ÷)
any algorithm A with arbitrary input I halt? h(A, I ) is incomputable • “Busy beaver” function
Σ(n)
S¨ oren Wellh¨ ofer
Structure and Operational Functionality of The Turing Machine
History Structure and Definition Samples Varieties Computability References
Computability
Computable
Incomputable
• Any number if
• Entscheidungsproblem: Will
TM-representable √ (π, e, ) • Numerical functions
(+, −, × , ÷)
any algorithm A with arbitrary input I halt? h(A, I ) is incomputable • “Busy beaver” function
Σ(n)
S¨ oren Wellh¨ ofer
Structure and Operational Functionality of The Turing Machine
History Structure and Definition Samples Varieties Computability References
Church?Turing thesis “Every effectively calculable function is a computable function.”
• Effectively calculable: produced intuitively • Computable function: computable by a Turing Machine
S¨ oren Wellh¨ ofer
Structure and Operational Functionality of The Turing Machine
History Structure and Definition Samples Varieties Computability References
Church?Turing thesis “Every effectively calculable function is a computable function.”
• Effectively calculable: produced intuitively • Computable function: computable by a Turing Machine
Solvable by humans = Solvable by machines (algorithm) S¨ oren Wellh¨ ofer
Structure and Operational Functionality of The Turing Machine
History Structure and Definition Samples Varieties Computability References
Church?Turing thesis “Every effectively calculable function is a computable function.”
• Effectively calculable: produced intuitively • Computable function: computable by a Turing Machine
Solvable by humans = Solvable by machines (algorithm) S¨ oren Wellh¨ ofer
Structure and Operational Functionality of The Turing Machine
History Structure and Definition Samples Varieties Computability References
The Universal Turing Machine: A Half-Century Survey R. Herken New York: Oxford University Press, 1988. [http://plato.stanford.edu/entries/turing-machine/] Turing Machines Stanford Encyclopedia of Philosophy, 04.11.1995 [http://www.intelligentedu.com/turing machines examples.html] Turing Machines: Examples Jaime Soffer, 2005. [http://en.wikipedia.org/wiki] Turing Machine, Busy Beaver, Computability, Turing-completeness, Entscheidungsproblem, 11-03-2008 S¨ oren Wellh¨ ofer
Structure and Operational Functionality of The Turing Machine
The Turing Machine 11 — 13 — 2008
¨ ren Wellho ¨ fer So
History Structure and Definition Samples Varieties Computability References
Table of Contents 1 History 2 Structure and Definition 3 Samples 4 Varieties 5 Computability 6 References S¨ oren Wellh¨ ofer
Structure and Operational Functionality of The Turing Machine
History Structure and Definition Samples Varieties Computability References
Time frame — The 20th century
What were mathematicians working on? • Rediscover Theory of Numbers • Reduction of all math to fundamental logic
S¨ oren Wellh¨ ofer
Structure and Operational Functionality of The Turing Machine
History Structure and Definition Samples Varieties Computability References
Time frame — The 20th century
What were mathematicians working on? • Rediscover Theory of Numbers • Reduction of all math to fundamental logic • Arithmetics/computations by means of automatic formal
system
S¨ oren Wellh¨ ofer
Structure and Operational Functionality of The Turing Machine
History Structure and Definition Samples Varieties Computability References
Time frame — The 20th century
What were mathematicians working on? • Rediscover Theory of Numbers • Reduction of all math to fundamental logic • Arithmetics/computations by means of automatic formal
system
S¨ oren Wellh¨ ofer
Structure and Operational Functionality of The Turing Machine
History Structure and Definition Samples Varieties Computability References
Time frame — The 20th century
What were mathematicians working on? • Rediscover Theory of Numbers • Reduction of all math to fundamental logic • Arithmetics/computations by means of automatic formal
system
S¨ oren Wellh¨ ofer
Structure and Operational Functionality of The Turing Machine
History Structure and Definition Samples Varieties Computability References
What does it mean to be computable?
Turing’s achievements • Proof of the possibility of a symbol-processing machine • Simple operations according to rules
S¨ oren Wellh¨ ofer
Structure and Operational Functionality of The Turing Machine
History Structure and Definition Samples Varieties Computability References
What does it mean to be computable?
Turing’s achievements • Proof of the possibility of a symbol-processing machine • Simple operations according to rules • Instruction tables for machine’s moves = formal system
S¨ oren Wellh¨ ofer
Structure and Operational Functionality of The Turing Machine
History Structure and Definition Samples Varieties Computability References
What does it mean to be computable?
Turing’s achievements • Proof of the possibility of a symbol-processing machine • Simple operations according to rules • Instruction tables for machine’s moves = formal system • All computations logically feasible!
S¨ oren Wellh¨ ofer
Structure and Operational Functionality of The Turing Machine
History Structure and Definition Samples Varieties Computability References
What does it mean to be computable?
Turing’s achievements • Proof of the possibility of a symbol-processing machine • Simple operations according to rules • Instruction tables for machine’s moves = formal system • All computations logically feasible!
→ wrote first programmes
S¨ oren Wellh¨ ofer
Structure and Operational Functionality of The Turing Machine
History Structure and Definition Samples Varieties Computability References
What does it mean to be computable?
Turing’s achievements • Proof of the possibility of a symbol-processing machine • Simple operations according to rules • Instruction tables for machine’s moves = formal system • All computations logically feasible!
→ wrote first programmes
S¨ oren Wellh¨ ofer
Structure and Operational Functionality of The Turing Machine
History Structure and Definition Samples Varieties Computability References
General Structure Formal definition Action table
Elements of the Turing Machine • Read/Write Head • Infinetly long tape • Divided into cells • Cells containing symbols
S¨ oren Wellh¨ ofer
Structure and Operational Functionality of The Turing Machine
History Structure and Definition Samples Varieties Computability References
General Structure Formal definition Action table
Elements of the Turing Machine • Read/Write Head • Infinetly long tape • Divided into cells • Cells containing symbols • Action table = the program
S¨ oren Wellh¨ ofer
Structure and Operational Functionality of The Turing Machine
History Structure and Definition Samples Varieties Computability References
General Structure Formal definition Action table
Elements of the Turing Machine • Read/Write Head • Infinetly long tape • Divided into cells • Cells containing symbols • Action table = the program
S¨ oren Wellh¨ ofer
Structure and Operational Functionality of The Turing Machine
History Structure and Definition Samples Varieties Computability References
General Structure Formal definition Action table
The Turing Machine
1 0
1 0
1 0
0
0
0
0
1 0
1 0
1 0
Infinetly long ... S¨ oren Wellh¨ ofer
Structure and Operational Functionality of The Turing Machine
History Structure and Definition Samples Varieties Computability References
General Structure Formal definition Action table
The Turing Machine
Tape
1 0
1 0
1 0
0
0
0
0
1 0
1 0
1 0
Infinetly long ... S¨ oren Wellh¨ ofer
Structure and Operational Functionality of The Turing Machine
History Structure and Definition Samples Varieties Computability References
General Structure Formal definition Action table
The Turing Machine
Tape
1 0
1 0
1 0
0
0
0
0
1 0
1 0
1 0
Infinetly long ... S¨ oren Wellh¨ ofer
Structure and Operational Functionality of The Turing Machine
History Structure and Definition Samples Varieties Computability References
General Structure Formal definition Action table
The Turing Machine
Tape
1 0
1 0
1 0
0
0
0
0
1 0
1 0
1 0
Infinetly long ... S¨ oren Wellh¨ ofer
Structure and Operational Functionality of The Turing Machine
History Structure and Definition Samples Varieties Computability References
General Structure Formal definition Action table
The Turing Machine
Tape
1 0
1 0
1 0
0
0
0
0
1 0
1 0
1 0
Infinetly long ... S¨ oren Wellh¨ ofer
Structure and Operational Functionality of The Turing Machine
History Structure and Definition Samples Varieties Computability References
General Structure Formal definition Action table
The Turing Machine Read/Write Head
Tape
1 0
1 0
1 0
0
0
0
0
1 0
1 0
1 0
Infinetly long ... S¨ oren Wellh¨ ofer
Structure and Operational Functionality of The Turing Machine
History Structure and Definition Samples Varieties Computability References
General Structure Formal definition Action table
The Turing Machine Read/Write Head
Tape
1 0
1 0
1 0
0
0
0
0
1 0
1 0
1 0
Infinetly long ... S¨ oren Wellh¨ ofer
Structure and Operational Functionality of The Turing Machine
History Structure and Definition Samples Varieties Computability References
General Structure Formal definition Action table
The Turing Machine Read/Write Head
Tape
A
1 0
1 0
1 0
0
0
0
0
1 0
1 0
1 0
Infinetly long ... S¨ oren Wellh¨ ofer
Structure and Operational Functionality of The Turing Machine
History Structure and Definition Samples Varieties Computability References
General Structure Formal definition Action table
The Turing Machine Read/Write Head
Tape Machine’s State
A
1 0
1 0
1 0
0
0
0
0
1 0
1 0
1 0
Infinetly long ... S¨ oren Wellh¨ ofer
Structure and Operational Functionality of The Turing Machine
History Structure and Definition Samples Varieties Computability References
General Structure Formal definition Action table
The Turing Machine Read/Write Head
Tape Machine’s State
A
1 0
1 0
1 0
0
0
0
0
1 0
1 0
1 0
Infinetly long ... S¨ oren Wellh¨ ofer
Structure and Operational Functionality of The Turing Machine
History Structure and Definition Samples Varieties Computability References
General Structure Formal definition Action table
The Turing Machine Read/Write Head
Now action according to state table
Machine’s State
A
1 0
1 0
1 0
0
0
S¨ oren Wellh¨ ofer
0
0
1 0
1 0
1 0
Structure and Operational Functionality of The Turing Machine
History Structure and Definition Samples Varieties Computability References
General Structure Formal definition Action table
The Turing Machine State table might say: When in state A reading 0: write 1, move right, change state to B.
Read/Write Head
Machine’s State
A
1 0
1 0
1 0
0
0
S¨ oren Wellh¨ ofer
0
0
1 0
1 0
1 0
Structure and Operational Functionality of The Turing Machine
History Structure and Definition Samples Varieties Computability References
General Structure Formal definition Action table
The Turing Machine State table might say: When in state A reading 0: write 1, move right, change state to B.
Read/Write Head
Machine’s State
A
1 0
1 0
1 0
0
1
S¨ oren Wellh¨ ofer
0
0
1 0
1 0
1 0
Structure and Operational Functionality of The Turing Machine
History Structure and Definition Samples Varieties Computability References
General Structure Formal definition Action table
The Turing Machine State table might say: When in state A reading 0: write 1, move right, change state to B.
Read/Write Head
Machine’s State
A
Move right
1 0
1 0
1 0
0
1
S¨ oren Wellh¨ ofer
0
0
1 0
1 0
1 0
Structure and Operational Functionality of The Turing Machine
History Structure and Definition Samples Varieties Computability References
General Structure Formal definition Action table
The Turing Machine State table might say: When in state A reading 0: write 1, move right, change state to B.
A
Move right
1 0
1 0
1 0
0
1
S¨ oren Wellh¨ ofer
0
0
1 0
1 0
1 0
Structure and Operational Functionality of The Turing Machine
History Structure and Definition Samples Varieties Computability References
General Structure Formal definition Action table
The Turing Machine State table might say: When in state A reading 0: write 1, move right, change state to B.
New state B
1 0
1 0
1 0
0
B
1
S¨ oren Wellh¨ ofer
0
0
1 0
1 0
1 0
Structure and Operational Functionality of The Turing Machine
History Structure and Definition Samples Varieties Computability References
General Structure Formal definition Action table
The Turing Machine
Now read again, etc ... ... until final configuration.
B
1 0
1 0
1 0
0
1
S¨ oren Wellh¨ ofer
0
0
1 0
1 0
1 0
Structure and Operational Functionality of The Turing Machine
History Structure and Definition Samples Varieties Computability References
General Structure Formal definition Action table
Formal definition — 7-tupel M = hS, Γ, b, Σ, δ, s0 , F i S
Finite set of states
S¨ oren Wellh¨ ofer
Structure and Operational Functionality of The Turing Machine
History Structure and Definition Samples Varieties Computability References
General Structure Formal definition Action table
Formal definition — 7-tupel M = hS, Γ, b, Σ, δ, s0 , F i S Γ
Finite set of states Finite set of symbols
S¨ oren Wellh¨ ofer
Structure and Operational Functionality of The Turing Machine
History Structure and Definition Samples Varieties Computability References
General Structure Formal definition Action table
Formal definition — 7-tupel M = hS, Γ, b, Σ, δ, s0 , F i S Γ b∈Γ
Finite set of states Finite set of symbols Blank symbol
S¨ oren Wellh¨ ofer
Structure and Operational Functionality of The Turing Machine
History Structure and Definition Samples Varieties Computability References
General Structure Formal definition Action table
Formal definition — 7-tupel M = hS, Γ, b, Σ, δ, s0 , F i S Γ b∈Γ Σ ⊆ Γ \ {b}
Finite set of states Finite set of symbols Blank symbol Input symbols
S¨ oren Wellh¨ ofer
Structure and Operational Functionality of The Turing Machine
History Structure and Definition Samples Varieties Computability References
General Structure Formal definition Action table
Formal definition — 7-tupel M = hS, Γ, b, Σ, δ, s0 , F i S Γ b∈Γ Σ ⊆ Γ \ {b} δ : S × Γ × {L, R}
S¨ oren Wellh¨ ofer
Finite set of states Finite set of symbols Blank symbol Input symbols Finite set of states
Structure and Operational Functionality of The Turing Machine
History Structure and Definition Samples Varieties Computability References
General Structure Formal definition Action table
Formal definition — 7-tupel M = hS, Γ, b, Σ, δ, s0 , F i S Γ b∈Γ Σ ⊆ Γ \ {b} δ : S × Γ × {L, R} s0 ∈ S
S¨ oren Wellh¨ ofer
Finite set of states Finite set of symbols Blank symbol Input symbols Finite set of states Initial state
Structure and Operational Functionality of The Turing Machine
History Structure and Definition Samples Varieties Computability References
General Structure Formal definition Action table
Formal definition — 7-tupel M = hS, Γ, b, Σ, δ, s0 , F i S Γ b∈Γ Σ ⊆ Γ \ {b} δ : S × Γ × {L, R} s0 ∈ S F ⊆S
S¨ oren Wellh¨ ofer
Finite set of states Finite set of symbols Blank symbol Input symbols Finite set of states Initial state Accepting states
Structure and Operational Functionality of The Turing Machine
History Structure and Definition Samples Varieties Computability References
General Structure Formal definition Action table
Formal definition — 7-tupel M = hS, Γ, b, Σ, δ, s0 , F i S Γ b∈Γ Σ ⊆ Γ \ {b} δ : S × Γ × {L, R} s0 ∈ S F ⊆S
S¨ oren Wellh¨ ofer
Finite set of states Finite set of symbols Blank symbol Input symbols Finite set of states Initial state Accepting states
Structure and Operational Functionality of The Turing Machine
History Structure and Definition Samples Varieties Computability References
General Structure Formal definition Action table
Formal definition — 7-tupel M = hS, Γ, b, Σ, δ, s0 , F i S Γ b∈Γ Σ ⊆ Γ \ {b} δ : S × Γ × {L, R} s0 ∈ S F ⊆S
S¨ oren Wellh¨ ofer
Finite set of states Finite set of symbols Blank symbol Input symbols Finite set of states Initial state Accepting states
Structure and Operational Functionality of The Turing Machine
History Structure and Definition Samples Varieties Computability References
General Structure Formal definition Action table
Action table/Transition function δ — Quintupel
si aj −→ si1 aj1 dk When in state si reading symbol aj :
S¨ oren Wellh¨ ofer
Structure and Operational Functionality of The Turing Machine
History Structure and Definition Samples Varieties Computability References
General Structure Formal definition Action table
Action table/Transition function δ — Quintupel
si aj −→ si1 aj1 dk When in state si reading symbol aj : • write symbol aj1
S¨ oren Wellh¨ ofer
Structure and Operational Functionality of The Turing Machine
History Structure and Definition Samples Varieties Computability References
General Structure Formal definition Action table
Action table/Transition function δ — Quintupel
si aj −→ si1 aj1 dk When in state si reading symbol aj : • write symbol aj1 • move into dk , k ∈ {L, R}
S¨ oren Wellh¨ ofer
Structure and Operational Functionality of The Turing Machine
History Structure and Definition Samples Varieties Computability References
General Structure Formal definition Action table
Action table/Transition function δ — Quintupel
si aj −→ si1 aj1 dk When in state si reading symbol aj : • write symbol aj1 • move into dk , k ∈ {L, R} • change state to si1
S¨ oren Wellh¨ ofer
Structure and Operational Functionality of The Turing Machine
History Structure and Definition Samples Varieties Computability References
General Structure Formal definition Action table
Action table/Transition function δ — Quintupel
si aj −→ si1 aj1 dk When in state si reading symbol aj : • write symbol aj1 • move into dk , k ∈ {L, R} • change state to si1
S¨ oren Wellh¨ ofer
Structure and Operational Functionality of The Turing Machine
History Structure and Definition Samples Varieties Computability References
General Structure Formal definition Action table
Action table/Transition function δ — Quintupel
si aj −→ si1 aj1 dk When in state si reading symbol aj : • write symbol aj1 • move into dk , k ∈ {L, R} • change state to si1
S¨ oren Wellh¨ ofer
Structure and Operational Functionality of The Turing Machine
History Structure and Definition Samples Varieties Computability References
Addition Class activity Complement
Unary Numbers
n−→u 1−→X 5−→XXXXX
S¨ oren Wellh¨ ofer
n=m u... number of Xs n... natural number
Structure and Operational Functionality of The Turing Machine
History Structure and Definition Samples Varieties Computability References
Addition Class activity Complement
Unary Number Addition — Self-performed
Simulating a Turing Machine:
Now it’s your turn!
S¨ oren Wellh¨ ofer
Structure and Operational Functionality of The Turing Machine
History Structure and Definition Samples Varieties Computability References
Addition Class activity Complement
Unary Number Addition Machine
S ={0, 1, HALT} F ={HALT}
S¨ oren Wellh¨ ofer
Γ={B, X, +} Σ={X, +}
Structure and Operational Functionality of The Turing Machine
History Structure and Definition Samples Varieties Computability References
Addition Class activity Complement
Unary Number Addition Machine
S ={0, 1, HALT} F ={HALT} s0 =0
S¨ oren Wellh¨ ofer
Γ={B, X, +} Σ={X, +} b=B
Structure and Operational Functionality of The Turing Machine
History Structure and Definition Samples Varieties Computability References
Addition Class activity Complement
Unary Number Addition Machine
S ={0, 1, HALT} F ={HALT} s0 =0 Action table δ
si = 0
S¨ oren Wellh¨ ofer
Γ={B, X, +} Σ={X, +} b=B si = 1
Structure and Operational Functionality of The Turing Machine
History Structure and Definition Samples Varieties Computability References
Addition Class activity Complement
Unary Number Addition Machine
S ={0, 1, HALT} F ={HALT} s0 =0 Action table δ
aj = X
Γ={B, X, +} Σ={X, +} b=B
si = 0 si1 = 0; aj1 = X; dK = R
S¨ oren Wellh¨ ofer
si = 1 si1 = HALT; aj1 = B; dK = R
Structure and Operational Functionality of The Turing Machine
History Structure and Definition Samples Varieties Computability References
Addition Class activity Complement
Unary Number Addition Machine
S ={0, 1, HALT} F ={HALT} s0 =0 Action table δ
aj = X aj = +
Γ={B, X, +} Σ={X, +} b=B
si = 0 si1 = 0; aj1 = X; dK = R si1 = 0; aj1 = X; dK = R
S¨ oren Wellh¨ ofer
si = 1 si1 = HALT; aj1 = B; dK = R —
Structure and Operational Functionality of The Turing Machine
History Structure and Definition Samples Varieties Computability References
Addition Class activity Complement
Unary Number Addition Machine
S ={0, 1, HALT} F ={HALT} s0 =0 Action table δ
aj = X aj = + aj = B
Γ={B, X, +} Σ={X, +} b=B
si = 0 si1 = 0; aj1 = X; dK = R si1 = 0; aj1 = X; dK = R si1 = 1; aj1 = B; dK = L
S¨ oren Wellh¨ ofer
si = 1 si1 = HALT; aj1 = B; dK = R — —
Structure and Operational Functionality of The Turing Machine
History Structure and Definition Samples Varieties Computability References
Addition Class activity Complement
Unary Number Addition Machine
S ={0, 1, HALT} F ={HALT} s0 =0 Action table δ
aj = X aj = + aj = B
Γ={B, X, +} Σ={X, +} b=B
si = 0 si1 = 0; aj1 = X; dK = R si1 = 0; aj1 = X; dK = R si1 = 1; aj1 = B; dK = L
S¨ oren Wellh¨ ofer
si = 1 si1 = HALT; aj1 = B; dK = R — —
Structure and Operational Functionality of The Turing Machine
History Structure and Definition Samples Varieties Computability References
Addition Class activity Complement
A Complement Machine
S ={0, HALT} F ={HALT}
S¨ oren Wellh¨ ofer
Γ={B, 0, 1} Σ={0, 1}
Structure and Operational Functionality of The Turing Machine
History Structure and Definition Samples Varieties Computability References
Addition Class activity Complement
A Complement Machine
S ={0, HALT} F ={HALT} s0 =0
S¨ oren Wellh¨ ofer
Γ={B, 0, 1} Σ={0, 1} b=B
Structure and Operational Functionality of The Turing Machine
History Structure and Definition Samples Varieties Computability References
Addition Class activity Complement
A Complement Machine
S ={0, HALT} F ={HALT} s0 =0 Action table δ
S¨ oren Wellh¨ ofer
Γ={B, 0, 1} Σ={0, 1} b=B si = 0
Structure and Operational Functionality of The Turing Machine
History Structure and Definition Samples Varieties Computability References
Addition Class activity Complement
A Complement Machine
S ={0, HALT} F ={HALT} s0 =0 Action table δ
aj = 0
Γ={B, 0, 1} Σ={0, 1} b=B si = 0 si1 = 0; aj1 = 1; dK = R
S¨ oren Wellh¨ ofer
Structure and Operational Functionality of The Turing Machine
History Structure and Definition Samples Varieties Computability References
Addition Class activity Complement
A Complement Machine
S ={0, HALT} F ={HALT} s0 =0 Action table δ
aj = 0 aj = 1
Γ={B, 0, 1} Σ={0, 1} b=B si = 0 si1 = 0; aj1 = 1; dK = R si1 = 0; aj1 = 0; dK = R
S¨ oren Wellh¨ ofer
Structure and Operational Functionality of The Turing Machine
History Structure and Definition Samples Varieties Computability References
Addition Class activity Complement
A Complement Machine
S ={0, HALT} F ={HALT} s0 =0 Action table δ
aj = 0 aj = 1 aj = B
Γ={B, 0, 1} Σ={0, 1} b=B si = 0 si1 = 0; aj1 = 1; dK = R si1 = 0; aj1 = 0; dK = R si1 = HALT; aj1 = B; dK = R
S¨ oren Wellh¨ ofer
Structure and Operational Functionality of The Turing Machine
History Structure and Definition Samples Varieties Computability References
Addition Class activity Complement
A Complement Machine
S ={0, HALT} F ={HALT} s0 =0 Action table δ
aj = 0 aj = 1 aj = B
Γ={B, 0, 1} Σ={0, 1} b=B si = 0 si1 = 0; aj1 = 1; dK = R si1 = 0; aj1 = 0; dK = R si1 = HALT; aj1 = B; dK = R
S¨ oren Wellh¨ ofer
Structure and Operational Functionality of The Turing Machine
History Structure and Definition Samples Varieties Computability References
Variations 4-tupel State diagrams Instantaneous description Universal Turing Machine
Variations of the TMs ...
... provably equivalent • Two-way infinite tapes • Arbitrary movement of the head • Arbitrary numbers of read-write heads • Arbitrary finite alphabet
S¨ oren Wellh¨ ofer
Structure and Operational Functionality of The Turing Machine
History Structure and Definition Samples Varieties Computability References
Variations 4-tupel State diagrams Instantaneous description Universal Turing Machine
Variations of the TMs ...
... provably equivalent • Two-way infinite tapes • Arbitrary movement of the head • Arbitrary numbers of read-write heads • Arbitrary finite alphabet
S¨ oren Wellh¨ ofer
Structure and Operational Functionality of The Turing Machine
History Structure and Definition Samples Varieties Computability References
Variations 4-tupel State diagrams Instantaneous description Universal Turing Machine
4-tupel representation
asi −→ si1 dk When in state si reading symbol a:
S¨ oren Wellh¨ ofer
Structure and Operational Functionality of The Turing Machine
History Structure and Definition Samples Varieties Computability References
Variations 4-tupel State diagrams Instantaneous description Universal Turing Machine
4-tupel representation
asi −→ si1 dk When in state si reading symbol a: • change state to si1
S¨ oren Wellh¨ ofer
Structure and Operational Functionality of The Turing Machine
History Structure and Definition Samples Varieties Computability References
Variations 4-tupel State diagrams Instantaneous description Universal Turing Machine
4-tupel representation
asi −→ si1 dk When in state si reading symbol a: • change state to si1 • Take action d: move right/left or
write
S¨ oren Wellh¨ ofer
Structure and Operational Functionality of The Turing Machine
History Structure and Definition Samples Varieties Computability References
Variations 4-tupel State diagrams Instantaneous description Universal Turing Machine
4-tupel representation
asi −→ si1 dk When in state si reading symbol a: • change state to si1 • Take action d: move right/left or
write
S¨ oren Wellh¨ ofer
Structure and Operational Functionality of The Turing Machine
History Structure and Definition Samples Varieties Computability References
Variations 4-tupel State diagrams Instantaneous description Universal Turing Machine
State diagram: successor of a unary number
S¨ oren Wellh¨ ofer
Structure and Operational Functionality of The Turing Machine
History Structure and Definition Samples Varieties Computability References
S¨ oren Wellh¨ ofer
Variations 4-tupel State diagrams Instantaneous description Universal Turing Machine
Structure and Operational Functionality of The Turing Machine
History Structure and Definition Samples Varieties Computability References
Variations 4-tupel State diagrams Instantaneous description Universal Turing Machine
Instantaneous description
A Turing Machine in an instantaneous state.
S¨ oren Wellh¨ ofer
Structure and Operational Functionality of The Turing Machine
History Structure and Definition Samples Varieties Computability References
Variations 4-tupel State diagrams Instantaneous description Universal Turing Machine
Universal Turing Machine
Features • Emulates δ of other Turing Machines • Von Neumann architecture
S¨ oren Wellh¨ ofer
Structure and Operational Functionality of The Turing Machine
History Structure and Definition Samples Varieties Computability References
Variations 4-tupel State diagrams Instantaneous description Universal Turing Machine
Universal Turing Machine
Features • Emulates δ of other Turing Machines • Von Neumann architecture • Turing-completeness
S¨ oren Wellh¨ ofer
Structure and Operational Functionality of The Turing Machine
History Structure and Definition Samples Varieties Computability References
Variations 4-tupel State diagrams Instantaneous description Universal Turing Machine
Universal Turing Machine
Features • Emulates δ of other Turing Machines • Von Neumann architecture • Turing-completeness
... 010110101111 00 101011011 00 110110110111 00 11010111011110 ...
S¨ oren Wellh¨ ofer
Structure and Operational Functionality of The Turing Machine
History Structure and Definition Samples Varieties Computability References
Variations 4-tupel State diagrams Instantaneous description Universal Turing Machine
Universal Turing Machine
Features • Emulates δ of other Turing Machines • Von Neumann architecture • Turing-completeness
... 010110101111 00 101011011 00 110110110111 00 11010111011110 ...
S¨ oren Wellh¨ ofer
Structure and Operational Functionality of The Turing Machine
History Structure and Definition Samples Varieties Computability References
Computability
Computable • Any number if
TM-representable √ (π, e, ) • Numerical functions
(+, −, × , ÷)
S¨ oren Wellh¨ ofer
Structure and Operational Functionality of The Turing Machine
History Structure and Definition Samples Varieties Computability References
Computability
Computable
Incomputable
• Any number if
• Entscheidungsproblem: Will
TM-representable √ (π, e, ) • Numerical functions
any algorithm A with arbitrary input I halt? h(A, I ) is incomputable
(+, −, × , ÷)
S¨ oren Wellh¨ ofer
Structure and Operational Functionality of The Turing Machine
History Structure and Definition Samples Varieties Computability References
Computability
Computable
Incomputable
• Any number if
• Entscheidungsproblem: Will
TM-representable √ (π, e, ) • Numerical functions
(+, −, × , ÷)
any algorithm A with arbitrary input I halt? h(A, I ) is incomputable • “Busy beaver” function
Σ(n)
S¨ oren Wellh¨ ofer
Structure and Operational Functionality of The Turing Machine
History Structure and Definition Samples Varieties Computability References
Computability
Computable
Incomputable
• Any number if
• Entscheidungsproblem: Will
TM-representable √ (π, e, ) • Numerical functions
(+, −, × , ÷)
any algorithm A with arbitrary input I halt? h(A, I ) is incomputable • “Busy beaver” function
Σ(n)
S¨ oren Wellh¨ ofer
Structure and Operational Functionality of The Turing Machine
History Structure and Definition Samples Varieties Computability References
Church?Turing thesis “Every effectively calculable function is a computable function.”
• Effectively calculable: produced intuitively • Computable function: computable by a Turing Machine
S¨ oren Wellh¨ ofer
Structure and Operational Functionality of The Turing Machine
History Structure and Definition Samples Varieties Computability References
Church?Turing thesis “Every effectively calculable function is a computable function.”
• Effectively calculable: produced intuitively • Computable function: computable by a Turing Machine
Solvable by humans = Solvable by machines (algorithm) S¨ oren Wellh¨ ofer
Structure and Operational Functionality of The Turing Machine
History Structure and Definition Samples Varieties Computability References
Church?Turing thesis “Every effectively calculable function is a computable function.”
• Effectively calculable: produced intuitively • Computable function: computable by a Turing Machine
Solvable by humans = Solvable by machines (algorithm) S¨ oren Wellh¨ ofer
Structure and Operational Functionality of The Turing Machine
History Structure and Definition Samples Varieties Computability References
The Universal Turing Machine: A Half-Century Survey R. Herken New York: Oxford University Press, 1988. [http://plato.stanford.edu/entries/turing-machine/] Turing Machines Stanford Encyclopedia of Philosophy, 04.11.1995 [http://www.intelligentedu.com/turing machines examples.html] Turing Machines: Examples Jaime Soffer, 2005. [http://en.wikipedia.org/wiki] Turing Machine, Busy Beaver, Computability, Turing-completeness, Entscheidungsproblem, 11-03-2008 S¨ oren Wellh¨ ofer
Structure and Operational Functionality of The Turing Machine
Related Documents
Turing Machine: Structure And Operational Functionality
December 2019 11
Biological Turing Machine Idea
November 2019 10
Operational Structure
June 2020 1
Turing Machine Synopsis
December 2019 4
Variations Of The Turing Machine
June 2020 20