# Simplest Turing Machine for a particular binary string

At the Bank of England is a proposed £50 note.

Alan Turing was born on the 23rd June 1912. 23061912 in decimal is 1010111111110010110011000.

Starting from a blank tape, what is the simplest Turing machine that generates 1010111111110010110011000 at some stage?

Starting from a blank tape, what is the simplest Turing machine that generates 1010111111110010110011000 and halts?

• A simple upper bound would be the brute force method, which would have 22 instructions: (A, R0, W1, B), (B, R0, W0, C)... (U, R0, W1, V), (V, R0, W1, HALT), where an instruction is (Start State, Read Bit, Write Bit, Next State). – Vedvart1 Jul 15 at 17:48
• How are you measuring simplicity? Or is there an implicit "without using more symbols than blank, 0, 1"? – Peter Taylor Jul 15 at 22:03

The second question is a tough one. I have a feeling that it is possible to do in $$\approx 8-10$$ states, but I am still figuring this out.