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 nth 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 nth 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 \ge 3 \uparrow x,
g_3(x) \ge 3 \uparrow^2 x,
And more generally,
g_{n+1}(x) \ge 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!
Category:Languages
Category:Total
Category:2024