Numbering Turing Programs

[jgens]

Homework Statement

Assign a code number n(P) to every Turing program P.

Homework Equations

N/A

The Attempt at a Solution

Let p_i denote the ith prime number. Let Q = {q₀,q₁,...} be internal states, let {B,1} denote tape symbols and let {L,R} denote direction symbols. Assign a code number to each of these symbols as follows: n(B) = p₁, n(1) = p₂, n(L) = p₃, n(R) = p₄, n(q_k) = p_k+5.

Now suppose L is a line of a Turing program P. Then L = (q_i,s,q_j,s',X) where s,s' in {B,1} and X in {L,R}. Assign a code number to L as follows: n(L) = p₁^n(q_i)p₂^n(s)p₃^n(q_j)p₄^n(s')p₅^n(X).

Lastly suppose that P = {L₁,...,L_k} is a Turing program. Assign a code number to P as follows: n(P) = p_n(L1)^n(L₁)...p_n(Lk)^n(L_k).

This assigns each syntactic object we consider to a unique natural number. Moreover, this assignment is effective.

Does this work?

 

[mighty2000]

Yes, this method of assigning code numbers to Turing programs is effective and will result in a unique code number for each program. This is because each symbol and line of the program is assigned a unique prime number, and the code number for the entire program is then computed by multiplying these prime numbers together. This ensures that no two programs will have the same code number, as the prime factorization of each code number will be unique. Additionally, this method allows for easy retrieval of a Turing program from its code number, making it a useful tool for organizing and categorizing programs.