Transfinity

From Esolang
Jump to navigation Jump to search
Transfinity
Paradigm(s) Functional
Designed by User:Hakerh400
Appeared in 2020
Computational class Uncomputable
Major implementations Unimplemented
File extension(s) .txt


Transfinity is a functional programming language that works with some sort of transfinite recursion.

Overview

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.

Operators

There are four operators that can be used to make composite functions:

  • Operator
  • Operator
  • Operator
  • Operator

Operator

For any and such that for some

where

Operator

For any such that for some

Operator

For any and

where is the smallest ordinal number for which

Operator

For any and

where is the smallest ordinal number such that . Note that must be finite, since it is a natural number.

Examples

These examples are written by hand. If anyone spots some trivial mistake, please fix it.

Zero


This is a function that takes no arguments and returns the constant zero.

Successor


Function succ takes an ordinal as an argument and increments it by 1.

Predecessor


Function pred returns the predecessor of its argument. The function does not terminate if its argument has no predecessor.

ω


Function omega takes no arguments and returns the smallest infinite ordinal .

ω + 1


Function omegaPlus1 returns .


Function 2omega returns .