I may come across something like (let $X$ be a binary representation of a Turing machine $M$), I know that we can easily encode the description of the machine as sequence of numbers (by assigning a number to every symbol and arranging the description in some particular way) and then encoding this sequence by a single number (using prime numbers and powers as in Godel numbering) and then considering the binary representation of this number as the encoding of the machine, but such an encoding would be difficult to manipulate and use in say a simulation.

If we want to encode Turing machines in binary form so that we can use this encoding in a simulation, such encoding should be simple so that we can recover the instructions of machine easily for example, A pair $(q_7,x)$ would be represented as the binary number of 7 followed by some (binary) distinguished mark that indicates the end of the number that represents that state and then a representation of the symbol $x$ but I can not see how can we come with such a "mark" that do the job and guarantee unique readability.

So, suppose that we want to encode every pair $(p,q)$ of natural numbers in binary. Suppose that we will do that by exhibiting the binary representation of both p and q with a (binary) mark in-between, is there any trick that we can use to add this distinguished (binary) string that will tell us where the first number ended and where the second starts? If not, then How can we encode Turing machines in binary so that, we guarantee well-readability and we can "recover" the instructions of implementation easily.

  • 3
    $\begingroup$ Encode $0$ as $00$, $1$ as $01$, and 'break' as $10$. Optionally, encode 'end' as $11$. Of course, there are more space-efficient schemes, but this should be one of the simplest. Is this what you are looking for? $\endgroup$ Commented Aug 8, 2016 at 16:14
  • $\begingroup$ I think you are confusing "useful in proofs" and "useful in practice". Gödel numbers are not intended for use in actual machines; of course we'd use some readable language. $\endgroup$
    – Raphael
    Commented Aug 8, 2016 at 18:53
  • $\begingroup$ @Raphael, Ok but I don't see how a turing machine can simulate another turing machine if its representation was done using Godel numbering, of course I know it can be done (we can recover it easily by factoring the numbers in an appropriate way) but I can not see how can the Turing machine (not me) recover the instructions in this case. Of course we can argue that as there are an algorithm that recover the instructions from the encoding so by Church-Turing thesis we guarantee the existence of some Turing machine that do this, but I can not see how to program such a machine. $\endgroup$
    – FNH
    Commented Aug 9, 2016 at 4:17
  • $\begingroup$ @LieuweVinkhuijzen, Yes I think that this is good enough, thank you very much :) $\endgroup$
    – FNH
    Commented Aug 9, 2016 at 4:18
  • 1
    $\begingroup$ @MathsLover I don't understand your question. You know that there is an algorithm (Yes, Gödel numbers are reversibly computable), but you don't know how a TM would do it? Well, it'd just implement that algorithm. The details depend on the specific encoding and how you want to approach the simulation itself. $\endgroup$
    – Raphael
    Commented Aug 9, 2016 at 8:20


Your Answer

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