Simple programs for simple turing machines

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:

1. outputs E if there is an even number of sequential x’es on tape
2. outputs O if there is an odd number of sequential x’es on tape
3. the program does not have to handle the empty string
4. 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:

1. Algorithm must have O(n) running time
2. 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:

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

TODO