Hyperamycus

From Esolang
Jump to: navigation, search

Hyperamycus is a functional programming language defined by David Madore in his 2015-11-16 blog article “Qu'est-ce qu'une machine hyperarithmétique ?” which is non-computable and strictly more powerful than Turing-machines.

The motivation why this language came to being is that David wanted to give a precise definition for a larger computability class called “hyperarithmetic function” by defining this programming language. To ensure that the definition of Hyperamycus is correct and understandible, he first defined a Turing-equivalent language Amycus, and then an extension that turns that language to Hyperamycus.

Definition

The basic data type of Hyperamycus is natural numbers of unbounded size, but these numbers are usually treated as representing recursive lists in the Lisp sense. The empty list <> is represented by the number 0, the list <a: d> with head a and tail d is represented as the number 2**a * (2 * d + 1), and in general a finite list <x1, x2, …, xk> is represented as <x1: <x2: <… <xk, <>>…>>>. This construction makes every natural number a list.

Programs are represented as a number (list), operate on a single input argument which is also a number (list), and give a single number (list) as the result. There is no IO or other side effects. Evaluation is defined by the following recursive definition, where E(p, x) = y means that the program p on the input x evaluates to the value y.

Rule 0. 
E(<0>, x) = x
Rule 1. 
E(<1, c>, x) = c
Rule 2. 
E(<2>, <x: y>) = 1 + x
Rule 3. 
E(<3, n>, <x1: <x2: <…, <xn:d>…>>>) = xn
Rule 4. 
E(<4>, <m, n, x, y>>) = (if m == n then x else y)
Rule 5. 
E(<5, q, p1, …, pn>, x) = E(q, <E(p1, x), …, E(pn, x)>)
Rule 6. 
E(<6>, <p, x>) = E(p, x)
Rule 7. 
E(<7>, p) = (TODO complete the definition here later)

It is unclear whether n is allowed to be 0 in rule 3 and/or in rule 5.

Notes

  • The addition of rule 7 is the only way this language differs from Amycus. This is the rule that makes the language uncomputable. Any Amycus program is also a Hyperamycus program, and on inputs where the result of running Amycus is defined for this program, Hyperamycus gives the same result.
  • The rules the Amycus article defines for abstraction elimination to transform lambda calculus expressions to Amycus still work if lambda calculus is expanded with new primitives so that some of the functions are non-computable, so the technique described there can also be used to program Hyperamycus. This is not immediate, because Amycus is capable of reading and interpreting its own programs, so you could use techniques that do not extend to Hyperamycus.
  • David doesn't give a name for this language, so User:B_jonas gave the name “Hyperamycus” as a placeholder.