[math-fun] Turing machine code golf for producing Fibonacci numbers.
I have come up with a protocol for realizing certain integer sequences in the behavior of a two-symbol Turing machine. My machines always start with a tape populated with all zeros. First, I dispense with the halt state; then, I designate some state, symbol, and direction as the reporting criteria of the machine. Whenever the machine performs a transition, and finds itself in the "report" state and looking at the "report" symbol, it looks in the specified direction and counts the number of 1s in that direction, and reports that count as the next element of the sequence. In general, I want to come up with a machine that realizes a given integer sequence in the fewest number of states. I don't care about efficiency. I decided to test the concept by creating a machine that realizes the Fibonacci sequence 0, 1, 1, 2, 3, 5 ... I succeeded, but I was surprised that it took 10 states; my intuition was that it would be about 5. I'm not going to reveal my machine right away, but I want to hear if any funsters can realize the Fibonacci sequence with a Turing machine (using my protocol, please) with fewer than 10 states.
participants (1)
-
Allan Wechsler