1
$\begingroup$

If we have a Turing machine with various $\delta(q_i, a_i) = (q_j, a_j, Direction)$ where Direction can be L or R(denoting the movement of head), can we encode it uniquely to some natural number(which can later be decoded to give us back the deltas) ? It doesn't matter if all the natural numbers map one-to-one to all the Turing machines.

$\endgroup$
2
$\begingroup$

Sure. Any Turing machine can be represented as a bit string (print out the description of the Turing machine). Any bit string can be encoded as a natural number (prepend a 1 bit, and view it as a binary representation of a number).

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I read the description number of Turing machine, it answered my query. Thank you! $\endgroup$ – user120215 May 8 at 4:41

Your Answer

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