Results 1 to 4 of 4

Math Help - Numbering Turing Programs

  1. #1
    Newbie
    Joined
    Jan 2012
    Posts
    4

    Numbering Turing Programs

    Does this procedure give an effective way of assigning unique Godel numbers to Turing programs?

    Let p_i denote the ith prime number. Let Q = \{q_0,q_1,\dots\} 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(q_i)}p_2^{n(s)}p_3^{n(q_j)}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(L_1)}^{n(L_1)}\cdots p_{n(L_k)}^{n(L_k)}.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,537
    Thanks
    778

    Re: Numbering Turing Programs

    I believe this coding does assign unique numbers to programs, but it can be made more economical. First, you can encode a program \{L_1,\dots,L_n\} by p_{n(L_1)}\cdots p_{n(L_k)} (this allows unambiguous recovering of n(L_1),\dots,n(L_n)). Also, instead of n(B) = p_1, n(1) = p_2, ..., n(q_k) = p_{k+5} you can have n(B) = 1, n(1) = 2, ..., n(q_k) = k+5.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Jan 2012
    Posts
    4

    Re: Numbering Turing Programs

    So when we are assigning a Godel numbering to the Turing program, the only important thing is that each program be assigned a unique natural number, correct? My text is really vauge on this point, so I was uncertain whether each symbol, formula, etc. needed a unique Godel number.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,537
    Thanks
    778

    Re: Numbering Turing Programs

    We need two facts: (1) each program is assigned a unique natural number and (2) we can determine the same properties given a program and given its number. The first fact is well-defined mathematically while the second is not. We have intuition about what a computer can find out about a Turing machine (TM): e.g., it can find the number of characters and instructions, run it for 100 steps to see if it stops, determine if it loops within the first 10^5 steps, etc. However, we don't have a mathematical definition of a computer yet; that's why we are working with TMs to begin with, and TMs work with numbers, or, rather, with two-character strings. Therefore, we have to encode a machine as such a string, but we want another machine to be able to discover all facts starting from this string code that our intuition says a computer is able to discover about the original TM. In other words, a TM as a sequence of instructions, i.e., tuples (q_i,s,q_j,s',X), must contain the same information as its two-character encoding. This claim is not a theorem; rather, it is the idea behind the definition of the encoding. Note that (1) above is, in fact, a consequence of (2).

    To get an example of a bad encoding, consider an injection f:\mathbb{N}^5\to\mathbb{N} whose inverse is not computable and encode instructions (q_i,s,q_j,s',X) as f({n(q_i)},{n(s)},{n(q_j)},{n(s')},{n(X)}). Then another TM would not be able to parse such instructions and, therefore, determine the run-time properties of the TM. So, we can extract fewer properties from the code than from the original TM. For another example, let \mathop{\mbox{halt}}(P)=1 if a TM P stops on the empty tape and \mathop{\mbox{halt}}(P)=0 otherwise. Then let n'(P)=p_1^{n(P)}p_2^{\mathop{\text{halt}}(P))} where n(P) is your encoding. Now, we can get more information from encodings than from TMs: we can find out if they halt, which is impossible (halting problem).

    Ideally, instead of TMs we should have a model of computation that works not with binary strings but with arbitrary datatypes (lists, trees, etc.). Then we could feed TMs as input to other TMs directly, without encoding through prime numbers and so on.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Godel Numbering
    Posted in the Number Theory Forum
    Replies: 6
    Last Post: February 24th 2011, 12:26 PM
  2. Equation numbering
    Posted in the LaTeX Help Forum
    Replies: 0
    Last Post: April 24th 2010, 12:53 AM
  3. Numbering within chapters
    Posted in the LaTeX Help Forum
    Replies: 7
    Last Post: March 7th 2010, 05:35 PM
  4. Godel Numbering
    Posted in the Advanced Math Topics Forum
    Replies: 3
    Last Post: January 16th 2010, 01:06 AM
  5. page numbering
    Posted in the LaTeX Help Forum
    Replies: 0
    Last Post: October 24th 2008, 12:17 PM

Search Tags


/mathhelpforum @mathhelpforum