FANDOM


Let's say that TM computes f(n) = m if for input = n consecutive 1's it outputs m 1's (may not be consecutive). Head is placed on the leftmost 1. For f(0), let's say that input is empty.

Next I'll post some TMs found by the program. If anyone interested, you can check them at simulator.


f(n) = n*2 for (n>=0):

0 _ _ r halt
0 1 1 l 1
1 _ 1 r 2
1 1 _ l 1
2 _ 1 r 2
2 1 1 r 0

f(0) = 1

f(n) = n*2 for (n>0)

0 _ 1 r halt
0 1 1 r 1
1 _ 1 r 0
1 1 _ l 2
2 _ 1 r 2
2 1 1 l 1

f(n) = n*2 for (n>0, doesn't halt at n=0)

0 _ 1 r 0
0 1 1 r 2
1 _ 1 r 0
1 1 _ l 1
2 _ 1 r halt
2 1 1 l 1

f(n) = n*3 for (n>=0)

0 _ _ l halt
0 1 1 l 1
1 _ _ l 2
1 1 _ l 1
2 _ 1 r 2
2 1 1 r 0