FANDOM


\Sigma(13)>f_{\omega}(2046) (Wythagoras 2016)

Historical table of boundsEdit

Bound Discoverer Year and month
f_{\omega}(2046) Wythagoras September 2016

Analysis of the current record holderEdit

Ackermannian growth using 8 statesEdit

0 1 1 r 0
0 _ 1 r 1
1 _ _ r halt
1 1 _ r 2
2 _ _ l 6
2 1 1 l 7
3 1 1 l 3
3 _ _ r 4
4 1 1 r 5
5 1 _ r 0
6 _ 1 l 3
7 1 1 l 7
7 _ _ l 8
8 1 1 l 7
8 _ 1 r 9
9 _ 1 r 0

Note that the following half-states can be paired: (4+6), (5+9).

This machine executes a function f(a_1,a_2,a_3,\cdots,a_n) of n variables, defined as

  • f(a_1,a_2,a_3,\cdots,a_n)=f(a_1+3,a_2-1,a_3,\cdots,a_n) if a_2>1.
  • f(a_1,\underbrace{1,1,\cdots,1,1}_{k},1,a_k,\cdots,a_n)=f(3,\underbrace{1,1,\cdots,1,1}_{k},a_1+1,a_k-1,\cdots,a_n) if a_k>1.
  • f(a_1,\underbrace{1,1,\cdots,1,1}_{k})=a_1+k+1.

We have f(3,a_2)=f(3a_2,1), f(3,a_2,2)=f(3a_2,1,2)=f(3,3a_2+1,1)>f(3,3a_2,1)=f(9a_2,1,1) and in general f(3,a_2,a_3)>f(3^{a_3}a_2,1,1). f(3,1,a_3)>f(3^{a_3},1,1). This gives f(3,1,1,a)>f(3\uparrow\uparrow a,1,1,1), and in general, by induction f(3,\underbrace{1,1,\cdots,1,1}_{b},a)>f(3\uparrow^b a,\underbrace{1,1,\cdots,1,1}_{b+1})>3\uparrow^b a

Input using 5 statesEdit

There exists a 5 state TM with the following output[1]:

11 (011)2047 1

It halts with the head on the second one. Instead of halting, we let it go to state 0 of the Ackermannian growth machine. This amounts to simulating  f(2,\underbrace{2,2,\cdots,2,2}_{2046},3) > f(3,\underbrace{1,1,\cdots,1,1}_{2046},3) > 3 \uparrow^{2046} 3 > f_{\omega}(2046)

ReferencesEdit

  1. H. Marxen, 5-state TM #3 from MaBu-List