Amycus Severus

Amycus Severus is a Turing-complete functional programming language that is a restricted variant of Amycus. Amycus is an esoteric programming language that was born from a misunderstanding by User:b_jonas over an esoteric programming language Amicus by David Madore.

Definition

A value in Amycus Severus is either a natural number of unbounded size, or a finite size list of Amycus Severus values. Lists are written as <x1, …, xn> where n is a natural number, and x1, … xn are values. (You could think of Amycus Severus values as binary trees with a natural number in each leaf. A list can contain numbers or lists, or the two mixed. Amycus Severus cannot create circular or infinite lists.)

Amycus Severus programs are list values whose head is an opcode number. Amycus Severus takes such a program, and a single input argument which is an Amycus Severus value (number or list), and gives an Amycus Severus value as the result. 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>, v) = v

Rule 1.

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

Rule 2.

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

Rule 3.

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

Rule 4.

E(<4>, <m, n, u, v>) = (if m == n then u else v) provided m, n are both natural numbers

Rule 5.

E(<5, q, p1, …, pn>, x) = E(q, <E(p1, x), …, E(pn, x)>)

Rule 6.

E(<6>, <h, v>) = E(h, v)

Notes

• Amycus Severus is a restricted version of Amycus. Any Amycus Severus program is also a valid Amycus program, and if evaluating Amycus Severus is defined on a program and an input, then evaluating it as an Amycus program is also defined and has the same result.
• Amycus Severus is Turing-equivalent. It can read and write any natural number, so it can compute any computable function from natural numbers to natural numbers.
• You can prove this by translating multivariate lambda calculus expressions and Peano arithmetic to Amycus, as outlined in the Amycus article. All of that translation works unchanged in Amycus Severus.
• Amycus Severus, however, cannot read or write arbitrary lists. Any Amycus Severus program can create lists of only a bounded size, can read only the first bounded number of elements of lists, and there are further restrictions on how it can access lists.
• David doesn't give a name for this language, so User:B_jonas gave the name “Amycus Severus”.