代写CSC173: Homework 3.2 Turing Machines and Decidability调试R语言程序

CSC173: Homework 3.2

Turing Machines and Decidability

1. Answer the following questions about Turing machines. Explain your answers very briefly.

(a)  Can a Turing machine ever write the blank symbol on its tape?

(b)  Can the tape alphabet Γ be the same as the input alphabet Σ ?

(c)  Can a Turing machine’s head ever be in the same location on two successive steps?

(d)  Can a Turing machine contain just a single state?

2. We proved that a language is recognized by a Turing machine if and only if some enumerator enumerates it (Sipser Theorem 3.21). Does the following simpler sim- ulation algorithm work for the proof? Why or why not?

(a)  Repeat for i = 1, 2, . . . :

(b)  Run M on the ith possible input string

(c)  If it accepts, print out that string

3.  Prove that the language L = {an bn cn |n ≥ 0} is recursive (decidable).

4.  Prove that if a language L is decidable (recursive), then it is also recognizable (recursively enumerable).

5.  Prove that if L is a decidable (recursive) language, then its complement, L, is also decidable (recursive).

6.  Prove that any finite language is decidable (recursive).

7.  Let A be the language containing only the single string s where

Assume that the question of whether life will be found on Mars has an unambigu- ous “yes” or “no” answer. Is A decidable (recursive)? Why or why not?