u/white_nerdy

The most obvious way to encode a length-N string of M possible symbols as an integer is to just make them the digits of an N-digit number in base M. E.g. if you have 10 possible symbols the string [3, 1, 4, 1, 5, 9] would be encoded as the (base-ten) integer 314159 (or maybe 951413). Is there a specific reason Godel numbering is easier to work with in the context of proving the incompleteness theorems? Or is it just the numbering Godel happened to pick in a pre-Turing pre-Shannon world? How hard would it be to prove incompleteness using the "obvious" encoding instead?