Undecidable among these for turing machine

Problem Detail: 

Below are two questions I found in Theory of Computation book but couldn't find its correct answers, can anyone please give correct answers with explanation?

1. It is undecidable, whether
   1. an arbitrary Turing machine(TM) has 15 states
   2. an arbitrary TM halts after 10 steps
   3. an arbitrary TM ever prints a specific letter
   4. an arbitrary TM accepts a string w in 5 steps
2. Which one of the following is not decidable?
   1. given a TM M, a string s and an integer k, M accepts s with k steps
   2. equivalence of two given TMs
   3. language accepted by a given DFSA(Deterministic finite state automata) is nonempty
   4. language accepted by a CFG(Context free grammar) is nonempty

Update: In first question I think 1.2 is right because halting is undecidable for Turing machine but not sure whether remaining options are decidable or not.
In second question I think 2 is right, but not sure about the decidability of non emptiness of CFG and DFSA.

Asked By : AbhiW

Answered By : Patrick87

(1.1) Is it undecidable whether an arbitrary Turing machine(TM) has 15 states?

No, this is a decidable problem. Given a TM in a suitable encoding, it is fairly straightforward to determine how many states the TM has. Consider any common encoding, or define a reasonable one yourself, and then describe an algorithm that answers the question using the encoding. Hint: you can make your algorithm really simple if you define the encoding such that the first part of the encoding is an encoded list of states that are part of the TM.

(1.2) Is it undecidable whether an arbitrary TM halts after 10 steps?

I assume what you mean by this is the following: is it undecidable whether an arbitrary TM halts after exactly 10 steps for some input? The answer is that, no, this is also decidable. Consider all $\Sigma^{10}$ configurations of the first $10$ cells of the tape. For each of these, configurations, execute 10 steps according to the TM's transition table (for nondeterministic TMs, this includes all possible paths of length 10). If one of the paths halts after exactly 10 steps, output yes; otherwise, output no.

(1.3) Is it undecidable whether an arbitrary TM ever prints a specific letter?

This one is actually undecidable. Suppose it weren't undecidable. Take an arbitrary TM. Construct a new TM with a new alphabet symbol not in the alphabet of the original TM. Replace all transitions in the original TM which cause the machine to halt with transitions which cause the machine to halt and which write this new symbol to the tape. By the assumption, the problem of whether the new TM prints this specific symbol is decidable; however, solving this problem would give us a way to solve the halting problem for the original TM (since the new one printing the symbol would only occur if the original one halted). Since the halting problem is undecidable, we have a contradiction, hence, this problem is undecidable.

(1.4) Is it undecidable whether an arbitrary TM accepts a string w in 5 steps?

This is clearly decidable. Given a TM and a string, write the string on the tape and execute five steps of the TM according to its transition table.

Which one of the following is not decidable?

1. given a TM M, a string s and an integer k, M accepts s with k steps
2. equivalence of two given TMs
3. language accepted by a given DFSA(Deterministic finite state automata) is nonempty
4. language accepted by a CFG(Context free grammar) is nonempty

• (2.1.) is definitely decidable as per the argument in (1.4).
• (2.2.) is ambiguous; if we mean syntactically equivalent, then this should be decidable given a suitable encoding. If it means semantically equivalent, i.e., they decide/accept the same language, then this is definitely undecidable.
• (2.3.) is definitely decidable, since you can always minimize the DFA and see whether it's a single state with no accepting states.
• (2.4.) is definitely decidable. Begin marking symbols (terminal/nonterminal) if they lead to a string of only terminal symbols. First, mark all terminal symbols. Next, mark nonterminals which lead to a string of only nonterminals. Iteratively, mark unmarked nonterminals which lead to strings of terminals or already-marked nonterminals. Continue until you complete an iteration without marking any new nonterminals. If the start symbol is marked, then it leads to a string of terminals, which is a string generated by the grammar, so its language is non-empty. Otherwise, the start symbol doesn't lead to a string of all terminals, so its language is empty.

By process of elimination, the answer to question (2) must be (2.2) and the interpretation given to "equivalent" must be "decides/accepts the same language."

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/14498