# 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).