Simplest Turing Machine for a particular binary string

421 Views Asked by At

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

enter image description here

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?

1

There are 1 best solutions below

0
On

I believe the answer to the first question is a 3-state machine:

enter image description here

This machine starts with a blank tape and creates every binary number (and never terminates).

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.