-
Notifications
You must be signed in to change notification settings - Fork 9
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Lecture "Computability", exercise 1 #7
Comments
Turing machine that writes 101 around the initial cell:
|
This is my proposed solution, I think it'll work
Starting state: A |
blank: '0' |
I don't understand how to do this unless it's possible to move the header two spaces at once. (or move the header without it being part of a state??) I'm going to through my understanding of all the answers posted so far. Please please please if you think you understand this and your answer is right, please reply to me and explain. I think I am misunderstanding some sort of key information about Turing machines and/or the stipulations within the question. @diegochillo's and @fcagnola write a 1 in the initial cell, which is incorrect since the instructions said that one had to be 0 and only the immediately adjacent cells should contain 1. @giorgiasampo's does make 1 0 1 with the 0 being in original cell position of the header but contains instructions for state D which is forbidden. @edoardodalborgo's doesn't work when you write 0 as in state A. It sends you to state C where you write a one and it finishes so it just says 01. Right? What am I missing? Is it something about how the cells are set up before state A begins? Is it the definition of instructions that I've misunderstood and a table that looks like @giorgiasampo's with stuff in state D is allowed? Is the origin cell of the header different from the origin cell of state A? I've tried reusing a state like @DeniseBas but it just traps me in an endless loop. Can you have one state with two different sets of instructions and next states (as in Denise's state A)??? I wouldn't think so but I am lost as to how to actually do this with only states A, B, and C containing instructions, moving one space at a time, and each phase being exactly the same each time it is used. |
I agree with SarahTew, something's not right. |
@SarahTew who wrote:
Dear Sarah, |
At first I was confused because I thought that at the beginning of the execution, the cells could contain either 0 or 1, but after rereading the book chapter, I saw that all the cells are assigned to 0 in advance! I don't know if this information can help other people... :) |
@diegochillo I am still confused so I've copied your algorithm here for reference and below it I have written out when happens when I follow the algorithm and the problems that still aren't resolved. I still don't understand if I'm misreading the question and/or your algorithm. input: ''
Let the bold number be the number in the initial position cell. Let __ represent a cell with nothing written in it (it is either blank or contains something for the machine to read that you have not written) At the end of state A you have __ 1 __ then you move left and to State B. All of the scenarios above end with a 1 in the initial cell. You don't replace it with 0 in State B because you've moved to the left; you're putting a 0 in the cell to the left of your initial starting place. They also don't contain 1s in the cells adjacent to the initial cell. How is your algorithm supposed to work? How are you getting 1 0 1 ? |
input:'' and blank: '0' mean that all the cells are initially filled with symbol '0'.
When there's no state specified, it means that you remain in the same state you are. So the sequence is: Initial symbols: 000 A: regardless of the symbol (1 or 0), write 1 on the initial cell, move left and switch to state B (Symbols: 010) B: cursor is left to initial cell, there's a 0, so write 1 and move right (Symbols: 110) B: cursor is back on initial cell, there's a 1, so write 0, move right and switch to state C (Symbols: 100) C: cursor is right to the initial cell, there's a 0, so write 1, move right and switch to final empty state D (Symbols: 101) ...as ou can check on https://turingmachine.io/ Hope this helps. |
|
@diegochillo Thank you!!! I understand now! For those following the replies: The key is that you don't have to assign a next state (duh!), that's how you can use the same state twice. See @diegochillo's latest reply for a step by step explanation. Mystery solved! Thank you! |
input: '01' seems to work using https://turingmachine.io/ |
input: '' Start state: A |
blank: '0' The output should be: ... 0 0 0 1 0 1 0 0 0 ... |
Hi all, Besides the varous correct answers I've seen here, I have to say that the discussion in this exercise was one of the best ones I've seen in the past four years. Thanks for that! |
Write the table of instructions of a Turing machine with four states – A (initial state), B, C, and D (final state) – such that, once reached the final state, only the cells immediately on the left and on the right of the initial position of the head of the machine will have the value 1 specified. The final state must not have any instruction specified in the table.
The text was updated successfully, but these errors were encountered: