7
$\begingroup$

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.

$\endgroup$
15
  • 1
    $\begingroup$ What have you tried? Please details your attempts, you will get better answers this way. $\endgroup$
    – Shaull
    Sep 21, 2013 at 16:03
  • 2
    $\begingroup$ Hint: A Universal Turing Machine can simulate any Turing Machine, whose states and transitions are encoded in a way that the Universal Turing Machine understands it. You can also modify it to keep track of how many steps you have made so far (even stop it right there). $\endgroup$
    – mdxn
    Sep 21, 2013 at 16:49
  • 1
    $\begingroup$ It would be polite to explain what "DFSA" and "CFG" stand for. Computer scientists are really infeceted with acronyms. $\endgroup$ Sep 21, 2013 at 17:08
  • $\begingroup$ @AndrejBauer Completely False. DFSA = Deterministic Finite State Automata (I have usually seen this written as DFA). CFG = Context Free Grammar. You would see these in any Theory of Computation course. Just about every complexity class is an acronym (P, NP, PSPACE). Just about every language/problem is an acronym (SAT, HALT). This is not just limited to theory, but many of the applied CS fields too. The acronyms are very well known and many are (roughly) consistent between texts. $\endgroup$
    – mdxn
    Sep 21, 2013 at 17:13
  • 1
    $\begingroup$ I could guess CFG but I expected DFA instead of DFSA. My point is that it is not so hard to write out the whole phrases, especially when you use them only a couple of times. $\endgroup$ Sep 21, 2013 at 17:38

1 Answer 1

17
$\begingroup$

(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."

$\endgroup$
7
  • 2
    $\begingroup$ We don't normally give full answers to homework questions. $\endgroup$ Sep 27, 2013 at 21:39
  • 2
    $\begingroup$ @DavidRicherby Sorry, whom do you mean by "we"? I've typically not given a lot of thought to whether a question is a homework question or not; although, somewhat begrudgingly, I've accepted the community's decision that requests for hints should be honored. $\endgroup$
    – Patrick87
    Sep 27, 2013 at 21:43
  • 1
    $\begingroup$ We, the users of the site in general, along the lines of the homework policy. $\endgroup$ Sep 27, 2013 at 23:36
  • 6
    $\begingroup$ @DavidRicherby Sorry, are we reading the same policy? The policy that I see in the link says that we don't play the game of deciding which questions are and aren't homework, and only need to provide hints upon request. Perhaps I'm missing something, but I don't see anything about homework or hints in the question. $\endgroup$
    – Patrick87
    Sep 30, 2013 at 14:54
  • $\begingroup$ @Patrick87 What I interpreted from your answer 1.2 is that "Just run the $TM$ for $N$ steps using dovetailing on all the inputs of length $N$, and when the $N$ steps are done, now stop and check the status of $TM$ on the given input . If $TM$ halted then say yes and if not halted then say no ". Is this interpretation fine or any chances of improvement ? $\endgroup$
    – Garrick
    Jul 24, 2017 at 2:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.