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 Dec 30 '18 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$ – Hendrik Jan Dec 30 '18 at 15:04

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.