0
$\begingroup$

I am a bit confused about using the subset of the turning machine to prove the desirability of the turning machine.

If I have a Turing Machine M and we have already know M has a single halting state. If we already the machine takes a string was the input and reaches to the state q0, is it possible to prove that M is decidable by considering constructing a new Turing Machine that halts on q0?

Thanks a lot!

$\endgroup$
  • $\begingroup$ I’m not sure what you are asking... but read Rice Theorem: all non trivial property (semantic) of TM are undecidable. $\endgroup$ – prime_hit May 23 at 5:43
  • $\begingroup$ (I am a bit confused about the syntax of the first two sentences in the second paragraph - we have already know and If we already the machine takes a string was the input: please check and improve/simplify.) $\endgroup$ – greybeard May 23 at 10:48

Your Answer

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

Browse other questions tagged or ask your own question.