Search code examples
turing-machinesdecidableundecidable-instances

Turing machine decidability ambiguous cases


1) Is a Turing machine M that accepts the language L = {ε}, accepting no entry?

In one hand, I think it can be false because the empty word could be an entry, but in another i think this could possibly be an indecidable problem.

2) Is every Turing machine whose language is decidable stops on any input ?

Same idea, intuitively I would have say yes, due to the definition of decidable, but I don't know, something trouble me.

3) Is the language of the palindromes decidable whatever the aphabet ?

For this one, I have almost no doubt that it's False, because with Rice's Theorem we can prove that, this probleme is indecidable.


Solution

  • 1) I am not sure how to parse this but if a TM accepts the language consisting only of the empty set, it will eventually halt-accept on a blank tape. Whether that counts as an entry or not depends on your definition of "entry". I would count it as an entry, so I would answer "no".

    2) The language consisting of only the empty string is decidable. However, we can write a TM that halt-accepts the empty string only and goes into an infinite loop for all other inputs. What is meant by "whose language" is debatable but for TMs that encode partial functions I would call the language of that TM the set of strings which it halt-accepts on, so I would answer "no".

    3) It seems to me that, given an alphabet with n symbols, you can always construct a single-tape deterministic TM with O(n) states which halt-accepts on palindromes over that alphabet and halt-rejects other strings, thus deciding the language of palindromes over the alphabet. I would answer "yes", as long as the terms have their usual meanings. Note that Rice's theorem does not apply; it would apply to the problem of deciding whether a TM accepts the language of palindromes over an alphabet, but actually deciding whether something is a palindrome is of course possible (PDAs do it).