Assigning Godel Numbers to Turing Programs

[jgens]

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.

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!

 

[aravantv]

Not sure this is really needed to answer your question, but what do you call a "line" in a Turing program? Actually how do you define a Turing program? (I never saw the expression "Turing program"; "Turing machine" ok, but "Turing program" never; is it different?) What is B in your statement?

Then could you clarify your question: you want to know if there should not be any number which is both the number of a Turing program and the number of a line?

 

[dvdl]

Godel numbering is essentially the creation of an injective function from one set to the natural numbers.

The method Godel used was in reference to symbols, formulae, (and proof schemata) in a first order formal system.

Basically the formal language consists of a set of symbols, say {a, b, c}.

And sequences of these symbols, e.g. abba, ccccc, a, cba etc.

(And sequences of sequences of symbols.)

The Godel numbering method used in his 1930 paper is:

1) to assign a natural to each symbol. i.e. a≈1, b≈2, c≈3

2) for each sequence of symbols, take the first prime number and raise it to the power of the natural number related to that symbol; take the second prime number and raise it to the power of the natural number related to that symbol, and on and on, and then multiply these together.

e.g. for aba, the corresponding Godel number is (2^1)x(3^2)x(5^1)=2x9x5=90

By the fundamental theorem of arithmetic, this method is injective; that is, there is a unique (different) Godel number for each and every two sequences of symbols.

Godel also allowed for variables in his formulation. In this case if you are using n variable, call them x1, x2, ... , xn, then assign to each of these the number 5 to the power of the variable number, so that xj≈5^j.Then for the sequence abx1, the corresponding Godel number is (2^1)x(3^2)x(5^(5^1))=2x9x(5^5)=...

I don't understand the terminology you are using. But this is the basic method. I hope it helps.

 

[funkstar]

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?

You don't. As you mention, all that matters is that each program, or machine, can be encoded by a distinct integer.

In computability theory, the exact Gödel numbering isn't particularly important, it's much more the concept itself that matters.

(Notice the umlaut over the 'o' i Gödel, btw.)