Turing Machine GK
Turing Machine GK
Turing Machine GK
20 May 2003
Master Editition
1
RECURSIVELY ENUMERABLE LANGUAGES
& TURING MACHINES
TURING MACHINES
M :
# /# R 1/1 R 0/0 R
q0 q1 q2 q3
M :
# /# R a/a R a/a R
q0 q1 q2 q3
b/b R
2
Problem 6. CH9 Problem 3c (Sudkamp)
Construct a Turing Machine with input alphabet {a, b} to perform:
c) Insert a blank between each of the input symbols.
a) computes the function Ratio(x, 2) for arbitrary natural number x in unary representation.
Input alphabet is {1} and tape alphabet {1, X, #}.
b) in unary representation decides if one natural number is bigger then the other. (“Decide”
means that given #1m#1n, M stops and returns YES if m > n, and stops with output NO if
m≤n.) Run the TM to illustrate its function.
d) accepts the language a#b#c, where a, b, c are in {0,1}*, and a + b = c, where a, b and c are
interpreted as positive binary integers.
f) Think about how tedious it would be to design a TM that enumerates all primes in binary!
3
Problems, LINZ
Problem 10. Problem 8, page 257
Suppose we make the requirement that a Turing machine can halt only in a final state, that is,
we ask that δ (q,a) be defined for pairs (q,a) with a ∈Γ and q ∉ F. Does this restrict the power
of the Turing Machine? Prove your answer.
4
DECIDABILITY
Problem 1. (CH11 Problem 12) Prove that there is no algorithm that determines
whether an arbitrary Tuning Machine halts when run with the input string 101.
Problem 2. Prove that the problem of determining whether for a Turing machine M
there is some input string for which M halts is undecidable.
Problem 3. Prove that the problem of determining whether for a Turing machine M the
language L(M) is regular is undecidable.
Problem 6. Prove that the problem of determining if the languages generated by two
CFGs are equal is undecidable.
Problem 7. Decidable or not? Given a (code for a) grammar does the language
produced by the grammar contains infinitely many strings? Motivate your answer!
a) Is there any TM that can decide the problem for a restriction free grammar?
b) Is there any TM that can decide the problem for a context free grammar?
c) Is there any TM that can decide the problem for a regular grammar?
Consider the language of all TMs that given no input eventually write a non-blank symbol
on their tapes. Explain why this set is decidable. Why does this not conflict with the
halting problem?
5
PRIMITIVE RECURSION
Problem 8. CH12 Problem 7a, Sudkamp
Describe the mapping defined by add o (mult o (id , id ), add o (id , id ))
6
RECURSIVELY ENUMERABLE OR NOT?
Problem 12. Determine for each of the following languages whether or not it is
recursively enumerable and whether the complement is or is not recursively enumerable.
Give justification for your answers.
Definitions
A decidable or recursive language is a formal language for which there exists an algorithm to
solve the following decision problem: Given string w, does w belong to the language? The
algorithm is not allowed to run into an infinite loop and has to produce a YES/NO answer for any
input string after a finite amount of time.
Definition 1. Given string w as input, the algorithm halts and outputs YES if and only if w
belongs to the language L. If w does not belong to the language L, the algorithm either runs
forever, or halts and outputs NO.
Definition 2. The algorithm takes a positive integer, say n as an argument, and produces as output
a string in the language L. For every string s which is in L there must be an n so that the algorithm
produces the string s.
7
SOLUTIONS
RECURSIVELY ENUMERABLE LANGUAGES
& TURING MACHINES
TURING MACHINES
Proof
We have two directions:
⇒
L is recursive. This means that L is accepted by a Turing machine M which always halts. We
have to show that L and L are recursively enumerable. Since every recursive language is
recursively enumerable, L is recursively enumerable. To accept L we just switch the accepting
and non-accepting states of M. This makes L recursively enumerable as well.
⇐
L and L are recursively enumerable. This means that L is accepted by a standard Turing Machine
M 1 and that L is accepted by another standard Turing machine M 2 . We have to show that L is
recursive, so that it is accepted by a standard Turing Machine M which always halts. To get M,
we “run” M 1 and M 2 in parallel, say we have two tapes and we run M 1 on tape 1 and M 2 on
tape 2. M accepts if M 1 accepts, and M rejects if M 2 accepts. Note that since either M 1 or M 2
accepts, thus M always halts.
Furthermore, L( M ) = L( M 1 ) = L . So L is recursive.
8
Problem 2. CH9 Problem 25 (Se even Sipser 3.14-3.15)
Prove that the recursive languages are closed under union, intersection, and complement.
Proof
Let L1 and L2 be recursive languages. Then there are Turning Machines M 1 and M 2 , such
that L( M 1 ) = L1 , L( M 2 ) = L2 and both M1 and M2 halt on every input string. We construct
another Turing machine M based on M 1 and M 2 to simulate union, intersection, and
We construct M as following:
a) Union:
Yes
Yes
M1
No
Input
Yes
M2 No
No
M
L( M ) = L1 ∪ L2
b) Intersection:
No
M1 No
Yes
Input
Yes
M2 Yes
No
M
L( M ) = L1 ∩ L2
9
c) Complement:
We just switch the accepting and non-accepting states of M to construct the new TM M’.
Then we have L( M ' ) = L .
Yes
Yes
Input M
No
No
M'
Therefore, recursive languages are closed under union, intersection, and complement.
a) Union operation
Assume L1 and L2 are recursively enumerable. We have two unrestricted grammars G1 and G2 ,
such that
L ( G1 ) = L1 and L ( G 2 ) = L2 .
G1 = (V1 , ∑1 , P1 , S1 )
G2 = (V2 , ∑ 2 , P2 , S 2 )
10
b) Intersection operation
Assume L1 and L2 are recursively enumerable. We can consider two single tape machines M1 and
M2, which accept L1 and L2 respectively. We define M as a single tape TM with three tracks.
Track 1 will hold the input. M will simulates M1 using track 2. If M1 halts in an accepting
configuration M moves the tape head back to the left end and starts simulating M2 or track 3. If
M2 also accepts the input string then the string is accepted by M.
c) Concatenation operation
We use the same assumptions for L1 and L2 as in problem 4a). We define G as being
G = (V1 ∪ V2 ∪ {S }, ∑1 ∪ ∑ 2 , P1 ∪ P2 ∪ {S → S1 S 2 }, S )
*
We have: S ⇒ S1 S 2 ⇒ uS 2 ⇒ uv where u ∈ L1 , v ∈ L2 (leftmost derivation).
The derivation of u uses only rules from G and the derivation of v uses only rules from G (since
V1 ∩ V2 = Φ ) ==> L(G ) ⊆ L1 L2 .
P1 = P ∪ {S1 → SS1| }
Where G ={V, , P, S} is an unrestricted grammar corresponding to L. the rule S1 → SS1|
generates any number of copies of S. Each S generates a string in L. The concatenation of any
number of strings in L represents L*.
==> L1=L* is recursively enumerable.
11
Problem 4. CH11 Problem 6
0/0 R
M :
# /# R 1/1 R 0/0 R
q0 q1 q2 q3
Solution
L (M) = 0*10(1 ∪ 0)*
b/b R
M :
# /# R a/a R a/a R
q0 q1 q2 q3
b/b R
Solution
L ( M ) = ( a ∪ b ) * aa ( a ∪ b ) *
12
Problem 6. CH9 Problem 3c (Sudkamp)
Construct a Turing Machine with input alphabet {a, b} to perform:
c) Insert a blank between each of the input symbols.
Solution
TM:
X/a R
a/a R
b/b R
q2
q5 B/a L
B/B L a/B R
a/X R
b/Y R
B/B L b/B R
B/b L
q3 q6
a/a R
b/b R
Y/b R
13
Solution
1/1 L 1/1 L
X/X L X/X L 1/1 R
B/B L B/B L
q6 q5 q4
1/1 R 1/X R
B/B R
X/X R
1/X R B/B R
q0 B/B R q1 q2 q3 X/X R
n>m
1/1 R
B/B R B/B L
B/B L
1/1 R X/B L
X/X R q7 q 12 q 13
1/B L
B/B L
B/B R
X/B L q9 q 15
B/1 L
B/B R
B/1 R B/1 L
q 10 q 11 q 16
1/1 L
qf
14
Solution
(a) “On input string w:
1) We maintain a set of states corresponding to the symbol we just read.
2) Mark the first symbol with a $ (assume $ ∉ ∑) and go on to the state corresponding
to that symbol read.
3) Move the head toward right till the end of the string (till you hit #) while replacing the
current symbol with the previous symbol (this information is contained in the state the
you are currently in), shifting to the state corresponding to the symbol just read.
4) After hitting the # at the end of the input, replace the #with the last symbol and start
going left back to the start position.
5) Clear the # symbol and move right one position to place the head right on top of the
first symbol of the shifted string.
6) Move one position backwards without doing anything to the tape to place the head
right on top of the original start position, accept.”
7) For any situation not described above, reject.
Solution
a) computes the function Ratio(x, 2) for arbitrary natural number x in unary representation.
Input alphabet is {1} and tape alphabet {1, X, #}. (Salling notation)
X /1
1/ X
R R# L LX
1 /#
# X /#
L#
15
b) in unary representation decides if one natural number is bigger then the other. (“Decide”
means that given #1m#1n, M stops and returns YES if m > n, and stops with output NO if
m≤n.) Run the TM to illustrate its function. (Salling notation)
R
R# R# L L # L#
1 /#
1 /#
# #
NO YES
Hint: To accept odd-valued binary strings, we only have to look at the last bit. The TM moves
right until it reads a blank, moves left one space and accepts if and only if there is a 1 on the
tape.
d) accepts the language a#b#c, where a, b, c are in {0,1}*, and a + b = c, where a, b and c are
interpreted as positive binary integers.
Simulate adding a and b, marking the digits right to left as we go and verifying the digits of c.
• Add a $ to the beginning of the tape and shift the rest of the input.
• Move right past the input string, write another # and a 0. This is the carry bit. Move left
until you hit the $.
• Move right to the first #, then move left until you find an unmarked digit.
• Remembering this digit, move right past a #.
• Move right to the second #, move left until you find an unmarked digit.
• Remembering this second digit, move right past the second #.
• Move right past the last #.
• If the two bits read, plus the carry bit, are equal 2 or 3, write a one to the carry bit.
• Move left past the # and stop at the first unmarked bit. If the the remembered bits plus the
old carry bit are equal to 1 or 3, check for a 1 under the head, and mark it. Otherwise, check
for a zero, and mark it. Reject if the check fails.
• Move left to the $, and repeat from 3.
• When there are no unmarked digits in a and b, move to the carry bit.
• If the carry bit is 1, check for an unmarked 1 in c. Accept as long as there are no unmarked
1s in c.
16
This solution is a bit non-intuitive, because it does not construct the odds by adding one each
time, but by constructing all possible odd-valued n-bit strings by prepending 0 and 1 to all odd-
valued n-1-bit strings. The resulting machine, though, is considerably simpler.
Solution
No, the requirement that a Turing machine must halt only in a final state does not restrict the
power of the machine. Let’s call the modified kind of machines, which halt only on final
states, as the “final-halt” machines. We need to prove that any language accepted by a
standard Turing Machine is also accepted by a no-halt machine, and vice-versa.
(a) Any language accepted by a standard Turing machine is also accepted by a final-halt
machine.
(Proof by construction)
We can convert any standard Turing machine into a final-halt machine using the
following method:
1. Create a new “trap state” with transitions to itself for all inputs
2. For each undefined transition from a non-final state, define a transition to the trap state
For all instances where the standard machine previously halted in a non-final state, the
final-halt machine now enters an infinite loop in a trap state. Therefore, all previous
inputs which where not accepted are still not accepted because the machine loops forever.
All input strings previously accepted are still accepted since transitions towards final
states are not modified.
17
(b) Any language accepted by a final-halt machine is also accepted by a standard Turing
Machine.
Trivially true, since any final-halt machine is also a standard Turing machine.
Solution
For any string w ∈ {a, b, c}+, let wi denote the i-th symbol of w, namely, w = w|w| w|w|-1…
w2 w1. Assign to letters a, b, and c the respective values 1, 2, and 3. The function f(w) that
returns the index for all w ∈ {a,b,c}+ in the proper ordering is:
Solution
Proof by construction:
There exists a Turing machine M1 that accepts L1 and halts on all inputs.
There exists a Turing machine M2 that accepts L2 and may not halt for all inputs.
We can construct a new Turing machine M3 from M1 and M2 that accepts L2 – L1.
M3 should accept all strings accepted by M2 but not accepted by M1.
Machine M3 first needs a new Turing machine to duplicate the input string on the tape.
Next M3 will run M2 and then M1 on the copy of the input with the following changes:
18
o Add transitions from all final states of M2 (and make them non-final states) to the
starting state of M1 (moving the read-write head to the second copy of the input string in
the process). Therefore, if a string is accepted by M2 it will be tested on M1.
o Convert all final states of M1 into non-final states. Furthermore, convert any other
hatling states of M1 to final states. Therefore, if a string is accepted by M1 it is rejected in
M3, and furthermore if a string is rejected by M1 it is accepted by M3.
Accept w
Reject w Reject w
M3
Since M3 contains M2 there are must be instances of w for which M3 does not halt (M2
doesn’t halt for these instances). Therefore, L2 – L1 is necessarily recursively enumerable.
However, if L2 was recursive then M3 would always halt and L2 – L1 would be recursive
as well.
19
Problem 13. Problem 13, page 282
Suppose that L is such that there exists a Turing machine that enumerates the elements of L in
proper order. Show that this means that L is recursive.
Solution
If there exists a Turing machine that enumerates the elements of L in proper order then it
must be a recursive language.
Proof by construction:
By definition, L is recursive if and only if there exists a membership algorithm for it.
We will construct a Turing machine M that determines membership in language L,
namely, for any input string w, machine M determines if w is in L or not.
Let M1 be the Turing machine that enumerates the elements of L in proper order.
Machine M compares the input string w with each output from M1.
If string w equals an output from machine M1 then machine M returns “yes”.
If the length of an output string from M1 exceeds the length of w then M returns “no”.
This works because strings in proper order are in order of increasing length. Thus, if M1
reaches a point where it is producing strings with a length greater than that of w, we know
that it will never produce w. This membership algorithm always produces an answer in
finite time (always halts) so L must be recursive.
20
DECIDABILITY
Problem 1. CH11 Problem 12 Sudkamp
Prove that there is no algorithm that determines whether an arbitrary Tuning Machine halts when
run with the input string 101.
Solution 1 (By Blank Tape Problem):
Assume that there is such a TM A exist:
M halts on 101
accept
R(M)101 A
reject
M doesn't halts on 101
So this solves the blank tape problem but blank tape problem is undecidable.
Therefore, there is no algorithm that determines whether an arbitrary Tuning Machine halts when
run with the input string 101.
We can reduce the halting problem to this problem by a TM N. The input is the representation of
a TM M followed by an input string w. The result of a computation of N is the representation of a
machine M’ that:
1. Replace 101 with w.
2. Return the tape head to the initial position with the machine in the initial state of M.
3. Runs M.
21
M halts on w
M' halts on 101 accept
R(M)w N R(M')101 A
M' doesn't halts on reject
101 M doesn't halt on w
This reduces the halting problem to the “101” problem and the halting problem is undecidable.
Therefore, there is no algorithm that determines whether an arbitrary Tuning Machine halts when
run with the input string 101.
Problem 2. Prove that the problem of determining whether for a Turing machine M
there is some input string for which M halts is undecidable.
Solution
Let’s call the problem for which we want to prove it is undecidable as the “any string”
problem. We will reduce the halting problem to the “any string” problem,
as shown in the above figure.
First, we take M and w and we construct a new machine M’, such that M’ first simulates
M on input w. If during the simulation M halts on input w, then M’ enters a new set of
states in which M’ halts for some input string on the tape of M’. However, if during the
simulation M doesn’t halt on input w, then M’ is stuck in the simulation of M, and thus M’
will not halt either, for any input string on the tape of M’.
We now have constructed M’ in such a way that if M halts on w, M’ will halt on some
string. Otherwise, if M doesn’t halt on w, then M’ will not halt as well. Therefore, if we
now the answer to the question of whether M’ halts on any input string, then we know the
answer to the question of whether M halts on w or not.
Because we have reduced the halting problem to the “any string” problem, we can
conclude that because the halting problem is undecidable, neither is the “any string”
problem.
22
Problem 3. Prove that the problem of determining whether for a Turing machine M the
language L(M) is regular is undecidable.
Solution
Let’s call the problem which we want to prove is undecidable as the “regular” problem.
We will reduce the halting problem to the “regular” problem,
as shown in the above figure.
First, we take M and w and we construct a new machine M’, such that M’ first simulates
M on input w. If during the simulation M halts on w, then M’ enters a new set of states in
which M’ accepts a non-regular language, like anbn, on the tape of M’. Namely, in this
case L(M’) = {anbn} which is non-regular . Otherwise, if during the simulation M does not
halt on w, then M’ is stuck in the simulation of M, and thus M’ will not halt either. In this
case M’ will not accept any string and thus L(M’) = ∅ , which is a regular language since
there is a finite automaton with one state which doesn’t accept any string.
We now have constructed M’ in such a way that if M halts on w, then L(M’) is a non-
regular language. Otherwise, if M doesn’t halt on w, then L(M’) is a regular language.
Therefore, if we know the answer to the question of whether L(M’) is regular or not, then
we know the answer to the question of whether M halts on w or not.
Therefore, the halting problem can be reduced to the “regular” problem, and because the
halting problem is undecidable, so must be the “regular” problem.
23
Problem 4. Prove each of the following languages decidable or undecidable.
Solution
1. Undecidable. We give a reduction from ETM. Suppose that this language is decidable.
Let T be a Turing machine that decides it. Then we can construct a Turing machine T´ deciding
ETM, that behaves as follows on input <M>.
(a) Simulate T on input <M, M´>, where M´ is a Turing machine recognizing the empty
language.
(b) Accept if and only if T accepts.
Suppose that M accepts the empty language. Then T accepts <M, M´>, and so T´ accepts. On the
other hand, suppose that M accepts some string. Then T rejects <M, M´>, and so T´ rejects. Thus,
T´ decides ETM.
4. Decidable. Deciding the language requires only inspection of the encoding <M>.
5. Undecidable. We give a reduction from ATM (accept(halting) problem). Suppose that this
language is decidable. Let T be a Turing machine that decides it. Then we can construct a Turing
machine T´ deciding ATM, that behaves as follows on input <M;w>.
(a) Construct a Turing machine M´ that behaves as follows on input v.
i. Simulate M on input w.
ii. Accept if and only if M accepts.
(b) Simulate T on input <M>.
(c) Accept if and only if T accepts.
Suppose that M does not accept w. Then M´ never accepts, the simulation of T rejects, and so T´
rejects. On the other hand, suppose that M does accept w. Then M´ accepts every string v in a
number of steps independent of |v| thus, in particular, M´ accepts some string v in fewer thatn |v|
steps. Therefore, the simulation of T accepts, and so T´ accepts. Thus T´ decides ATM.
24
Problem 5. Consider the problem of testing whether a Turing machine M on input w
ever attempts to move its head left when its head is on the left-most tape cell. Formulate
this problem as a language and show that it is undecidable.
Solution
The proof is by contradiction. Assume that this problem is decidable, then we will show
that ATM is also decidable:
ATM = {<M, w> | M is a TM and M accepts w}.
Let R be a Turing machine that decides the problem. That is, R decides the language
LEFTMOST = {<M, w> | M on input w ever attempts to move its head left when it's head
is on the left-most tape cell }.
We can construct a Turing machine S that decides ATM as follows. On input <M; w>, S
first modifies machine M to M´, so that M´ moves its head to the left from the left-most
cell only when M accepts its input. To ensure that during its computation M´ doesn't
move the head left from the left-most position, machine M´ first shifts the input w one
position to the right, and places a special symbol on the left-most tape cell. The
computation of M´ starts with the head on the second tape cell. If during its computation
M´ ever attempts to move its head to the left-most tape cell, M´ finds out that it did so by
reading the special symbol and then puts the head back to the second cell, and continues
its execution. If M would enter an accept state, then M´ enters a loop that forces the head
to move always to the left.
After S has constructed M´ it runs the decider R on input < M´; w>. If R accepts then S
accepts, otherwise if R rejects then S rejects.
Problem 6. Prove that the problem of determining if the languages generated by two
CFGs are equal is undecidable.
Solution
We show this by reducing the problem of determining whether a CFG accepts everything
to the problem of determining if the languages generated by two CFGs are equal by taking
our input CFG and comparing it to the CFG that generates everything. Since we know
from class that the "everything" problem is undecidable, the "equal" probably must also
be.
25
Problem 7. Decidable or not? Given a (code for a) grammar does the language produced
by the grammar contains infinitely many strings? Motivate your answer!
d) Is there any TM that can decide the problem for a restriction free grammar?
e) Is there any TM that can decide the problem for a context free grammar?
f) Is there any TM that can decide the problem for a regular grammar?
Solution
Consider the language of all TMs that given no input eventually write a non-blank symbol
on their tapes. Explain why this set is decidable. Why does this not conflict with the
halting problem?
The state of a Turing machine is determined by the state of its controller (a DFA) and the
state of the tape. Since the controller is finite, there are only a finite number of states
possible before the TM is forced to either loop or write a symbol, so we simply run the
Turing machine for that number of steps and then accept if it has written a symbol and
reject otherwise.
This does not conflict with the halting problem because we are considering only a subset
of Turing machines (those roughly equivalent to DFAs) and not really addressing the
halting problem for Turing machines.
26
PRIMITIVE RECURSIVE
Problem 8. CH12 Problem 7a, Sudkamp
Describe the mapping defined by add o (mult o (id , id ), add o (id , id ))
Solution:
Solutions:
First let’s do f ( x) = 2 x , nothing that
f ( y + 1) = f ( y ) + 2 and f (0) = 0
Have
f (0) = 0 ← k
f ( y + 1) = s o s o p 2( 2 ) ( y, f ( y ))
Now, f ( y ) = 2 y + 2 just adds “2”, so just need to start with f (0) = 2 .
Have
f (0) = 2 ← k
f ( y + 1) = s o s o p 2( 2 ) ( y, f ( y ))
27
So
g=2
h( y, f ( y )) = s o s o p 2( 2) ( y, f ( y ))
Check:
f (3) = h(2, f (2))
= s o s o p 2( 2 ) (2, f (2))
= s o s o f (2)
= s o s o s o s o p 2( 2) (1, f (1))
= s o s o s o s o f (1)
= s o s o s o s o s o s o p 2( 2 ) (0, f (0))
= s o s o s o s o s o s o f (0)
= sosososososo2
=8
Therefore f ( x) = 2 x + 2 is primitive recursive.
Solution
max( x, y ) = x ⋅ ( gt ( x, y ) + eq( x, y )) + y ⋅ gt ( y, x)
Check:
max(2,3) = 0 ⋅ 2 + 1 ⋅ 3 = 3
max(3,2) = 1 ⋅ 3 + 0 ⋅ 2 = 3
max(2,2) = 1 ⋅ 2 + 0 ⋅ 2 = 2
Therefore max( x, y ) is primitive recursive.
28
NAME THE LANGUAGE
Problem 11. For each of the languages below, give the smallest language class that
contains it [i.e. Regular, Deterministic Context Free, Context Free, Turing Machines
(Recursive)]. Assume an alphabet of {0,1} unless other specified. You do not need to
prove your answers.
Solution
29
RECURSIVELY ENUMERABLE OR NOT?
Problem 12. Determine for each of the following languages whether whether or not it is
recursively enumerable and whether the complement is or is not.
We can enumerate all possible regular languages, but testing every regular
language against every TM would take forever. If fact, even testing a TM against a
single infinite regular language would take forever.
We would have to try every string before declaring that a PDA accepts everything,
but since membership in a CFG (equivalent to a PDA) is decidable, we determine
that a PDA does not accept anything once it rejects anything.
We can determine that a CFG is ambiguous by finding a single string which has an
ambiguous derivation, but we cannot determine if a CFG is unambiguous unless
we try everything string in it.
30
References
2. Linz, An Introduction to Formal Languages and Automata, Jones & Bartlett 2000
31