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?   Reply With Quote

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.  Reply With Quote

4.  Reply With Quote

5.  Reply With Quote

+ Reply to Thread Tags for this Thread

gödel, machine, number, table, turing  Posting Permissions

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