Transfinity is a functional programming language that works with some sort of transfinite recursion.
Source code consists of function definitions such that for all
where is the set of all countable ordinal numbers and is the arity of -th function. Some of the functions are allowed to be partial (undefined for some inputs).
Each function definition can be one of:
- Constant zero function:
- Projection function: for some
- A function call
- An operator applied to other functions (including the function itself)
or some combination of the above.
There are four operators that can be used to make composite functions:
For any and such that for some
For any such that for some
For any and
where is the smallest ordinal number for which
For any and
where is the smallest ordinal number such that . Note that must be finite, since it is a natural number.
These examples are written by hand. If anyone spots some trivial mistake, please fix it.
This is a function that takes no arguments and returns the constant zero.
succ takes an ordinal as an argument and increments it by 1.
pred returns the predecessor of its argument. The function does not terminate if its argument has no predecessor.
omega takes no arguments and returns the smallest infinite ordinal .
ω + 1
omegaPlus1 returns .
2omega returns .