Hyperamicus

Hyperamicus 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 Hyperamicus is correct and understandible, he first defined a Turing-equivalent language Amicus, and then an extension that turns that language to Hyperamicus.

Definition

The basic data type of Hyperamicus 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 <v1, v2, …, vk> is represented as <v1: <v2: <… <vk, <>>…>>>, or 2**v1 + 2**(v1+v2+1) + … + 2**(v1+v2+…+vk+(k-1)). 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, v) = y means that the program p on the input v evaluates to the value y.

Rule 0.

E(<0>, v) = v

Rule 1.

E(<1, c>, v) = c

Rule 2.

E(<2>, <n: r>) = 1 + n

Rule 3.

E(<3, n>, <v1: <v2: <…, <vn:d>…>>>) = vn, provided 0 < n

Rule 4.

E(<4>, <m, n, u, v>>) = (if m == n then u else v)

Rule 5.

E(<5, f, g1, …, gn>, v) = E(f, <E(g1, v), …, E(gn, v)>)

Rule 6.

E(<6>, <h: r>) = E(h, r)

Rule 7.

E(<7>, <f>) = 0 if E(<f>, <i>) = 0 for all natural numbers i, and

E(<7>, <f>) = 1 if E(<f>, <i>) is defined (terminates) for all natural numbers i and E(<f>, <j>) ≠ 0 for at least one natural number j.

Rule 5 is valid for any natural number n. As a special case, E(<5, f>) = E(f, <>) = E(f, 0).

Notes

• The addition of rule 7 is the only way this language differs from Amicus. This is the rule that makes the language uncomputable. Any Amycus program is also a Hyperamicus program, and on inputs where the result of running Amycus is defined for this program, Hyperamicus gives the same result.
• The rules that Amicus article defines for abstraction elimination to transform lambda calculus expressions to Amicus 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 Hyperamicus. This is not immediate, because Amicus is capable of reading and interpreting its own programs, so you could use techniques that do not extend to Hyperamicus.
• David doesn't give a name for this language, so User:B_jonas gave the name “Hyperamicus”.