Recently, I've become interested in googology. The Busy Beaver function, \(BB(n)\), has been of particular interest. It is defined as the maximum number of \(1\)s written by any halting \(n\)-state Turing machine. A natural extension of the Busy Beaver function is to replace Turing machines with a more powerful construct, such as augmenting a Turing machine with a halting oracle. I develop such an extension below.
A \(SEA(\alpha)\) machine is a 3-tape Turing machine with tapes denoted \(T_1\), \(T_2\), and \(T_3\). Each cell is indexed by an ordinal in \(\mathcal{K} = \omega\) (this notation will facilitate later extensions). There is only one head, \(H\). The value of the \(k\)th cell after \(t\) steps on the \(n\)th tape is \(T_n(k, t)\) and the position of the head is \(H(t)\). The initial position of the head is \(0\). Unless otherwise specified, every cell on every tape is initialized to \(0\).
The head can only write directly to \(T_1\), but it can read from all tapes. That is, at step \(t\), \(H\) reads \((T_1(H(t),t),\, T_2(H(t),t),\, T_3(H(t),t))\), and writes to \(T_1\).
Write symbols are in \(\{0, 1, S, E_\alpha, A_\alpha\}\).
When the head writes the symbol \(S\) at step \(t\), \(T_1\) is unchanged (i.e. it writes whatever was already there). However, \(T_3\) is instantaneously changed globally so that for every \(k \in \mathcal{K}\), \(T_3(2k,t+1)=T_3(k,t)\) and \(T_3(2k+1,t+1)=T_2(k,t)\).
(The idea is that \(S\) saves the information on \(T_2\) to \(T_3\) via interleaving. Note \(T_2\) is currently a read-only string of \(0\)s. It will be relevant later when considering \(E_\alpha\) and \(A_\alpha\).)
For a given \(SEA(\alpha)\) machine that has computed \(t\) steps with tapes \(T_1\), \(T_2\), and \(T_3\), let a \((\beta, s, t)\)-copy denote a \(SEA(\beta)\) machine with tapes denoted by \(T'_1\), \(T'_2\), and \(T'_3\). Instead of starting with blank tapes, a \((\beta, s, t)\)-copy's tapes are initialized such that for every \(k \in \mathcal{K}\), \(T'_1(k,0)=T_1(k,t), T'_2(k,0)=s(k),\) and \(T'_3(k,0)=T_3(k,t)\). The transition table of the \((\beta, s, t)\)-copy is the same as that of the \(SEA(\alpha)\) machine, except that every instance of \(E_\alpha\) is replaced with \(E_\beta\) and every instance of \(A_\alpha\) is replaced with \(A_\beta\).
Let \(\mathcal{S}\) denote \(\{s \mid s: \mathcal{K} \to \{0,1\},\; |\{k \in \mathcal{K} \mid s(k)=1\}| = |\mathcal{K}| \}\)
(The restriction on \(\mathcal{S}\) to output \(1\) \(\mathcal{K}\)-many times is useful as it guarantees that we can count the number of \(0\)s between the \(k\)th and \(k+1\)th \(1\)s to get a total function \( f \mid f: \mathcal{K} \to \mathcal{K}\).)
\(E_0\) always writes \(1\) and \(A_0\) always writes \(0\).
If \(\alpha = \beta + 1\), then \(E_\alpha\) writes a \(1\) at step \(t\) if there exists some \(s \in \mathcal{S}\) such that a \((\beta, s, t)\)-copy of the machine halts, \(0\) otherwise. \(A_\alpha\) writes a 1 at step \(t\) if for every \(s \in \mathcal{S}\) the corresponding \((\beta, s, t)\)-copy of the machine halts, \(0\) otherwise.
If \(\alpha\) is a limit ordinal, then \(E_\alpha\) writes a \(1\) at step \(t\) if there exists some \(\beta < \alpha\) such that there exists some \(s \in \mathcal{S}\) such that a \((\beta, s, t)\)-copy of the machine halts, \(0\) otherwise. \(A_\alpha\) writes a \(1\) at step \(t\) if for every \(\beta < \alpha\), for every \(s \in \mathcal{S}\), the corresponding \((\beta, s, t)\)-copy of the machine halts, \(0\) otherwise.
We define a \(SEA\) machine, which is defined as before except the write symbols are in \(\{0, 1, S, E, A\}\). \(E\) writes the same value to \(T_1\) as \(E_{H(t)}\) and \(A\) writes the same value to \(T_1\) as \(A_{H(t)}\).
(We diagonalize the hierarchy, but only for finitely many levels of the hierarchy when \(\mathcal{K}=\omega\).)
To get an idea of the power \(SEA\) states give a machine, I would like to note that a \(SEA(1)\) machine can represent \(\omega_1^{CK}\), and the same program can represent even larger ordinals when executed by higher \(SEA(\alpha)\) machines:
[Click to show/hide Python Pseudocode]
from itertools import count
from functools import cmp_to_key
from [EATM_oracle] import s, E, A
from [this_would_be_annoying_to_code] import nth_computable_binary_relation
# basic functions
halt_check = False
prog = None
def all_halts(check_prog, args):
return halts(check_prog, args, True)
def any_halts(check_prog, args):
return halts(check_prog, args, False)
def halts(check_prog, args, allOracle):
global prog, halt_check
prog = lambda: check_prog(*args)
halt_check = True
result = A() if allOracle else E()
halt_check = False
return result
def loop():
while True:
pass
def f(n):
m = 0
for k in count():
if s(k):
if n == 0:
m = k
if n == -1:
return k - m - 1
n -= 1
# supremum of well-orders
def pair():
return (f(0), f(1))
def trip():
return (f(0), f(1), f(2))
def can_eval(R):
(x,y) = pair()
R(x,y)
return
def is_total(R):
(x,y) = pair()
if not (R(x,y) or R(y,x) or x == y):
loop()
def is_antisymmetric(R):
(x,y) = pair()
if R(x,y) and R(y,x) and x != y:
loop()
def is_transitive(R):
(x,y,z) = trip()
if R(x,y) and R(y,z) and not R(x,z):
loop()
def is_well_founded(R):
for n in count():
if not (R(f(n+1), f(n)) and f(n+1) != f(n)):
return
def is_well_order(R):
if not all_halts(can_eval, (R,)):
return False
if not all_halts(is_total, (R,)):
return False
if not all_halts(is_antisymmetric, (R,)):
return False
if not all_halts(is_transitive, (R,)):
return False
return all_halts(is_well_founded, (R,))
def encode(n):
n += 1
x = 0
while n % 2 == 0:
n //= 2
x += 1
y = (n - 1) // 2
return (x, y)
def sup_order(m, n):
(x0, y0) = encode(m)
(x1, y1) = encode(n)
if x0 < x1:
return True
if x0 > x1:
return False
(r, R) = (-1, None)
while x0 > 0:
r += 1
R = nth_computable_binary_relation(r)
if is_well_order(R):
x0 -= 1
return R(y0, y1)
def order(m, n):
if m == 0:
return False
if n == 0:
return True
return sup_order(m-1, n-1)
def main(*args):
global prog, halt_check
if halt_check:
prog()
return
return order(args[0], args[1])
But we don't need to stop there! Note that if instead of Turing machines, we work with ordinal Turing machines and set \(\mathcal{K}=\mathbf{Ord}\), none of the definitions above need to be changed (although we do need to move to a more powerful background theory like \(MK\)).
We can then define a more powerful function, Ordinal-\(TTER\), or \(OTTER(n)\), the maximum number of \(1\)s written by any \(n\)-state ordinal \(SEA\) machine that halts with finitely many \(1\)s on \(T_1\). (Get it? "The Busy Sea Otter." And sea otters kind of look like beavers. I am hilarious.)
Comments
Post a Comment