[Solved]: Decide if a specific Turing machine halts on a specific string

Problem Detail: 

Can you always decide if a specific Turing machine accepts a specific string?

I started thinking about this after reading an answer to this question, Rice's theorem vs Turing completeness, which seams to you can.

If this is true, intuitively, it seams it would be implied that HALT could be decided, which is obviously not true. Otherwise what is the difference?

Asked By : tAllan

Answered By : Kurt Mueller

The problem you are referring to is sometimes known as the Acceptance problem. It is indeed undecidable.

Let me attempt to find the source of your confusion. I assume by linking the other thread you are referring to the following decidable language:

$$ L_{HP-M'-x} = \begin{cases} 1 & \text{M' halts on x} \\ 0 & \text{otherwise} \end{cases} $$

The reason this language is decidable is because, given any $M'$ and $x$, this language must be either $\{1\}$ or $\{0\}$. In particular, this MUST be a finite language, and ALL finite languages are decidable.

Note that this doesn't mean we can solve the Acceptance problem. Using classical logic, we deduce that either a machine accepts a string or it does not. The hard part is figuring out which case it is! We know that the language is decidable, but we do not know what a machine that accepts this language looks like because we don't know what the language itself looks like.

Best Answer from StackOverflow

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

3.2K people like this

 Download Related Notes/Documents