- #1

jgens

Gold Member

- 1,581

- 50

## 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

_{0},q

_{1},...} 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

_{1}, n(1) = p

_{2}, n(L) = p

_{3}, n(R) = p

_{4}, 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

_{1}

^{n(qi)}p

_{2}

^{n(s)}p

_{3}

^{n(qj)}p

_{4}

^{n(s')}p

_{5}

^{n(X)}.

Lastly suppose that P = {L

_{1},...,L

_{k}} is a Turing program. Assign a code number to P as follows: n(P) = p

_{n(L1)}

^{n(L1)}...p

_{n(Lk)}

^{n(Lk)}.

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

Does this work?