Description
Problem 1 (20 points)
Let Σ = {0, 1, #}. Consider the following language over Σ:
L = { w1#w2 | w1, w2 ∈ {0, 1}
∗
and w1 < w2 }.
Note: w1 < w2 means w1 is less than w2 when they are both
viewed as integers in binary. For example, 1110#11100 ∈ L while
0011#011 < L .
Design a Turing machine (in pseudo-code) that recognizes L .
2 / 6
CS 331: Theory of Computing
Problem 2 (20 points)
A 2-dimensional Turing machine is a Turing machine with a
2-dimensional tape that is an unbounded grid of tape squares over
which the head can move in 4 directions: left (L), right (R), up (U)
and down (D). The tape space is denoted by N × N. The head
starts at (0, 0), and is governed by two restrictions:
The head never moves down when it is on the bottom row, i.e., in
positions (i, 0) for i ∈ N,
The head never moves left when it is on the leftmost column, i.e., in
positions (0, i) for i ∈ N.
Prove that 2-dimensional Turning machines are no more powerful
than the standard Turing machines.
Note: Your proof need not be completely formal, but it should have
sufficient details on how a 2-dimensional Turing machine can
simulated by a standard Turing machine step by step.
3 / 6
CS 331: Theory of Computing
Problem 3 (20 points)
Prove that the class of Turing-recognizable languages are closed
under the following operations.
(5 points) Union: L = L1 ∪ L2.
(5 points) Intersection: L = L1 ∩ L2.
(10 points) Concatenation: L = L1 · L2.
Note: Your proof should be constructive. That is, given Turing
machines TM1 and TM2 that recognize L1 and L2 respectively,
your proof should show how to construct a Turing machine TM that
recognize L for each operation.
4 / 6
CS 331: Theory of Computing
Problem 4 (20 points)
Prove the following languages are not Turing-decidable.
(10 points) LB = { hMi | M will write “V” somewhere on the tape }.
(10 points) LU = { hMi | M halts on all words except one }.
5 / 6
CS 331: Theory of Computing
Problem 5 (20 points)
We say that a Turing machine is n-bound if its head visits at most n
squares on the tape.
Is the following language Turing decidable? Prove or disprove it.
LS = { hMi | M is |w| ∗ |w|-bound on any input w. }.
Note: |w| denotes the length of w.
6 / 6
CS 331: Theory of Computing