## FANDOM

6 Pages

$\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