Googology on graphs
Here we define a few interesting operations that build large (finite) graphs out of small graphs. We only consider simple, undirected, connected graphs.
Let \(G = (V, E)\) be a graph and \(n\) a positive number. Let \(S = \{0, 1, \cdots, n - 1\}\). Define \(G' = \exp(G, n)\) as follows.
The vertices of \(G'\) are functions \(f : S \mapsto V\). There is an edge between two vertices \(f_1, f_2\) iff there exists \(i\) such that \(f_1(j) = f_2(j)\) for every \(j \neq i\), and \(f_1(i), f_2(i)\) are joined by an edge in \(G\).
Example: Let \(G\) be the complete graph \(K_2\), then \(\exp(G, n)\) is the \(n\)-dimensional hypercube graph.
If \(G\) has \(m\) vertices then \(\exp(G, n)\) will have \(m^n\) vertices. Furthermore if \(G\) has \(e\) edges…
Revisit Algebraic BEAF
Pick your favorite ordinal notation, which defines a fundamental sequence for every ordinal \(\alpha\) below some limit \(\Gamma\). Previously I described how we can define a system of hypernomials upon this, and introduce an algebraic version of BEAF. Here we consider how to define it more carefully, and how to extend it.
So how do we choose the "root" hypernomial \(H_r\)? Our definition is designed to make the descend to \(0\) as slow as possible. First we prepare a hypernomial \(H' = R(H)\) with complexity lower than \(H\). This can be constructed as follows: \[R(1) = 0\] \[R(X) = \underbrace{1 + 1 + \cdots + 1}_n\] \[R(f(X, H)) = f(X, R(H))\] \[R(H_1 + \cdots + H_n) = H_1 + \cdots + R(H_n)\]
Next we construct a structure that "traces" th…
A General Scheme for Veblen Function
Let \(f(x)\) be a normal function. In general, we assume that \(f(x)\) only outputs additively indecomposable ordinals. Let \(\kappa\) be the smallest regular cardinal, whose first ordinal (Let's call it \(X\)) is a fixed point of \(f\). For example, if you take \(f(x) = \omega^x\) then \(\kappa = \aleph_1, X = \Omega\). We use \(X^+\) to denote the first ordinal of \(\kappa^+\).
Let \(X_k = \begin{cases}1 & k = 0\\X^{X_{k - 1}} & k > 0\end{cases}\) for each natural number \(k\). Then for each positive integer \(k\) we have \(X_{k + 1} = X_k^{X_k}\).
Let \(\alpha\) be any ordinal below \(\epsilon_{X + 1}\). If \(X_k \leq \alpha < X_{k + 1}\) then we say the height of \(\alpha\) is \(k\). The height of \(0\) is \(0\).
If the height of \(\alpha…
Functions on graphs
If you are tired of iterated exponentiations and factorials, here are two ways to construct computable functions that are more interesting to imagine. Both are based on graphs .
First fix a function \(F(n)\) that maps \(n\) to graphs. Its output should increase in complexity as \(n\) grows. For example, the \(n \times n\) grid graph , the \(n\)-dimensional hypercube graph , or the Cayley graph of an \(n\)-dimensional Rubik's Cube .
Let \(G = (V, E)\) be a finite, connected, undirected graph. Pick one vertex \(q\) in \(G\) and call it the sink. The exact choice doesn't matter much. Let \(\tilde{V} = V / \{q\}\). A sandpile on \(G\) is a function \(f : \tilde{V} \mapsto \mathbb{N}\), such that \(0 \leq f(v) < \mathrm{deg}_G(v)\) for each vertex …
Algebraic BEAF
It is well known that BEAF was originally only defined up to tetrational arrays. For pentational and higher arrays, Bowers says: "How to work with these? - Only God knows."
The modern way to define BEAF uses ordinal numbers. To summarize, each "array" is a function which maps ordinals to natural numbers, such that all but a finite number of ordinals are mapped to \(1\). Each ordinal is associated with a group of "passengers", which is a finite set of smaller ordinals. At each step of evaluation, we take the smallest ordinal not mapped to \(1\), decrease its image by \(1\), and set the image of its passengers to the base value.
The problem with this definition is that it loses some of the structural regularity seen in smaller arrays. Up to te…