2
$\begingroup$

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?

$\endgroup$
5
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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