Hydra

From Esolang
Jump to: navigation, search

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[edit]

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[edit]

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[edit]

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[edit]

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)