CSCI 510, Fall 2016, Homework # 5
1. Show that A is Turing-recognizable iff A ≤m ATM. 2. Let J = {w | either w = 0x for some x ∈ ATM, or w = 1y for some y ∈ ATM}. Show that neither J nor J is Turing-recognizable.
3. Let
f(x) =? 3x + 1 for odd x x/2 for even x for any natural number x. If you start with a natural number x and iterate f, you obtain a sequence, x,f(x),f(f(x)),... Stop if you ever hit 1. For example, if x = 17, you ge the sequence 17,52,26,13,40,20,10,5,16,8,4,2,1. Extensive computer tests have shown that every starting point between 1 and a very large positive integer gives a sequence that ends in 1. But the question of whether all positive starting points end up at 1 is unsolved; it is called the 3x + 1 problem. Suppose that ATM were decidable by a TM H. Use H to describe a TM that is guaranteed to state the answer to the 3x + 1 problem. 4. Let T = {hMi|M is a TM that accepts wR whenever it accepts w}. Show that T is undecidable. 5. Show that the Post Correspondence Problem is decidable over the unary alphabet Σ = {1}. 6. Prove that there exists an undecidable subset of {1}∗.
1
