Description
The Problems
Let L = { 0
y
| y = 2
n
for n >= 0} . L is the language consisting of all strings of 0s whose length is
a power of 2.
You will find a state diagram for a Turing machine that decides L in Figure 3.8 on p. 172.
10 points
1. Give a formal description of the Turing machine, M, that decides L, using the format in
Definition 3.3 on p. 168. Do not enumerate δ. That will be done implicitly in part B.
15 points
2. Write a python program that simulates a Turing machine M that decides L, both from
Problem 1. The program is invoked from the Linux command line. The Turning machine will
continuously accept input and display ‘accept’ or ‘reject,’ depending on whether the input is or is
not an element of L. By “continuous input,” I mean this sequence:
a. User enters a string.
b. If the string is ‘quit,’ the program stops, otherwise M evaluates the string and prints
‘accept’ or ‘reject’
d. Go to step a
Please do not print anything else, not transitional states, not welcomes or goodbyes, only
‘accept’ or ‘reject’
Hint: I’m sure you have realized that δ is a collection of functions. The easiest approach is to
code each state as a function in your program.
We know that if A ≦M B and A is undecidable, then B is undecidable. We use this principle to
conclude that an important problem in computational theory is undecidable.
5 points
3. What is that problem?
5 points
4. State that problem informally.
5 points
5. What theorem did we call the “gloomiest theorem of them all?”
10 points
6. Extra Credit
Theorem 3.2
if A ≦M B and B is decidable then A is decidable.
Corollary 5.23
if A ≦M B and A is undecidable, then B is undecidable
Strange? Maybe?
Now suppose A ≦M B and B is a regular language. Is A regular? Why or why not?
