- #1

mathmari

Gold Member

MHB

- 5,049

- 7

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? (Wondering)