Rayofuck

Rayofuck is an extension of brainfuck that adds a new set-theoretic Rayo's function. This function is extremely fast growing that it outgrows all Busy beaver numbers, oracle busy beaver numbers, hyperarithmetic busy beavers, and so on.

Definition

+ Increment the cell pointer value (unbounded)
- Attempt to decrement the cell pointer value (lower bounded by 0)
< Move the cell pointer to the left
> Move the cell pointer to the right
, Input a character from the current cell
. Attempt to output a character from the current cell (0-255)
[ While current cell pointer value is nonzero...
] ... do the stuff inside the brackets
# Replace the number X in the pointer with Rayo(X)

Here, we define Rayo(X) as "The smallest (natural) number bigger than any finite (natural) number named by an expression in any language of first-order set theory in which the language uses only X symbols or less."

Full definition of Rayo's function is on the Googology wiki page.

Computational Class

Very clearly, Rayofuck is extremely powerful, as we can essentially determine if a Turing machine halts or not by running for Rayo(n) > BB(n) steps, for sufficiently large n. This means Rayofuck is capable of solving the Halting problem, though Rayofuck can also solve the oracle Halting problem since one can imagine running the higher level machine for Rayo(n) > BB_1 (n) steps but the simulated machine for Rayo(Rayo(n)) > BB_0 (BB_1 (n)) steps.

In fact, Rayofuck is already more powerful than Version 0 of Σ∞ because Rayofuck can simulate oracle Turing machine: we imagine having Rayo(n) layers, each with Rayoⁱ(n) iterations. This works because Rayo(n) grows faster than any function describably in first order arithmetic.

Conjecture

Rayofuck is conjectured to be as powerful as hyperarithmetic turing machines: that is it can simulate anything up to hyperarithmetic. We can do this by building a fast iteration hierarchy on Rayo's function as the base case. This allows us to define any ordinal up to the Church Kleene ordinal, where we hit a roadblock. This is because to go beyond we must quantify over sets of natural numbers, but we do not have access to these structures.

Large Numbers

Even if Rayofuck fully covers hyperarithmetic functions but not say... analytical hierarchy functions, Rayofuck can still produce extremely large numbers by iterating Rayo's function. For example, the following program:

+++...a googol pluses...+++#[->.<]

produces Rayo's number of null characters. We can continue up the fast iteration hierarchy with Rayo's function as the base.

Limiting Rayofuck

We may choose to accept only programs that produce the same output if we replace the behavior of # operator with something more powerful, say this:

# Replace the number X in the pointer with f(Rayo(X)) where f is the function from https://googology.fandom.com/wiki/Large_Number_Garden_Number

The result is Rayofuck-, and it is more stable as it disallows large numbers generated by a fast iteration hierarchy on Rayo's function.