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