Turing Machine to generate Fibonacci number in unary

Question

Given a number of consecutive 1's on a Turing machine's tape, I would like to generate a Fibonacci number like so:

Input	Expected output
1	0
11	01
111	011
1111	01111
11111	01111111
111111	0111111111111
...	....

So the output should start with 0 and the total number of output symbols, including the zero, should be the 𝑛^th Fibonacci number where 𝑛 is the input in unary format, actually 𝐹_𝑛−1 according to the definition given by Wikipedia - Fibonacci sequence.

Here an image for when the input is five (B is blank):

How to accomplish this?

Answer 1

You could aim for the following pattern first:

01122333

...where the group with 2's and group with 3's represent the last two members of the Fibonacci sequence produced so far. Then to get the next one added to it, you would append a number of 4's that corresponds to the number of 2's and 3's:

0112233344444

In the process of doing that, you would need to use a mark so you know which digits have already been copied. You could use an 8 to mark a copied 2, and a 9 to mark a copied 3. Once copied you could restore these 8 and 9 digits back to what they were. Then decrease all digits with values between 2 and 4:

0111122233333

Repeat this process as many times as there are 1's in the original input.

The first two cycles will need to be treated differently, so to "boot" the process:

• First cycle: just write a 0
• Second cycle: extend with 3
• From third cycle onwards: apply the above procedure.

When all input has been processed (and removed), replace all 2's and 3's by 1.

Here is a transition table that implements this idea:

state	read	write	move head	next state
start	1	_	right	right
start	0		right	clean
right	1		right	right
right	_	0	left	next
next	0, 1, 2 or 3		left	next
next	_		right	start
right	0		right	read
read	_	3	left	next
read	1		right	read
read	2	8	right	carry
read	3	9	right	carry
read	4	3	right	dec
carry	2, 3 or 4		right	carry
carry	_	4	left	fetch
fetch	2, 3 or 4		left	fetch
fetch	8	1	right	read
fetch	9	2	right	read
dec	4	3	right	dec
dec	_		left	next
clean	1, 2 or 3	1	right	clean
clean	_		left	halt

And a runnable snippet to test it with your own input:

createTuring({
    transitions: [
        { state: "start", read: "1",  write: "_", move: "R", nextState: "right" },
        { state: "start", read: "0",              move: "R", nextState: "clean" },
        { state: "right", read: "1",              move: "R", nextState: "right" },
        { state: "right", read: "_",  write: "0", move: "L", nextState: "next"  },
        { state: "next",  read: "0123",           move: "L", nextState: "next"  },
        { state: "next",  read: "_",              move: "R", nextState: "start" },
        { state: "right", read: "0",              move: "R", nextState: "read"  },
        { state: "read",  read: "_",  write: "3", move: "L", nextState: "next"  },
        { state: "read",  read: "1",              move: "R", nextState: "read"  },
        { state: "read",  read: "2",  write: "8", move: "R", nextState: "carry" },
        { state: "read",  read: "3",  write: "9", move: "R", nextState: "carry" },
        { state: "read",  read: "4",  write: "3", move: "R", nextState: "dec"   },
        { state: "carry", read: "234",            move: "R", nextState: "carry" },
        { state: "carry", read: "_",  write: "4", move: "L", nextState: "fetch" },
        { state: "fetch", read: "234",            move: "L", nextState: "fetch" },
        { state: "fetch", read: "8",  write: "1", move: "R", nextState: "read"  },
        { state: "fetch", read: "9",  write: "2", move: "R", nextState: "read"  },
        { state: "dec",   read: "4",  write: "3", move: "R", nextState: "dec"   },
        { state: "dec",   read: "_",              move: "L", nextState: "next"  },
        { state: "clean", read: "123",write: "1", move: "R", nextState: "clean" },
        { state: "clean", read: "_",              move: "L", nextState: "halt"  },
    ],
    initState: "start",
    tape: "1111111",
});

<script src="https://trincot.github.io/turing.js"></script>