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.)

 

[blue_raver22]

I can confirm that assigning Godel numbers to Turing programs is a valid and useful method for creating an effectively computable listing of these programs. The process of assigning numbers to internal states, elements, and lines is a common technique in computability theory and is used to represent complex systems in a more manageable way. In this case, assigning Godel numbers to each line of a Turing program allows us to easily identify and distinguish between different programs, making it easier to analyze and compare their properties.

To answer your question, it is important to ensure that the Godel numbers assigned to Turing programs are distinct from the numbers assigned to internal states and lines. This is because the Godel number of a program is used to uniquely identify and represent that specific program. If the numbers were not distinct, it would lead to confusion and make it difficult to accurately represent and analyze the programs. Additionally, it is important to note that the process of assigning Godel numbers is not limited to just Turing programs, but can also be applied to other computational systems as well.

In conclusion, assigning Godel numbers to Turing programs is a valid and effective method for creating an effectively computable listing. It is important to ensure that the numbers assigned are distinct in order to accurately represent and analyze the programs. This technique is widely used in computability theory and has proven to be a valuable tool in understanding the properties and behaviors of complex systems.