I am working through a computability theory textbook and right now the author is discussing assigning Godel numbers to each Turing Program. To do this, he suggests assigning each internal state, each of the elements of {1,B} and each of the elements of {L,R} a number. Then using these numbers, we can construct a unique Godel number for every line of a Turing program. Then using the numbering of these lines, we can assign a Godel number to the Turing programs themselves.(adsbygoogle = window.adsbygoogle || []).push({});

My question is this: When assigning Godel numbers for the Turing programs, do we need to make sure that they are distinct from the numbers assigned to the internal states or lines for instance? We only seem to use the numbering to create an effectively computable listing of Turing programs, so it seems like this should be fine. But I am unsure if there are other reasons why this will not work.

Thanks!

**Physics Forums | Science Articles, Homework Help, Discussion**

Dismiss Notice

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Godel Numbers

**Physics Forums | Science Articles, Homework Help, Discussion**