Numbering Turing Programs

  • Thread starter jgens
  • Start date
  • #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 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?
 

Answers and Replies

Related Threads on Numbering Turing Programs

  • Last Post
Replies
4
Views
2K
  • Last Post
Replies
4
Views
3K
  • Last Post
Replies
9
Views
3K
Replies
0
Views
938
  • Last Post
Replies
5
Views
1K
Replies
1
Views
4K
Replies
6
Views
2K
Replies
0
Views
777
Z
  • Last Post
Replies
0
Views
1K
  • Last Post
Replies
4
Views
870
Top