COMS 331: Theory of Computing, Spring 2021 Homework Assignment 7
Due at 10:00PM, Wednesday, March 17, on Gradescope.
Problems 43 and 44 can be found in your textbook Automata and Computability by Dexter Kozen. You only have to give a high level description of the Turing Machine you design.
Problem 43. Page 309 #1. Problem 44. Page 340 #96.
Problem 45. Prove that the set of Turing-decidable languages are closed under union, i.e., if both L1 and L2 are Turing-decidable, then L1 ∪ L2 is Turing-decidable.
Problem 46. Prove that the set of Turing-decidable languages are closed under reversal, i.e., if L is Turing-decidable, then LR = {x ∈ Σ∗ | xR ∈ L, where xR is the reverse of x} is Turing decidable.
Problem 47. Consider a variant of Turing machine called 2-cell Turing machine which has a finite set of states, a semi-infinite left-ended tape(just as a standard Turing machine), a read/write tape head that has access to 2 tape cells, i.e., in a single step, the head can simultaneously read the tape cell under it and the tape cell to the right of it, and can write to those two cells. Show how you can simulate these 2-cell Turing machines with standard Turing machines.
Problem48.ProvethatA≤M AjoinBwhereAjoinB={0x|x∈A}∪{1y|y∈B}.
Problem 49. Show that A = {M | M is a TM, and M accepts wR whenever it accepts w} is un- decidable.
1