
MHB Master
#1
October 9th, 2019,
14:46
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?

October 9th, 2019 14:46
# ADS
Circuit advertisement

#2
October 9th, 2019,
15:23
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.

MHB Master
#3
October 9th, 2019,
15:35
Thread Author
Here are some notes (in german) that I am looking at:

MHB Master
#4
October 10th, 2019,
15:41
Thread Author
If this is a Gödel number, how can we determine the corresponding Turing table?