Hydra
Hydra is a type of rewriting system that iterates the application of a single transformation rule to a bracket expression. All hydra computations terminate after a (typically very large) finite number of iterations; consequently, hydra is not Turing-complete. Hydra was created by user "r.e.s." in 2002, based on the "Hydra game" of Kirby and Paris.
Bracket expressions
The set of bracket expressions is defined in Backus-Naur form as follows:
E ::= e | E1 '(' E2 ')'
where e denotes the empty string.
These are simply the usual "balanced" bracket expressions in which all brackets appear as pairs of "matching" right- and left-brackets.
An expression of the form (E), i.e. with an outermost enclosing pair of brackets, will be called a tree. Note that every nonempty bracket expression E is a unique sequence of trees, say T1T2...Tk, where k ≥ 1.
The ordinal of a bracket expression is defined recursively as follows:
ord e ::= 0 ord (E) ::= ωord E ord T1T2...Tk ::= sum(ord T1, ord T2, ..., ord Tk)
where E is any bracket expression, the Ti are trees, and the ordinal addition in the sum is performed with the addends in nonincreasing order.
Thus
ord () = ωord e = ω0 = 1 ord ()() = ord () + ord () = 2 ord (()) = ωord () = ω ord (()()) = ωord ()() = ω2 ord ()((()()))(()) = ord ((()())) + ord (()) + ord () = ωω2 + ω + 1 etc.
The size of an expression is the number of bracket pairs composing it.
The hydra transformation
In general, a hydra transformation is any operation of the following form, applying to a nonempty bracket expression, say XT, where X is a bracket expression and T is a tree:
hydra XT = fTX gXT where fTX is a bracket expression (possibly depending on T), with ord fTX < ord X, gXT is a tree (possibly depending on X), with ord gXT > ord T, and these are simply concatenated.
Note that f maps a bracket expression to another bracket expression, and g maps a tree to another tree.
The default hydra transformation uses
gXT = (T) fTX = rnX
where n is the size of (T), and rn is the "reduction operator" defined as follows for any expression X = A(B):
rn A(B) = A (rn B)n if B > e rn A() = A
where a superscript n on an expression denotes n concatenated copies of that expression.
As a (non-Turing-complete) computational model, hydra takes an initial bracket expression XT, where X is interpreted as a program and T is interpreted as the input. The hydra tranformation is then iterated until the entire bracket expression is reduced to a single tree, which is interpreted as the output. The computation thus appears as follows:
XT → hydra XT → hydra(hydra(XT)) → ... → hydra(hydra(...hydra(XT)...) = Tfinal.
In the fast-growing hierarchy of functions, it can be shown that every function with ordinal index less than ε0 is hydra-computable. Furthermore, the function h(n) computed by the hydra program ((..()..)) with n nested brackets, where n is the size of the input tree, has a growth rate equal to that of the function in the fast-growing hierarchy whose ordinal index is ε0. The function h therefore dominates Goodstein's function, strictly dominating it for all n > 1.
Note that with the default g, the rightmost tree serves as a simple counter, whose size is incremented by 1 in each application of the hydra transformation. An alternative g, for example, would be gX(Y) = (XY), which would vastly accelerate the "counting".
By the decreasing ordinal theorem, there exists no infinite strictly-decreasing sequence of ordinals; consequently, repeated application of a hydra transformation (for fixed f and g) eventually reduces any nonempty expression to a single tree. The final tree is typically of immense size, even with the default hydra transformation.
Among the possible concatenations of a given set of trees, the one in which they appear in nonincreasing order of their ordinals (from left to right), will result in hydra iterations halting with a tree of maximum size.
OISC interpretation
Hydra can also be viewed as a type of OISC, in which memory is a finite but unbounded bitstring with bits represented as brackets '(' and ')', rather than the usual '0' and '1'. The entire bitstring is interpreted as a single instruction to transform itself by one application of the hydra transformation. The instruction consists of two parts: a leading bracket expression X (interpreted as a program) followed by a tree (Y) (interpreted as the input). If the leading expression X is not empty the instruction is executed, which transforms it into another instruction of the same two-part form. The resulting instruction is again executed if its leading expression is not empty, and so on, with execution halting when the instruction has been reduced to a single tree (interpreted as the ouput).
Another equivalent OISC interpetation of hydra is to regard the entire bitstring as a finite sequence of trees, with the instruction consisting of the rightmost two trees. Repeated execution eventually halts when the instruction is reduced to a single tree. The same transformation rule that's explained above for XT would apply, but now X is just the next-to-last tree rather than the whole expression preceding the last tree.
Examples
In the following, <n> denotes any tree of size n, and the default incrementing function is assumed.
program + input output --------------- ------ ()<n> <n+1> (())<n> <2n+2> (()())<n> <2n+1(n+3)-2> (()k)<n> greater than 2^^...^(n+1), where ^^...^ denotes k-1 Knuth arrows ((()))<n> greater than the diagonalised Ackermann function A(n,n) ((()()))<n>, etc., have rates-of-growth far exceeding that of the diagonalised Ackermann function
E.g., ((()))() outputs a tree of size 23941 - 2, and ((()()))() outputs a tree of size far greater than Graham's number.
Here's an execution trace for (()())(), i.e. for (()2)<1>, which outputs a tree of size 14 = 21+1(1+3) - 2:
program data tree
-------------- ---------
(()()) <1>
(())(()) <2>
(())()()() <3>
(())()() <4>
(())() <5>
(()) <6>
()()()()()()() <7>
()()()()()() <8>
()()()()() <9>
()()()() <10>
()()() <11>
()() <12>
() <13>
<14>
(halt with a tree of size 14)