Facebook Page
Twitter
RSS
+ Reply to Thread
Results 1 to 4 of 4
  1. MHB Master
    MHB Site Helper
    mathmari's Avatar
    Status
    Offline
    Join Date
    Apr 2013
    Posts
    3,546
    Thanks
    2,835 times
    Thanked
    917 times
    Awards
    MHB Model User Award (2017)  

MHB Chat Room Award (2015)  

MHB Model User Award (2015)  

MHB LaTeX Award (2015)
    #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. # ADS
    Circuit advertisement
    Join Date
    Always
    Posts
    Many
     

  3. MHB Master
    MHB Site Helper
    MHB Math Scholar

    Status
    Offline
    Join Date
    Jan 2012
    Posts
    2,467
    Thanks
    531 times
    Thanked
    4,393 times
    Thank/Post
    1.781
    Awards
    MHB University Math Award (2018)  

MHB Humor Award (2017)  

MHB Discrete Mathematics Award (2017)  

MHB Chat Room Award (2016)  

MHB Humor Award (2016)
    #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.

  4. MHB Master
    MHB Site Helper
    mathmari's Avatar
    Status
    Offline
    Join Date
    Apr 2013
    Posts
    3,546
    Thanks
    2,835 times
    Thanked
    917 times
    Awards
    MHB Model User Award (2017)  

MHB Chat Room Award (2015)  

MHB Model User Award (2015)  

MHB LaTeX Award (2015)

  5. MHB Master
    MHB Site Helper
    mathmari's Avatar
    Status
    Offline
    Join Date
    Apr 2013
    Posts
    3,546
    Thanks
    2,835 times
    Thanked
    917 times
    Awards
    MHB Model User Award (2017)  

MHB Chat Room Award (2015)  

MHB Model User Award (2015)  

MHB LaTeX Award (2015)
    #4 Thread Author
    If this is a Gödel number, how can we determine the corresponding Turing table?

Similar Threads

  1. (un)Modified Turing Machine
    By mathmari in forum Computer Science
    Replies: 24
    Last Post: Today, 12:44
  2. Find the turing machine
    By evinda in forum Discrete Mathematics, Set Theory, and Logic
    Replies: 0
    Last Post: February 1st, 2017, 15:13
  3. Describe the Turing machine
    By mathmari in forum Discrete Mathematics, Set Theory, and Logic
    Replies: 1
    Last Post: August 13th, 2016, 18:10
  4. Sets - Turing machine
    By mathmari in forum Computer Science
    Replies: 4
    Last Post: June 26th, 2015, 20:25
  5. Relationship between the Turing Machine and RAM Models
    By mathmari in forum Computer Science
    Replies: 0
    Last Post: November 19th, 2014, 21:31

Tags for this Thread

Posting Permissions

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