SSK5204
CHAPTER 8:TURING MACHINES
DR. NOR FAZLIDA MOHD SANI,
DEPT. OF COMPUTER SCIENCE,
FAC. OF COMPUTER SCIENCE AND INFORMATION
TECHNOLOGY, UPM.
WHAT IS A COMPUTER?
program
input
computer
output
A computer is a machine that manipulates data
according to a list of instructions.
WHAT IS A COMPUTER?
void hello( String name)
{
print( Hello, , name);
}
world
deep blue
E2-E4
computer
Hello, world
?
3
TURING MACHINES
control
head
a b b
input
blanks
Can both read from and write to the tape
Head can move both left and right
Tape is infinite
Has two special states accept and reject
4
EXAMPLE
L1 = {w#w: w {a, b}*}
Strategy:
Read and remember the first symbol
abbaa#abbaa
Cross it off (x)
xbbaa#abbaa
Read the first symbol past #
xbbaa#abbaa
If they dont match, reject
If they do, cross it off
xbbaa#xbbaa
EXAMPLE
L1 = {w#w: w {a, b}*}
Strategy:
Look for the first uncrossed symbol
xbbaa#xbbaa
Cross it off (x)
xxbaa#xbbaa
Read the first uncrossed symbol past # xxbaa#xbbaa
If they match, cross it off, else reject
xxbaa#xxbaa
xxxxx#xxxxx
At the end, there should be only xs and #s
If not, reject; otherwise, accept.
6
HOW TURING MACHINES OPERATE
current state
q1
a/bL
q2
a b a
Replace a with b, and move head left
new state
q1
a/bL
q2
a b b
FORMAL DEFINITION
A Turing Machine is (Q, , , , q0, qacc, qrej):
Q is a finite set of states;
is the input alphabet not containing the blank symbol
is the tape alphabet ( ) including
q0 in Q is the start state;
qacc, qrej in Q are the accepting and rejecting state
is the transition function
: (Q {qacc, qrej}) Q {L, R}
Turing Machines are deterministic
8
CONFIGURATIONS
A configuration consists of the current state, the head
position, and tape contents
configuration
q1
q1
qacc
a/bR
abq1a
qacc
abbqacc
CONFIGURATIONS
We say configuration C yields C if the TM can go from C
to C in one step
abq1a yields abbqacc
The start configuration of the TM on input w is q0w
An accepting configuration is one that contains qacc;
A rejecting configuration is one that contains qrej
10
THE LANGUAGE OF A TURING MACHINE
We say M accepts x if there exists a sequence of
configurations C0, C1, ..., Ck where
C0 is starting
Ci yields Ci+1 Ck is accepting
The language recognized by M is the set of
all strings that M accepts
11
LOOPING
Something strange can happen in a Turing Machine:
/R
qacc
q0
= {0, 1}
input: e
qrej
This machine
never halts
Inputs can be divided into three types
qacc
accept
qrej
reject
loop
12
HALTING
We say M halts on x if there exists a sequence of
configurations C0, C1, ..., Ck where
C0 is starting
Ci yields Ci+1
Ck is accepting
or rejecting
A TM M is a decider if it halts on every input
Language L is decidable if it is recognized by
a TM that halts on every input
13
PROGRAMMING TURING MACHINES
Description of Turing Machine: L1 = {w#w: w {a, b}*}
1
Until you reach #
Read and remember entry
Write x
Move right past # and past all xs
If this entry is different, reject
Otherwise
Write x
Move left past # and to right of first x
If you see only xs followed by , accept
2
3
4
5
xbbaa#xbbaa
xxbaa#xbbaa
xxbaa#xbbaa
xxbaa#xxbaa
xxbaa#xxbaa
14
PROGRAMMING TURING MACHINES
a/aR
b/bR
L1 = {w#w: w {a, b}*}
x/xR
#/#R
x/xR
a/aL
b/bL
x/xL
q0 #/#R
q1 /R qacc
1
8
q2
qa1
qa2
a/aL
b/bL
#/#L
q3
qrej
everything else
qb1
a/aR
b/bR
#/#R
qb2
x/xR
x/xR
15
PROGRAMMING TURING MACHINES
input: aab#aab
a/aR
b/bR
x/xR
#/#R
x/xR
a/aL
b/bL
x/xL
q0 #/#R
q1 /R qacc
1
8
q2
qa1
qb1
a/aR
b/bR
#/#R
qa2
qb2
x/xR
x/xR
a/aL
b/bL
#/#L
q3
7
configurations:
q0aab#aab
xqa1ab#aab
xaqa1b#aab
xabqa1#aab
xab#qa2aab
xabq2#xab
xaq3b#xab
xq3ab#xab
q3xab#xab
xq0ab#xab
16
PROGRAMMING TURING MACHINES
L2 = {aibjck: i j = k and i, j, k > 0 }
High-level description of TM:
aabbcccc
For every a:
aabbcccc
Cross off the same number of bs and cs
Uncross the crossed bs (but not the cs)
Cross off this a
If all as and cs are crossed off, accept.
aabbcccc
= {a, b, c}
= {a, b, c, a, b, c, }
aabbcccc
aabbcccc
aabbcccc
aabbcccc
aabbcccc
17
PROGRAMMING TURING MACHINES
L2 = {aibjck: i j = k and i, j, k > 0 }
Low-level description of TM:
Scan input from left to right to check it looks like aa*bb*cc*
Move the head to the first symbol of the tape
For every a:
how do we know?
Cross off the same number of bs and cs how to do this?
Restore the crossed of bs (but not the cs)
Cross off this a
If all as and cs are crossed off, accept.
18
PROGRAMMING TURING MACHINES
aabbcccc
Implementation details:
Move the head to the first symbol of the tape
aabbcccc
Put a special marker on top of first a
Cross off the same number of bs and cs:
aaqbbcccc
aabqbcccc
aabbqcccc
aabqbcccc
aabbqcccc
aabbcqccc
aabbqcccc
Replace b by b
Move right until you see a c
Replace c by c
Move left just past the last b
If any bs are left, repeat
= {a, b, c}
= {a, b, c, a, b, c, a, a, }
19
PROGRAMMING TURING MACHINES
L3 = {#x1#x2...#xl : xi {0, 1}* and xi xj for each i j}
High-level description of TM:
#01#0011#1
On input w,
For every pair of blocks xi and xj in w,
Compare the blocks xi and
xj they are the same,
If
reject. accept.
Otherwise,
20
PROGRAMMING TURING MACHINES
L3 = {#x1#x2...#xl : xi {0, 1}* and xi xj for each i j}
Low-level description:
#01#0011#1
0. If input is e, or has exactly one #, accept.
1. Place a mark on the leftmost #
(i.e. replace # by #) and move right
#01#0011#1
#
2. Place another mark on next unmarked#01#0011#1
(If there are no more #, accept)
21
PROGRAMMING TURING MACHINES
L3 = {#x1#x2...#xl : xi {0, 1}* and xi xj for each i j}
#01#0011#1
current state:
3. Compare the two strings to the right
of marked #. If there are same, reject
#01#0011#1
#01#0011#1
4. Move the right # to the right
If not possible, move the left # to the
next # and put the right # on the next
If not possible, accept
5. Repeat Step 3
#01#0011#1
22
PROGRAMMING TURING MACHINES
L3 = {#x1#x2...#xl : xi {0, 1}* and xi xj for each i j}
3. Compare the two strings to the right
of marked #. If there are same, reject
#01#0011#1
#01#0011#1
4. Move the right # to the right
If not possible, move the left # to the accept
next # and put the right # on the next
If not possible, accept
23
HOW TO DESCRIBE TURING
MACHINES?
Unlike for DFAs, NFAs, PDAs, we rarely give complete
state diagrams of Turing Machines
Usually we give a high-level description:
A recipe about the workings of the Turing Machine
Just like in cooking, practice makes perfect!
24
PROGRAMMING TURING MACHINES
L4 = {G: G is a connected undirected graph}
Q: How do we feed a graph into a Turing Machine?
A: We represent it by a string, e.g.
(1,2,3,4)((1,4),(2,3),(3,4)(4,2))
1
Convention for describing graphs:
(nodes)(edges)
no node must repeat
edges are pairs (node1,node2)
25
PROGRAMMING TURING MACHINES
L4 = {G: G is a connected undirected graph}
On input G,
0. Verify that G is the description of a graph
(no vertex repeats; edges only go between nodes)
1. Mark the first node of G
1
2. Repeat until no new nodes are marked:
For each node, mark it if it is attached
to an already marked node
3. If all nodes are marked accept, otherwise reject.
x
4
26
PROGRAMMING TURING MACHINES
L4 = {G: G is a connected undirected graph}
(1,2,3,4)((1,4)(2,3)(3,4)(4,2))
(1,2,3,4)((1,4)(2,3)(3,4)(4,2))
(1,2,3,4)((1,4)(2,3)(3,4)(4,2))
1
(1,2,3,4)((1,4)(2,3)(3,4)(4,2))
(1,2,3,4)((1,4)(2,3)(3,4)(4,2))
(1,2,3,4)((1,4)(2,3)(3,4)(4,2))
3
(1,2,3,4)((1,4)(2,3)(3,4)(4,2))
(1,2,3,4)((1,4)(2,3)(3,4)(4,2))
(1,2,3,4)((1,4)(2,3)(3,4)(4,2))
(1,2,3,4)((1,4)(2,3)(3,4)(4,2))
etc.27
Whats so great about
Turing Machines?
28
Hilberts list of 23 problems
Leading mathematician in the 1900s
At the 1900 International Congress
of Mathematicians, proposed a list of
23 problems for the 20th century
David Hilbert
Hilberts 10th problem:
(1862-1943)
Find a method to tell if an equation like
xyz 3xy + 6xz + 2 = 0 has integer solutions
29
A BRIEF HISTORY OF COMPUTING
DEVICES
Z3 (Germany, 1941)
PC (1980)
ENIAC (Pennsylvania, 1945)
MacBook Air (2008)
30
COMPUTATION IS UNIVERSAL
In principle, all these
have the same problem-solving ability
31
THE CHURCH-TURING THESIS
Turing Machine
If an algorithm can be implemented on
any realistic computer, then it can be
implemented on a Turing Machine.
32
THE CHURCH-TURING THESIS
Turing Machine
quantum computing
cosmic computing
DNA computing
33
ALAN TURING
Invented the Turing Test to tell
humans and computers apart
Broke German encryption machines
in World War II
The Turing Award is the Nobel
prize of Computer Science
Alan Turing
(1912-1954)
Turings motivation: By studying Turing
Machines, we can understand the limitations of
real computers.
34
UNDECIDABILITY
What Hilbert meant to ask was:
Find a Turing Machine to tell if an equation
like
xyz 3xy + 6xz + 2 = 0 has integer solutions
Building on work of Gdel, Church, Turing, Davis,
Putnam, Robinson, in 1970 Matijasievi showed:
There is no such Turing Machine!
35
COMPUTER PROGRAM ANALYSIS
public static void main(String args[]) {
System.out.println("Hello World!");
}
What does this program do?
public static void main(String args[]) {
int i = 0;
for (j = 1; j < 10; j++) {
i += j;
if (i == 28) {
System.out.println("Hello World!");
}
}
}
How about this one?
36
COMPUTERS CANNOT ANALYZE
PROGRAMS!
No Turing Machine can do this:
input: The code of a java program P
Accept if P prints hello, world
Reject if not
Significance: It is impossible for computer
to predict what a computer program will
do!
37
HOW DO YOU ARGUE THINGS LIKE
THAT?
To argue what computers cannot do,
we need to have a precise definition
of what a computer is.
Turings answer: A computer is just
a Turing Machine.
1936: On Computable Numbers, with an
Application to the Entscheidungsproblem
Section 1. Computing Machines
38
THE CHURCH-TURING THESIS
All arguments [for the CT Thesis] which can be given are
bound to be, fundamentally, appeals to intuition, and for this
reason rather unsatisfactory mathematically.
The arguments which I shall use are of three kinds:
1. A direct appeal to intuition
2. A proof of the equivalence of two definitions
(In case the new definition has greater intuitive appeal)
3. Giving examples of large classes of numbers which are
computable.
1936: On Computable Numbers, with an
Application to the Entscheidungsproblem
Section 9. The extent of the computable numbers
39
Variants of Turing Machines
40
THE CHURCH-TURING THESIS
All arguments [for the CT Thesis] which can be given are
bound to be, fundamentally, appeals to intuition, and for this
reason rather unsatisfactory mathematically.
The arguments which I shall use are of three kinds:
1. A direct appeal to intuition
2. A proof of the equivalence of two definitions
(In case the new definition has greater intuitive appeal)
3. Giving examples of large classes of numbers [languages]
which are computable.
1936: On Computable Numbers, with an
Application to the Entscheidungsproblem
41
Section 9. The extent of the computable numbers
THE MULTITAPE TURING MACHINE
control
tape 1 0 1 0
tape 2 0 1
tape 3 1 0 0
The transition may depend on the contents of
all the cells
Different tape heads can be moved independently
42
THE MULTITAPE TURING MACHINE
0 1 0
0 1
1 0 0
q3
0/1R
/1R
0/0L
q7
1 1 0
0 1 1
1 0 0
Multiple tapes are convenient,
e.g. one can serve as temporary storage
43
HOW TO ARGUE EQUIVALENCE
Multitape Turing Machines are equivalent
to single-tape Turing Machines
single tape
multiple tapes
44
THE MULTITAPE TURING MACHINE
Multitape Turing Machines are equivalent
to single-tape Turing Machines
# 0
= {0, 1, }
0 # 0
# 1
0 #
= {0, 1, , 0, 1, , #}
45
SIMULATING A MULTITAPE TM
We show how to simulate a multitape TM on an single
tape TM
To be specific, lets do a 3-tape TM
x
y1
y2
z1
zc
xa xi
yb
yj
zk
Multitape TM
#x1x2...x a...xi#y1y2...yb...yj#z1z2...zc...zk#
Single-tape TM
46
SIMULATING A MULTITAPE TM
Single-tape TM: Initialization
w1w2...wn
#w 1w2...wn###
# 0
0 #
S: On input w1...wn:
1. Replace tape contents by
#w1w2...wn###
Remember that M is in state q0
47
SIMULATING A MULTITAPE TM
Single-tape TM: Simulating Multitape TM moves
Suppose Multitape TM wants to move like this:
q3
0/1R
/1R
0/0L
q7
We simulate move on single-tape TM like this:
# 0
# 0
0 # 0
0 # 0
# 1
# 1
0 #
0
0 #
48
SIMULATING A MULTITAPE TM
S: On input w1...wn:
1. Replace tape contents by
#w1w2...wn###
Remember (in state) that M is in state q0
2. To simulate a step of M:
Make a pass over tape to find
x, y, z
#x1x2...x...x
i#y1y2...y...yj#z1z2...z...zk#
If M is in state qi and has
update state / tape accordingly.
transitionqi
x/xA
y/yB
z/zC
qj
3. If M reaches accept (reject) state, accept (reject).
49
DOING SIMULATIONS
To simulate a model M by another model N:
1. Say how the state and storage of N is used
to represent the state and storage of M
2. Say what should be initially done to convert
the input of N (if anything)
3. Say how each transition of M can be implemented
by a sequence of transitions of N
50
WHAT DOES A COMPUTER LOOK
LIKE?
CPU
PC
0000
arithmetic
logical unit
registers
R0
R1
R2
R3
instruction
memory
data memory
0100
1010
0000
0000
51
WHAT DOES A COMPUTER LOOK
LIKE?
instruction memory
CPU
PC
0000
0001
0010
0011
0100
0000
arithmetic
logical unit
registers
R0
R1
R2
R3
load 0001
write R3
store R5
add R5
jpos 0011
...
0100
1010
data memory
0000
0000
0001
0010
0011
0100
0000
0110
0110
0110
0110
0110
52
INSTRUCTION SET
load x
Put the value x into R0
load Rk
Copy the value of Rk into R0
store Rk
Copy the value of R0 into Rk
read Rk
Copy the value at memory location Rk into R0
write Rk
Copy the value of R0 into memory location Rk
add Rk
Add R0 and Rk, and put result in R0
jump n
Set PC to n
jzero n
Set PC to n, if R0 is zero
jpos n
Set PC to n, if R0 is positive
53
RANDOM ACCESS MACHINES
PC 0
program
counter
R0
registers
R1
R2
2
0
1
1
2
2
0
1
2
3
4
5
instruction
meaning
load -7
write R2
store R1
add R1
jzero 3
accept
R0 := -7
M[R2] := R0
R1 := R0
R0 := R0 + R5
if R0 = 0 then PC := 3
2
3
0
4
memory
It has registers that can store integer values, a
program counter, and a random-access memory
54
RANDOM ACCESS MACHINES
PC 01
23
45
R0
R1
07
14
07
R2
0-7
0
0
1
2
3
4
5
0
1
0
2
instruction
meaning
load 7
write R2
store R1
add R1
jzero 3
accept
R0 := 7
M[R2] := R0
R1 := R0
R0 := R0 + R1
if R0 = 0 then PC := 3
0
3
0
4
The instructions are indexed by the program counter
Initially, the input is in the first k memory cells, all registers
and PC are set to 0
55
RANDOM ACCESS MACHINES
Random access machines are equivalent
to Turing Machines
Simulating a Turing Machine on a RAM:
PC
= {0, 1, 2, ..., k}
R0
blank
56
SIMULATING A TM ON A RAM
q0 1/2R q1
R1
0
1
2
3
store R1
read R1
x
add -1
jzero 6
handle
for state
q0
save
head
position
read tape contents
if x = 1 goto line 6
6
7
8
9
10
load 2
new value of cell
write R1
write in memory
load R1
recall head position
add 1 move head to right
30
jump
go to state q1
handle for state q1
30 store R1
PC 0
R0
program
200 accept
handle for state qacc
57
SIMULATING A TM ON A RAM
q0 1/2R q1
R0
23
2
0
21
R1
02
program
store R1
read R1
x
add -1
jzero 6
handle
for state
q0
save
head
position
read tape contents
load 2
write R1
load R1
add 1
30
jump
30 store R1
new value of cell
write in memory
recall head position
move head to right
go to state q1
handle for state q1
0
1
2
3
6
7
8
9
10
(head)
if x = 1 goto line 6
12 (tape)
58
SIMULATING A RAM ON A TURING
MACHINE
The configuration of a RAM consists of
Program counter
Contents of registers
Indices and contents of all nonempty memory cells
PC 14
R0
R1
17
R2
2
0
configuration =
(14, 3, 17, 5, (0, 2), (2, 1), (3, 2))
0
1
1
2
2
3
0
4
59
SIMULATING A RAM ON A 2-TAPE TM
The TM has a simulation tape and a scratch tape
The simulation tape stores RAM configuration
(14,3,17,5,(0,2),(2,1),(3,2))
The TM has a set of states corresponding to each
program instruction of the RAM
The TM tape is updates according to RAM instruction
60
SIMULATING A RAM ON A 2-TAPE TM
Initialization
TM input:
122
RAM initial state: PC 0
R0
...
S: On input w1...wn:
1. Replace tape contents by
(0, 0, 0, ..., 0, (0, w1), (1, w2), ..., (n-1, wn))
61
SIMULATING A RAM ON A 2-TAPE TM
Example: load R1
(14,3,17,5,(0,2),(2,1),(3,2))
1. Copy R1 to scratch tape s 17
2. Write R1 to conf tape
c
s
(14,1,17,5,(0,2),(2,1),(3,2))
17
.
(14,1,17,5,(0,2),(2,1),(3,2) )
.
(14,1 ,17,5,(0,2),(2,1),(3,2))
3. Erase scratch tape
(14,17,17,5,(0,2),(2,1),(3,2))
4. Update PC
(15,17,17,5,(0,2),(2,1),(3,2))
Make more space
as needed
62
SIMULATING A RAM ON A 2-TAPE TM
S: On input w1...wn:
1. Replace tape contents by
(0, 0, 0, ..., 0, (0, w1), (1, w2), ..., (n-1, wn))
2. Simulate instruction in RAM program
by a sequence of TM transitions
See notes for details.
3. If RAM instruction is accept, go to accept state.
If RAM instruction is reject, go to reject state.
63
