This question already has an answer here:

Let us define a Turing machine by a machine description that is a string of symbols produced by some numerical encoding. For example, a Turing machine $M_1$ can be represented by 9,900,599 ([0 0 halt], where halt = 5 and the start and end of an instruction is 99). A standard enumeration consists of all possible Turing machines.

If given a number $n$, is there a known algorithm out there for producing the $n$th Turing machine ($M_n$) in the standard enumeration?


marked as duplicate by Yuval Filmus algorithms Feb 5 '17 at 9:19

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.


Generate all strings in order, and keep track of which of them correspond to valid encodings. One you have seen the $n$th one, output it.

There are probably more efficient algorithms, but it depends on your exact encoding. Standard combinatorial enumeration techniques might suffice.


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