# Thread: Is this a Gödel number of a Turing machine?

1. Hey!!

We have the number \begin{align*}70&6737922567786324304462189150536772513339293263220644
\\ &=2^2\cdot 3\cdot 59^5\cdot 103\cdot 149^2\cdot 353\cdot 607\cdot 823^4\cdot 1409\cdot 1873^2\cdot 4201^3\end{align*}

I want to check if this is a Gödel number of a Turing machine.

From the prime factorization we have that $m=2$ and $k=1$.

The Gödel number is then of the form \begin{align*}G&=p_1^mp_2^k\prod_{i=1}^{(k+1)(m+1)}\prod_{j=3}^4p^{c_{ij}}_{\sigma_2(i,j)} \\ & = p_1^2p_2\prod_{i=1}^{2\cdot 3}\prod_{j=3}^4p^{c_{ij}}_{\sigma_2(i,j)} \\ & = p_1^2p_2\prod_{i=1}^6\prod_{j=3}^4p^{c_{ij}}_{\sigma_2(i,j)}\end{align*}

We have the following table:

$$(i,j) \ \ \ \sigma_2 \ \ \ P\sigma_2 \\ (1,3) \ \ \ 13 \ \ \ 41 \\ (1,4) \ \ \ 17 \ \ \ 59 \\ (2,3) \ \ \ 27 \ \ \ 103 \\ (2,4) \ \ \ 35 \ \ \ 149 \\ (3,3) \ \ \ 55 \ \ \ 257 \\ (3,4) \ \ \ 71 \ \ \ 353 \\ (4,3) \ \ \ 111 \ \ \ 607 \\ (4,4) \ \ \ 143 \ \ \ 823 \\ (5,3) \ \ \ 223 \ \ \ 1409 \\ (5,4) \ \ \ 287 \ \ \ 1873 \\ (6,3) \ \ \ 447 \ \ \ 3163 \\ (6,4) \ \ \ 575 \ \ \ 4201$$

All the prime numbers of the factorization are in the table. Does this mean that the given number is the Gödel number of a Turing machine? Or do we have to check also something else?

2.

3. Your question makes little sense to someone unfamiliar with how Turing machines are coded as numbers in your course. You probably realize that there are dozens of ways to do it. Even the table does not look as standard Turing machine instructions.

If this is a Gödel number, how can we determine the corresponding Turing table?

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•