3
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ 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). $\endgroup$ – Vedvart1 Jul 15 at 17:48
  • 2
    $\begingroup$ How are you measuring simplicity? Or is there an implicit "without using more symbols than blank, 0, 1"? $\endgroup$ – Peter Taylor Jul 15 at 22:03
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.