I’ve always wanted to understand Turing Machines better. I believe that the best understanding comes from the intuition developed by solving puzzles.

So here, I give myself some challenges. Solve simple problems by writing programs for a simple Turing Machine, using this simulator: http://ironphoenix.org/tril/tm/

**Challenge 1: Odd or even characters?**

Challenge:

Make a program for a Turing Machine, such that the program:

- outputs E if there is an even number of sequential x’es on tape
- outputs O if there is an odd number of sequential x’es on tape
- the program does not have to handle the empty string
- running time not important

For example, the program should output ‘E’ for the following input:

xxxx |

My solution to challenge 1:

1,x 2,1 > 2,x 3,. < 2,. 2,. > 2,_ 4,_ < 3,. 3,. < 3,0 2,1 > 3,1 2,0 > 4,. 4,_ < 4,0 5,E > 4,1 8,O > 5,_ 6,V, > 6,_ 7,E > 7,_ H,N > 8,_ 9,D > 9,_ H,D > |

The program has O(n^2) running time.

## Challenge 2: Improve the solution to linear running time

In the above only the character ‘x’ is matched. Matching *n* characters would mean adding n transitions to state 2. That is straight forward, and I’ll not do it in the following.

Challenge:

Improve the solution to challenge 1:

- Algorithm must have O(n) running time
- It should handle the empty string (output ‘E’)

My solution to challenge 2:

1,_ 9,_ > 1,x 2,# > 2,x 3,x < 2,_ 6,_ < 3,0 5,0 > 3,1 4,1 > 3,# 4,# > 4,x 2,0 > 5,x 2,1 > 6,0 7,_ < 6,1 8,_ < 6,# 10,_ > 7,0 7,_ < 7,1 7,_ < 7,# 9,_ > 8,0 8,_ < 8,1 8,_ < 8,# 10,_ > 9,_ H,E > 10,_ H,O > |

## Challenge 3: Sorting

Ok, let’s up the ante a little bit. Let’s do sorting.

Challenge:

- Sort a scrambled sequence of numbers from 0-9
- Running time should be no worse than bubble sort, O(n^2) worst case

TODO