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)
Category:2002
Category:Total