Is this a Gödel number of a Turing machine?

In summary, the conversation discusses the possibility of a given number being a Gödel number of a Turing machine. It provides the prime factorization of the number and a table showing the corresponding prime numbers. However, the conversation also mentions that there are multiple ways to code Turing machines as numbers and questions how to determine the corresponding Turing table.
  • #1
mathmari
Gold Member
MHB
5,049
7
Hey! :eek:

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)
 
Technology news on Phys.org
  • #2
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.
 
  • #3

Attachments

  • GN1.jpg
    GN1.jpg
    37.2 KB · Views: 96
  • GN2.jpg
    GN2.jpg
    34.1 KB · Views: 95
  • #4
If this is a Gödel number, how can we determine the corresponding Turing table? (Wondering)
 

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

1. What is a Gödel number of a Turing machine?

A Gödel number of a Turing machine is a unique numerical representation of a specific Turing machine, named after mathematician Kurt Gödel. It is used in the field of computability theory to analyze and compare different Turing machines.

2. How is a Gödel number of a Turing machine calculated?

A Gödel number is calculated by assigning a unique prime number to each symbol and state of a Turing machine's transition function. These prime numbers are then multiplied together to form a single number that represents the entire machine.

3. Why is the concept of Gödel numbers important in computability theory?

Gödel numbers allow for a compact and efficient way to represent and compare Turing machines, which are the foundation of theoretical computer science. They also help to prove the undecidability of certain problems and provide insights into the limits of computation.

4. Can any Turing machine have a Gödel number?

Yes, any Turing machine can have a Gödel number assigned to it, as long as it follows the rules for calculating the number. However, some Turing machines may have the same Gödel number, as there are an infinite number of possible machines but a finite number of prime numbers.

5. How are Gödel numbers used in the study of computability?

Gödel numbers are used to prove the existence of undecidable problems, meaning there are certain questions that cannot be answered by a computer. They also help to define and classify different classes of problems based on their computability, such as recursively enumerable or recursive problems.

Similar threads

Replies
1
Views
1K
Replies
1
Views
1K
Replies
6
Views
2K
Replies
3
Views
1K
6
Replies
175
Views
22K
Back
Top