Bigfun

Bigfun is a total esolang created by User:Pro465 in 2024 to represent fast-growing functions and large numbers. It is based on minsky machines and the fast growing hierarchy.

Description

Since this esolang relies heavily on functions, the following part contains some maths, so beware.

Let $\mathbb {S} :=\mathbb {N} ^{\mathbb {c} }$ be the set of all possible register states with $\mathbb {c}$ being the number of registers required, then a Bigfun program is just a function $f:\mathbb {S} \rightarrow \mathbb {S} .$

Let $r\in \mathbb {S}$ and $n<\mathbb {c}$, then $r[n]$ is defined as the $n$th entry of $r$ (0-based).

There is only one type of primitive function, represented by +n where $n\in \mathbb {N}$ and $n<\mathbb {c}$, which just takes the register state and returns it but with $r[n]$ incremented by 1.

There are two operations on functions:

1. concatenation is composition - Let there be two programs p and q with corresponding functions $f,g:\mathbb {S} \rightarrow \mathbb {S} .$

Then the function representing p q is given by $g\circ f$.

2. the bigify operator - Let there be a program p with corresponding function $f:\mathbb {S} \rightarrow \mathbb {S} .$

then the function corresponding to (m|n|p) where $m,n\in \mathbb {N}$ and $m,n<\mathbb {c}$ is $\Omega (f,m,n)$

where $\Omega (f,m,n):\mathbb {S} \rightarrow \mathbb {S}$ defines a new family of functions, $g_{i,j}:\mathbb {S} \rightarrow \mathbb {S}$,

such that:

1. $g_{i,0}(r)=f(r),$

2. $g_{i,j+1}(r)=g_{i,j}^{r[i]}(r)$, where $g_{i,j}^{n}$ is the $n$th iterate of $g_{i,j}$.

and diagonalizes over it:

$\Omega (f,m,n)(r)=g_{m,r[n]}(r).$

Execution

The function $f$ corresponding to the whole program is evaluated with its argument being a $\mathbb {c}$-tuple with every element being 0, and the resulting state is outputted and the program halted.

Examples

just some random large number

  +0+0+0(0|0|+0)

exits with $3\cdot 2^{402653211}$ in register 0.

a number much greater than Graham's number

+0+0+0+0
+1+1+1+1
(1|1|+0(0|0|+0+0))

exits with a number much greater than graham's number on register 0. In fact, it's much larger than $g_{256}.$

Explanation

Let $f,g_{i}:\mathbb {N} \rightarrow \mathbb {N} ,i\in \mathbb {N}$ be defined by:

$f(x)=x+2,$

$g_{0}(x)=f(x),$

$g_{i+1}(x)=g_{i}^{x}(x).$

(We'll use $G_{n}$ instead of $g_{n}$ for Graham's numbers to avoid conflict with our function.)

Then, $g_{1}(x)=2x+x=3x,$

$g_{2}(x)=x\cdot 3^{x}\geq 3\uparrow x,$

$g_{3}(x)\geq 3\uparrow ^{2}x,$

And more generally,

$g_{n+1}(x)\geq 3\uparrow ^{n}x$

where $a\uparrow ^{n}b$ is Knuth's up-arrow notation.

And thus, $g_{n+1}(n+1)>3\uparrow ^{n}3$ for any $n>0.$

so the corresponding program,

   +0(0|0|+0+0)

implements a function that always results in a number that's at least $3\uparrow ^{n}3$ given an input $n>0.$

now we just need to repeat this 256 times, which is what +1+1+1+1(1|1|p) does for any program p, provided that register 1 doesn't get incremented in p.

So our almost finished code is:

   +1+1+1+1(1|1|+0(0|0|+0+0))

we need to initialize register 0 with 4 though, because the first number ($G_{1}$) is supposed to be $3\uparrow ^{4}3$ and we are currently starting off with $G_{1}=g_{1}(1)=3.$ So we add a +0+0+0+0 to the beginning of the program:

   +0+0+0+0+1+1+1+1(1|1|+0(0|0|+0+0))

and that's it!