I am creating a two-tape Turing machine to recognize the language $\{0^{2^n}|n\geq 0\}$. My idea is to put an input string, such as 0000, at the first tape, and use the second one to count the number of 0s in binary form (as a suggestion at A two-tape deterministic Turing machine that recognizes an exponential string). Every time Turing machine read a single 0, increase the counter (on the second tape) by 1. My difficulty is to write clearly the transition function, namely $\delta$, such as, I don't know how many states this Turing machine should have.

  • 1
    $\begingroup$ Are you supposed to give $\delta$ and the TM states explicitly? Usually, a precise description (in prose) suffices. $\endgroup$
    – dkaeae
    Commented Dec 30, 2018 at 13:23
  • $\begingroup$ Well, you decide how many states the machine needs. Enough states to remember what it is supposed to be doing. $\endgroup$ Commented Dec 30, 2018 at 15:04


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.