A community for students.

Here's the question you clicked on:

55 members online
  • 0 replying
  • 0 viewing

dan815

  • one year ago

Turing Machine

  • This Question is Closed
  1. dan815
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    |dw:1444363880290:dw|

  2. dan815
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    so basically turing came up with this idea for a computer

  3. dan815
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    Now the theorem is that, any intuitive thing you can think of doing, can be formulated into steps, or an algorithm for this "computer"

  4. dan815
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    That shouldnt really say readstate, its not reading state, think about it like the machine knows the state its in, or some person or thing is there to change the state, so the machine is in a current state, no based on what it reads or doesnt read in the strip, you can make it change state or do other stuff

  5. dan815
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    i can give u some example or you can try a fun excercise

  6. Kainui
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    Sure sounds fun

  7. dan815
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    okay let me give u some example first, so u can play this game right

  8. dan815
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    Lets say our strip is loaded with 0s everywhere to begin with |dw:1444364282679:dw|

  9. dan815
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    The main thing to get from that example is how these steps are being used

  10. dan815
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    this program is not technically "complete" because we left some cases out like (s2,1,....) (s3,1,....) the cases where its in this state and reads a 1 in the strip, which we know wont happen since we decided this stips starting condition was all 0

  11. Kainui
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    Ok I think I'm following so far.

  12. dan815
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    okay now the turing theory is that, anything you can possibly think of, can be done with just what u have already

  13. dan815
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    a fun problem to throw you into this mess is

  14. dan815
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    suppose I give you a strip, that has a "number" somewhere in the stip, lets say there are n, 1s, side by side, and everything else is a 0, what is one way, you can write an algorithm that will always find this number

  15. dan815
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    wait before that start with this,

  16. dan815
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    |dw:1444364919462:dw|

  17. Kainui
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    since it's an infinite strip I guess I have to zig zag back and forth until I find it

  18. dan815
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    yeah exactly

  19. dan815
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    try to do that left most strip problem, i want to make sure u get how to write the steps

  20. dan815
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    the halting state is S0 state, that marks the end of all computation

  21. Kainui
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    |dw:1444365057431:dw|

  22. dan815
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    |dw:1444365079498:dw|

  23. dan815
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    after some program, u want to leave the strip as it is, and get that pointer/ reader to the left most 1 in the strip

  24. dan815
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    ill just get u started i think u need to see an example atleast

  25. Kainui
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    No what's that word say "will en--" got cut off

  26. dan815
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    |dw:1444365168395:dw|

  27. dan815
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    oh my bad okay

  28. dan815
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    okay but do u get this example, u dont need to think about htis really, i want to make sure u understand rules

  29. dan815
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    that first line is enough to cover everything that happens when it reads s1,1

  30. dan815
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    this only works for the scneario that your reader is already somewhere in a list of 1s

  31. Kainui
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    Yeah I was working on it I am not clear on the rules yet but I see you put it, I'll pretend I didn't see it: (S1,1,S1,1,L) (S1,0,S0,?,?)

  32. dan815
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    you have to make sure that direction is R on the 2nd step

  33. dan815
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    and leave the 0 as 0 , so the strip is unchanged

  34. Kainui
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    Won't that make it off by one? like it'll be |dw:1444365416912:dw|

  35. Kainui
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    Since we moved right

  36. dan815
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    the 2nd line of code basically means u were |dw:1444365428897:dw|

  37. dan815
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    the 2nd line* is triggered once you are the 0 so u are fine

  38. dan815
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    we should be in a call right now xD why are even wasting out time typing all this lol

  39. Kainui
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    Ok so let me explain this if I have it correctly: (s1,1,s1,1,L) This means this is what you do when s1 is 'called' by the third yeah true

  40. dan815
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    okay so basically that line you wrote (s1,1,s1,1,L) is saying if you in state s1, and read 1 in that box, stay s1, leave box 1, and go left 1 space

  41. dan815
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    as soon as it goes to the left spot, the reader will read again, and see what state u are in, and continue the process

  42. Kainui
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    \[(S_{2n-1},1,S_{2n},1,L)\]\[(S_{2n-1},0,S_0,0,R)\]\[(S_{2n},1,S_{2n+1},1,R)\]\[(S_{2n},0,S_0,0,L)\]

  43. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    can you put 5 heads and get it done at one go avoiding backtracking ?

  44. dan815
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    only 1 reader fort now :)

  45. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    you can convert that state machine to turing program easily

  46. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    ** |dw:1444367192800:dw|

  47. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    basically, the statemachine resets everytime it sees a 0

  48. dan815
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    can u write out your program in that 5 step rule

  49. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    |dw:1444367429426:dw|

  50. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    your states correspond to above, right ?

  51. dan815
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    okay i can kind of see what ua re doing

  52. dan815
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    yeah, like if u are in a state, and u see a 1 or 2 u can change state or loop back to same stape and so on

  53. dan815
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    those kind of drawings could be useful actually in just come up with some idea to do, before writing al gorithm

  54. dan815
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    like for example if i were to use your drawings to make this left most finding 1 problem it would look like --->

  55. dan815
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    |dw:1444367903673:dw|

  56. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    To identify the pattern 01111 w/o backtracking : ``` (START,0,s1,0,R) (s1, 0, s1, 0, R) (s1, 1, s2, 0, R) (s2, 0, s1, 0, R) (s2, 1, s3, 0, R) (s3, 0, s1, 0, R) (s3, 1, s4, 0, R) (s4, 0, s1, 0, R) (s4, 1, END, 0, R) ```

  57. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    because the turing machine has state knowledge, it never has to backtrack

  58. dan815
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    okay so can you tell me which problem you are trying to solve ganeshie

  59. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    to identify the pattern 01111 on a sequential line using turing machine

  60. Kainui
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    (S1,0,S1,0,R) (S1,1,S2,0,R) (S2,0,S3,1,L) (S2,1,S0,1,L) (S3,0,S3,0,L) (S3,1,S4,0,L) (S4,0,S1,0,R) (S4,1,S0,1,R)

  61. dan815
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    but remember this is an infnite strip ganeshie, you dont knwo if ur 1s are on the left or right

  62. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    How does that matter if the turing maching is keeping track of the state that is in

  63. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    s1, s2, s3, s4, s5 correspond to specific states that give us the information about what state we are in finding the pattern, right ?

  64. dan815
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    are you currently just going only right ganeshie

  65. Kainui
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    |dw:1444368331824:dw|

  66. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    Yes, only forward...

  67. dan815
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    you have to make sure you find your number even if its in infinite time, just gotta make sure ur program is complete, right now you program has a flaw that if the number is to the left then you would be lost

  68. dan815
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    the idea is that this is an infinite strip and u are somewhere lost on this strip, and u have to find a the 1s

  69. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    I am assuming we have reset thingy and the tape has a well defined start point

  70. dan815
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    no reset thing xD

  71. dan815
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    there is the halting state which just stops, and move the reader to the left or right before it does so, thats about it

  72. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    so the tape starts somewhere in the middle and the pattern we want to find "can" be to the either left or right is it ? so there is no "start point" for the tape ?

  73. dan815
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    nope

  74. dan815
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    i mean your reader is somewhere we dont know where it is, we just know its somewhere

  75. dan815
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    jut some infinite line

  76. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    Okay the previous statemaching works just fine, I just need to add what happens when it encounters "1", one sec...

  77. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    If the current value is 0, it can simply move forward, no need to backtrack, agree ? |dw:1444368962345:dw|

  78. Kainui
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    |dw:1444369006730:dw|

  79. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    Because, we're trying to find the pattern "01111", and, if the current value is 0, we know for sure what the next state will be

  80. dan815
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    you gotta find a way to do that zigzag thign in the above pic

  81. dan815
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    we have to back and forth

  82. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    we have to back and forth only if the current value is 1 when we start

  83. dan815
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    if u start on a 1, u are pretty much done, you will just go back until you go to the left most 1 and u found the start of your number sequence

  84. dan815
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    the whhole problem is 0 0000000001111111000000000 you dont know if ur in the 0s on the left or the right

  85. dan815
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    ...0000001111110000......

  86. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    if you start at 1, you don't know what the next state will be

  87. Kainui
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    Start at S5 heh (S5,0,S6,0,L) (S6,0,S7,0,L) (S7,0,S1,1,L) (S6,1,S0,1,R) (S7,1,S0,1,R) (S1,0,S1,0,R) (S1,1,S2,0,R) (S2,0,S3,1,L) (S2,1,S0,1,L) (S3,0,S3,0,L) (S3,1,S4,0,L) (S4,0,S1,0,R) (S4,1,S0,1,R)

  88. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    `01111` it could be the first, second, third or fourth 1

  89. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    however if the head reads 0 as its starting value, you always know that the next state is s1 it moves forward and looks for 1 next, if it doesn't find 1 there, it goes back to the state s1

  90. dan815
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    oh i see i think u are misunderstading what a state is

  91. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    enlighten me then

  92. dan815
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    a state has nothing to do with where your reader is or how your strip is right now or anything

  93. Kainui
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    Start at S5 heh (S5,0,S6,0,L) (S6,0,S7,0,L) (S7,0,S1,1,R) (S6,1,S0,1,R) (S7,1,S0,1,R) (S1,0,S1,0,R) (S1,1,S2,0,R) (S2,0,S3,1,L) (S2,1,S0,1,L) (S3,0,S3,0,L) (S3,1,S4,0,L) (S4,0,S1,1,R) (S4,1,S0,1,R) |dw:1444369525101:dw|

  94. dan815
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    its just this like variable you are using to keep track of what command u want to do right now

  95. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    are you defining own terminology here ? because thats not how i remember using it..

  96. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    consider the state diagram of a simpler circuit, mod10 counter or something, how do you define a state in this ?

  97. dan815
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    http://prntscr.com/8pcu8g

  98. dan815
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    |dw:1444369816762:dw|

  99. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    don't take me seriosuly though, i could be wrong... its been so many years...

  100. dan815
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    |dw:1444369924025:dw|

  101. dan815
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    |dw:1444369944055:dw|

  102. dan815
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    https://ms.mcmaster.ca/~speisseg/blog/?page_id=2731

  103. dan815
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    |dw:1444370662565:dw|

  104. Not the answer you are looking for?
    Search for more explanations.

    • Attachments:

Ask your own question

Sign Up
Find more explanations on OpenStudy
Privacy Policy

Your question is ready. Sign up for free to start getting answers.

spraguer (Moderator)
5 → View Detailed Profile

is replying to Can someone tell me what button the professor is hitting...

23

  • Teamwork 19 Teammate
  • Problem Solving 19 Hero
  • You have blocked this person.
  • ✔ You're a fan Checking fan status...

Thanks for being so helpful in mathematics. If you are getting quality help, make sure you spread the word about OpenStudy.

This is the testimonial you wrote.
You haven't written a testimonial for Owlfred.