# 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 T_{1}T_{2}...T_{k}, where *k* ≥ 1.

The ordinal of a bracket expression is defined recursively as follows:

ord e ::= 0 ord (E) ::= ω^{ord E}ord T_{1}T_{2}...T_{k}::= sum(ord T_{1}, ord T_{2}, ..., ord T_{k})

where E is any bracket expression, the T_{i} 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 = f_{T}X g_{X}T where f_{T}X is a bracket expression (possibly depending on T), with ord f_{T}X < ord X, g_{X}T is a tree (possibly depending on X), with ord g_{X}T > 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

g_{X}T = (T) f_{T}X = r_{n}X

where *n* is the size of (T), and r_{n} is the "reduction operator" defined as follows for any expression X = A(B):

r_{n}A(B) = A (r_{n}B)^{n}if B > e r_{n}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)...) = T_{final}.

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 g_{X}(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> <2^{n+1}(n+3)-2> (()^{k})<n> greater than 2^^...^(n+1), where ^^...^ denotesk-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 2^{39}41 - 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 = 2^{1+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)