Facebook Page
Twitter
RSS
+ Reply to Thread
Page 3 of 3 FirstFirst 123
Results 21 to 25 of 25
  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)
    #21 Thread Author
    Quote Originally Posted by Klaas van Aarsen View Post
    Perhaps the context of the problem defines its Ordinary Turing Machine such that every state - that is not a final state - must have a state transition for all inputs...
    After all, we already now that what the problem considers an 'ordinary Turing Machine' is not the definition that wiki gives.

    Or perhaps those steps are indeed redundant...
    We have the following definition for the transformation:



    Do we have those steps maybe because of the last part of that definition?

  2. # ADS
    Circuit advertisement
    Join Date
    Always
    Posts
    Many
     

  3. MHB Seeker
    MHB Global Moderator
    MHB Math Scholar
    MHB Coder
    Klaas van Aarsen's Avatar
    Status
    Offline
    Join Date
    Mar 2012
    Location
    Leiden
    Posts
    8,102
    Thanks
    5,321 times
    Thanked
    14,342 times
    Thank/Post
    1.770
    Awards
    MHB Pre-University Math Award (2018)  

MHB Model Helper Award (2017)  

MHB Best Ideas (2017)  

MHB Analysis Award (2017)  

MHB Calculus Award (2017)
    #22
    Quote Originally Posted by mathmari View Post
    We have the following definition for the transformation:

    Do we have those steps maybe because of the last part of that definition?
    That transformation converts the Modified Turing Machine into and Ordinary Turing Machine.

    First off, it shows that we will indeed have states with only 1 transition in the Ordinary Turing Machine.
    That is, the state transition from $s_1'$ to $s$ in the 2nd rule is only defined for the symbol $x'$ and not for any other symbol.

    The last part with $\delta(s,x)=\varnothing$ shows that if there are no state transitions at all in state $s$ of the Modified Turing Machine, that we transform it into a state that halts the Ordinary Turing Machine. It means that it is a final state.

  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)
    #23 Thread Author
    Quote Originally Posted by Klaas van Aarsen View Post
    That transformation converts the Modified Turing Machine into and Ordinary Turing Machine.

    First off, it shows that we will indeed have states with only 1 transition in the Ordinary Turing Machine.
    That is, the state transition from $s_1'$ to $s$ in the 2nd rule is only defined for the symbol $x'$ and not for any other symbol.

    The last part with $\delta(s,x)=\varnothing$ shows that if there are no state transitions at all in state $s$ of the Modified Turing Machine, that we transform it into a state that halts the Ordinary Turing Machine. It means that it is a final state.
    Is the third line at each step of the proposed solution at #16 justified by the above?

  5. MHB Seeker
    MHB Global Moderator
    MHB Math Scholar
    MHB Coder
    Klaas van Aarsen's Avatar
    Status
    Offline
    Join Date
    Mar 2012
    Location
    Leiden
    Posts
    8,102
    Thanks
    5,321 times
    Thanked
    14,342 times
    Thank/Post
    1.770
    Awards
    MHB Pre-University Math Award (2018)  

MHB Model Helper Award (2017)  

MHB Best Ideas (2017)  

MHB Analysis Award (2017)  

MHB Calculus Award (2017)
    #24
    Quote Originally Posted by mathmari View Post
    Is the third line at each step of the proposed solution at #16 justified by the above?
    No. It is not.
    The above specifies the single transition I suggested and leaves out that third line at each step.

  6. 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)
    #25 Thread Author
    Quote Originally Posted by Klaas van Aarsen View Post
    No. It is not.
    The above specifies the single transition I suggested and leaves out that third line at each step.
    At the given table of the modified TM of #1 do we not have $\delta (s_4 ,\sqcup )=\emptyset$ ?

    So according to the definition do we not get the following ordinary TM ?

    $(s_0,\sqcup,s_1,|,\ell)$ gets $(s_0,\sqcup,s_1',|), (s_1',\mid,s_1,\ell)$

    $(s_0,\mid,s_0,|,\ell)$ gets $(s_0,\mid,s_0',|), (s_0',\mid,s_0,\ell)$

    $(s_1,\sqcup,s_2,|,r)$ gets $(s_1,\sqcup,s_2',|), (s_2',\mid,s_2,r)$

    $(s_1,\mid,s_1,|,r)$ gets $(s_1,\mid,s_1'',|), (s_1'',\mid,s_1,r)$

    $(s_2,\sqcup,s_0,|,\ell)$ gets $(s_2,\sqcup,s_0'',|), (s_0'',\mid,s_0,\ell)$

    $(s_2,\mid,s_3,|,r)$ gets $(s_2,\mid,s_3',|), (s_3',\mid,s_3,r)$

    $(s_3,\sqcup,s_0,|,\ell)$ gets $(s_3,\sqcup,s_0''',|), (s_0''',\mid,s_0,\ell)$

    $(s_3,\mid,s_4,|,r)$ gets $(s_3,\mid,s_4',|), (s_4',\mid,s_4,r)$

    $(s_4,\mid,s_2,\sqcup,r)$ gets $(s_4,\mid,s_2'',\sqcup), (s_2'',\sqcup,s_2,r)$


    Now we have that \begin{align*}\delta (s_1', \sqcup)&=\delta (s_0', \sqcup)=\delta (s_2', \sqcup)=\delta (s_1'', \sqcup)=\delta (s_0'', \sqcup)\\ & =\delta (s_3', \sqcup)=\delta (s_0''', \sqcup)=\delta (s_4', \sqcup)=\delta (s_4, \sqcup)\\ & =\delta (s_2'', \mid)=\emptyset \end{align*} or not?


    So according to the last line of the definition we have to add for each of these ones an additional transition, which are the following:

    \begin{align*}&(s_1', \sqcup, s_1',h), \ (s_0', \sqcup, s_0', h), \ (s_2', \sqcup, s_2', h), \ (s_1'', \sqcup, s_1'', h), \ (s_0'', \sqcup, s_0'', h)\\ & (s_3', \sqcup, s_3', h), \ (s_0''', \sqcup, s_0''', h), \ (s_4', \sqcup, s_4', h), \ (s_4, \sqcup, s_4, h), \ (s_2'', \mid, s_2'', h) \end{align*}

    Or have I understood that wrong?
    Last edited by mathmari; Today at 18:10.

Similar Threads

  1. Find the turing machine
    By evinda in forum Discrete Mathematics, Set Theory, and Logic
    Replies: 0
    Last Post: February 1st, 2017, 15:13
  2. Describe the Turing machine
    By mathmari in forum Discrete Mathematics, Set Theory, and Logic
    Replies: 1
    Last Post: August 13th, 2016, 18:10
  3. Non-deterministic 2-tape Turing Machine
    By mathmari in forum Discrete Mathematics, Set Theory, and Logic
    Replies: 1
    Last Post: July 30th, 2016, 06:05
  4. Sets - Turing machine
    By mathmari in forum Computer Science
    Replies: 4
    Last Post: June 26th, 2015, 20:25

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