2. |
Turing machines: being logical
In the Turing machine simulator, erase the content of the program box and type in (copy/paste from here) the following program:
0 * * * start_state ; renaming the start state to something more meaningful
start_state 0 _ r zero_state
start_state 1 _ r one_state
start_state _ 0 r halt
zero_state 0 _ r zero_state
zero_state 1 _ r one_state
zero_state _ 0 r halt
one_state 0 _ r one_state
one_state 1 _ r one_state
one_state _ 1 r halt
Then press "reset" to load it on the Turing machine. Now, test this Turing machine on a few inputs.
2.1. |
Suppose instead of 0 and 1 the symbols on the tape are F and T. Which of 0, 1 would you make a T and which a F? Would it now be more readable (i.e., more meaningful) for you? Could you change the names of the states to make it even more readable? And if you change the names of the states and input symbols, would you still consider it to be the same Turing machine? Note: the simulator still wants the input to be 0s and 1s, so you don't need to test the renamed program in the simulator.
|
2.2. |
This machine is designed to simulate a logical operator. Can you see which one it is? And does it simulate it for just two inputs, or any number? Explain in words what you think the program is doing.
|
2.3. |
Modify this program to make it compute a different logic operator. Explain which operator your new program is computing. Try to make as few changes as possible. (Again, because of the simulator limitations please use 0s and 1s in your input).
|
|