Programming Turing Machines

Today we worked on an another example of programming a TM.

We learned about the strategy to attack a problem: We start by solving simple cases first and build all the rules along the way solving slightly more difficult cases each time.

Problem statement

Come up with a TM that satisfy the following requirements:

1. The TM must HALT after reading 3 consecutive 0's
2. As soon as it finds a 1, it starts writing the pattern 1010101010 until it halts

Mind you this is not an easy problem, so don't despair, but learn to value your steps forward!

Example cases

1. If it reads ...0000.... the output must be ...0000...., that is, it leaves the tape unmodified
2. if it reads ...01000... the output must be ...01010000....
3. if it reads ...10000... the output must be ...10100000....
4. if it reads ...11000... the output must be ...10100000....
5. if it reads ...1011101000... the output must be ...1010101010000....

Homework: Due Wed Feb 6th 2019

Write a set of rules that achieve to do what examples 1 and 2 above show.

Does this TM you come up with solve as well example 3? Does it solve all cases?

Exploring further

Here a suggestion for you to explore. Search for videos on Conway's Game of Life and for Cellular Automatas. They all are similar to a TM in the sense that they have a set of internal states and a set of rules and what they do depends on those and on what they read. In the game of life, and in general all cellular automata, they read the current cell as well as the neighboring ones.