Unit 5

TURING MACHINES

1. Draw and explain turing machine model.
2. State the techniques for turing machine construction. Explain each of them.
3. What is halting problem? Explain the two cases.
4. If L ={anbn, where n≥1}, Construct turing machine to recognize L(R).
5. Construct turing machine for L ={anbnan , n≥1}.
6. Construct turing machine for 2’s complement of binary number.
7. Construct turing machine for n2.
8. Write a TM for making a copy of string that consists of {a,b}.
9. Write short note on: Halting problem.
10. Write short note on: Church’s turing hypothesis.