The confusing part is, that $M$ basically is simulated on its own encoding $\langle M\rangle$. Nevertheless, I would claim its decidable by simply creating the following $TM$ $T$:

check if $\langle M\rangle$ is correctly encoded
Build a $TM$ $M$ with input $\langle M\rangle$
Simulate $M$ on $\langle M\rangle$ for $32$ steps
if $M$ halts, $T$ accepts, otherwise $T$ rejects.

This is totally straightforward, thus I am quite unsure. Any hint is highly appreciated!

  • 2
    $\begingroup$ this looks correct $\endgroup$
    – nir shahar
    Jun 28 at 13:07

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.