# Homework Help: Numbering Turing Programs

1. Jan 10, 2012

### jgens

1. The problem statement, all variables and given/known data

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

2. Relevant equations

N/A

3. The attempt at a solution

Let pi denote the ith prime number. Let Q = {q0,q1,...} 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) = p1, n(1) = p2, n(L) = p3, n(R) = p4, n(qk) = pk+5.

Now suppose L is a line of a Turing program P. Then L = (qi,s,qj,s',X) where s,s' in {B,1} and X in {L,R}. Assign a code number to L as follows: n(L) = p1n(qi)p2n(s)p3n(qj)p4n(s')p5n(X).

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

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

Does this work?