I am trying to interpret the following problem:

"Describe an algorithm for a Turing machine which receives the integer n as input and proceeds to write the description of the n-th Turing machine from the standard enumeration on its tape."

I am confused about how a Turing machine itself can represent another Turing machine (the n-th Turing machine).


The question is probably assuming that there is some arbitrary but agreed-upon convention that specifies how to write a Turing machine description with the symbols of some alphabet. Since all Turing machines have by definition a finite description, all valid outputs will be finite strings.

The exercise itself is an ordinary combinatorics problem.

| cite | improve this answer | |

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.