MUN Computer Science 2000 - Lab 2

Logic and computation

Topics

Lab Explorationstop |

1.

Turing machines: playing with numbers

In the Turing machine simulator, load the example program called "Binary to decimal conversion", and try it on a few inputs of your choice.
1.1. Does this program always stop, no matter what the input is?
1.2. How does the number of steps it takes to convert a number relate to the number being converted? Try it on a few inputs, and see if you can generalize it (just a ballpark figure is good enough, no need for an exact formula).
1.3. What kind of input format does it expect to see? What does this machine do if you give it an erroneous number (e.g., no input or an input that's already in decimal)?

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).

3.

Game of Life:

Run the Game of Life simulator
3.1. Try the "glider" pattern from the pattern list. How many different shapes does the glider take? How much does it move up and to the right after one iteration (that is, cycling through all its shapes)?
3.2. Try making a pattern consisting of a row (or a column) of live cells. How does it behave? Try a few experiments with different number of cells; which numbers do you find the most interesting and why?
3.3. Try creating a few random patterns using the mouse. Take the picture of the screen at the start and after it stabilizes (if it does).
3.3.1 Run the random patterns until they stabilize. What kind of patterns do you see when it stabilizes (static ones, oscillating ones)? How long did it take them to stabilize? Did you see any pattern that did not really stabilize after a significant amount of time?
3.3.2 Did any of the patterns stabilized to an empty screen (with no live cells)? If so, were they much different from the other patterns (in the number of initial cells, the way they were spread out, etc)?
3.3.3 Did you see many moving ("crawling") patterns? If so, which kinds? Draw some of them. Did any ever come back after disappearing from view? And what did you observe when they ran into stabilized patterns and/or each other?
3.3.4 Write any other thoughts you have about your experiments.