dan815
  • dan815
Turing Machine
Mathematics
  • Stacey Warren - Expert brainly.com
Hey! We 've verified this expert answer for you, click below to unlock the details :)
SOLVED
At vero eos et accusamus et iusto odio dignissimos ducimus qui blanditiis praesentium voluptatum deleniti atque corrupti quos dolores et quas molestias excepturi sint occaecati cupiditate non provident, similique sunt in culpa qui officia deserunt mollitia animi, id est laborum et dolorum fuga. Et harum quidem rerum facilis est et expedita distinctio. Nam libero tempore, cum soluta nobis est eligendi optio cumque nihil impedit quo minus id quod maxime placeat facere possimus, omnis voluptas assumenda est, omnis dolor repellendus. Itaque earum rerum hic tenetur a sapiente delectus, ut aut reiciendis voluptatibus maiores alias consequatur aut perferendis doloribus asperiores repellat.
jamiebookeater
  • jamiebookeater
I got my questions answered at brainly.com in under 10 minutes. Go to brainly.com now for free help!
dan815
  • dan815
|dw:1444363880290:dw|
dan815
  • dan815
so basically turing came up with this idea for a computer
dan815
  • dan815
Now the theorem is that, any intuitive thing you can think of doing, can be formulated into steps, or an algorithm for this "computer"

Looking for something else?

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

More answers

dan815
  • dan815
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
dan815
  • dan815
i can give u some example or you can try a fun excercise
Kainui
  • Kainui
Sure sounds fun
dan815
  • dan815
okay let me give u some example first, so u can play this game right
dan815
  • dan815
Lets say our strip is loaded with 0s everywhere to begin with |dw:1444364282679:dw|
dan815
  • dan815
The main thing to get from that example is how these steps are being used
dan815
  • dan815
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
Kainui
  • Kainui
Ok I think I'm following so far.
dan815
  • dan815
okay now the turing theory is that, anything you can possibly think of, can be done with just what u have already
dan815
  • dan815
a fun problem to throw you into this mess is
dan815
  • dan815
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
dan815
  • dan815
wait before that start with this,
dan815
  • dan815
|dw:1444364919462:dw|
Kainui
  • Kainui
since it's an infinite strip I guess I have to zig zag back and forth until I find it
dan815
  • dan815
yeah exactly
dan815
  • dan815
try to do that left most strip problem, i want to make sure u get how to write the steps
dan815
  • dan815
the halting state is S0 state, that marks the end of all computation
Kainui
  • Kainui
|dw:1444365057431:dw|
dan815
  • dan815
|dw:1444365079498:dw|
dan815
  • dan815
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
dan815
  • dan815
ill just get u started i think u need to see an example atleast
Kainui
  • Kainui
No what's that word say "will en--" got cut off
dan815
  • dan815
|dw:1444365168395:dw|
dan815
  • dan815
oh my bad okay
dan815
  • dan815
okay but do u get this example, u dont need to think about htis really, i want to make sure u understand rules
dan815
  • dan815
that first line is enough to cover everything that happens when it reads s1,1
dan815
  • dan815
this only works for the scneario that your reader is already somewhere in a list of 1s
Kainui
  • Kainui
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,?,?)
dan815
  • dan815
you have to make sure that direction is R on the 2nd step
dan815
  • dan815
and leave the 0 as 0 , so the strip is unchanged
Kainui
  • Kainui
Won't that make it off by one? like it'll be |dw:1444365416912:dw|
Kainui
  • Kainui
Since we moved right
dan815
  • dan815
the 2nd line of code basically means u were |dw:1444365428897:dw|
dan815
  • dan815
the 2nd line* is triggered once you are the 0 so u are fine
dan815
  • dan815
we should be in a call right now xD why are even wasting out time typing all this lol
Kainui
  • Kainui
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
dan815
  • dan815
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
dan815
  • dan815
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
Kainui
  • Kainui
\[(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)\]
ganeshie8
  • ganeshie8
can you put 5 heads and get it done at one go avoiding backtracking ?
dan815
  • dan815
only 1 reader fort now :)
ganeshie8
  • ganeshie8
you can convert that state machine to turing program easily
ganeshie8
  • ganeshie8
** |dw:1444367192800:dw|
ganeshie8
  • ganeshie8
basically, the statemachine resets everytime it sees a 0
dan815
  • dan815
can u write out your program in that 5 step rule
ganeshie8
  • ganeshie8
|dw:1444367429426:dw|
ganeshie8
  • ganeshie8
your states correspond to above, right ?
dan815
  • dan815
okay i can kind of see what ua re doing
dan815
  • dan815
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
dan815
  • dan815
those kind of drawings could be useful actually in just come up with some idea to do, before writing al gorithm
dan815
  • dan815
like for example if i were to use your drawings to make this left most finding 1 problem it would look like --->
dan815
  • dan815
|dw:1444367903673:dw|
ganeshie8
  • ganeshie8
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) ```
ganeshie8
  • ganeshie8
because the turing machine has state knowledge, it never has to backtrack
dan815
  • dan815
okay so can you tell me which problem you are trying to solve ganeshie
ganeshie8
  • ganeshie8
to identify the pattern 01111 on a sequential line using turing machine
Kainui
  • Kainui
(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)
dan815
  • dan815
but remember this is an infnite strip ganeshie, you dont knwo if ur 1s are on the left or right
ganeshie8
  • ganeshie8
How does that matter if the turing maching is keeping track of the state that is in
ganeshie8
  • ganeshie8
s1, s2, s3, s4, s5 correspond to specific states that give us the information about what state we are in finding the pattern, right ?
dan815
  • dan815
are you currently just going only right ganeshie
Kainui
  • Kainui
|dw:1444368331824:dw|
ganeshie8
  • ganeshie8
Yes, only forward...
dan815
  • dan815
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
dan815
  • dan815
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
ganeshie8
  • ganeshie8
I am assuming we have reset thingy and the tape has a well defined start point
dan815
  • dan815
no reset thing xD
dan815
  • dan815
there is the halting state which just stops, and move the reader to the left or right before it does so, thats about it
ganeshie8
  • ganeshie8
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 ?
dan815
  • dan815
nope
dan815
  • dan815
i mean your reader is somewhere we dont know where it is, we just know its somewhere
dan815
  • dan815
jut some infinite line
ganeshie8
  • ganeshie8
Okay the previous statemaching works just fine, I just need to add what happens when it encounters "1", one sec...
ganeshie8
  • ganeshie8
If the current value is 0, it can simply move forward, no need to backtrack, agree ? |dw:1444368962345:dw|
Kainui
  • Kainui
|dw:1444369006730:dw|
ganeshie8
  • ganeshie8
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
dan815
  • dan815
you gotta find a way to do that zigzag thign in the above pic
dan815
  • dan815
we have to back and forth
ganeshie8
  • ganeshie8
we have to back and forth only if the current value is 1 when we start
dan815
  • dan815
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
dan815
  • dan815
the whhole problem is 0 0000000001111111000000000 you dont know if ur in the 0s on the left or the right
dan815
  • dan815
...0000001111110000......
ganeshie8
  • ganeshie8
if you start at 1, you don't know what the next state will be
Kainui
  • Kainui
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)
ganeshie8
  • ganeshie8
`01111` it could be the first, second, third or fourth 1
ganeshie8
  • ganeshie8
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
dan815
  • dan815
oh i see i think u are misunderstading what a state is
ganeshie8
  • ganeshie8
enlighten me then
dan815
  • dan815
a state has nothing to do with where your reader is or how your strip is right now or anything
Kainui
  • Kainui
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|
dan815
  • dan815
its just this like variable you are using to keep track of what command u want to do right now
ganeshie8
  • ganeshie8
are you defining own terminology here ? because thats not how i remember using it..
ganeshie8
  • ganeshie8
consider the state diagram of a simpler circuit, mod10 counter or something, how do you define a state in this ?
dan815
  • dan815
http://prntscr.com/8pcu8g
dan815
  • dan815
|dw:1444369816762:dw|
ganeshie8
  • ganeshie8
don't take me seriosuly though, i could be wrong... its been so many years...
dan815
  • dan815
|dw:1444369924025:dw|
dan815
  • dan815
|dw:1444369944055:dw|
dan815
  • dan815
https://ms.mcmaster.ca/~speisseg/blog/?page_id=2731
dan815
  • dan815
|dw:1444370662565:dw|

Looking for something else?

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