Transfinity

Transfinity is a functional programming language that works with some sort of transfinite recursion.
== Overview ==
Source code consists of n\ge1 function definitions f_1,\dots,f_n such that for all i\in\{1,\dots,n\}
f_i:\omega_1^{m_i}\to\omega_1
where \omega_1 is the set of all countable ordinal numbers and m_i\ge0 is the arity of i-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: f_i(x_1,\dots,x_{m_i})\stackrel{\mathrm{def}}=0
* Projection function: f_i(x_1,\dots,x_{m_i})\stackrel{\mathrm{def}}=x_j for some 1\le j\le m_i
* 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 \circ
* Operator \alpha
* Operator \beta
* Operator \gamma
Operator \circ
For any i,k\in\{1,\dots,n\} and j_1,\dots,j_k\in\{1,\dots,n\} such that m_{j_1}=\dots=m_{j_k}=p for some p
f_i\circ\left[f_{j_1},\dots,f_{j_k}\right]=g
where
g\left(x_1,\dots,x_p\right)\stackrel{\mathrm{def}}=f_i\left(f_{j_1}\left(x_1,\dots,x_p\right),\dots,f_{j_k}\left(x_1,\dots,x_p\right)\right)
Operator \alpha
For any i,j\in\{1,\dots,n\} such that m_i=m_j=p for some p
 \alpha\left(f_i,f_j,x_1,\dots,x_p,y_1,y_2\right)\stackrel{\mathrm{def}}=\begin{cases}
 f_i\left(x_1,\dots,x_p\right), &y_1=y_2\\
 f_j\left(x_1,\dots,x_p\right), &y_1\neq y_2
 \end{cases}
Operator \beta
For any i\in\{1,\dots,n\} and m_i\ge1
\beta\left(f_i,x_1,\dots,x_{m_i-1}\right)\stackrel{\mathrm{def}}=y
where y is the smallest ordinal number for which f_i\left(x_1,\dots,x_{m_i-1},y\right)=0
Operator \gamma
For any i\in\{1,\dots,n\} and m_i\ge1
\gamma\left(f_i,x_1,\dots,x_{m_i-1}\right)\stackrel{\mathrm{def}}=y
where y is the smallest ordinal number such that \forall z\in\mathbb N \left(f_i\left(x_1,\dots,x_{m_i-1},z\right)<y\right). Note that z 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 ===
 \begin{align}
 &\text{zero}\left(\right)=0\\
 \end{align}
This is a function that takes no arguments and returns the constant zero.
=== Successor ===
 \begin{align}
 &\text{succ}\left(x\right)=\gamma\left(f,x\right)\\
 &f\left(x,y\right)=x\\
 \end{align}
Function succ takes an ordinal as an argument and increments it by 1.
=== Predecessor ===
 \begin{align}
 &\text{pred}\left(x\right)=\beta\left(f,x\right)\\
 &f\left(x,y\right)=\alpha\left(\text{zero},\text{succ}\circ\left[\text{zero}\right],x,\text{succ}\left(y\right)\right)\\
 \end{align}
Function pred returns the predecessor of its argument. The function does not terminate if its argument has no predecessor.
=== ω ===
 \begin{align}
 &\text{omega}\left(\right)=\gamma\left(f\right)\\
 &f\left(x\right)=x\\
 \end{align}
Function omega takes no arguments and returns the smallest infinite ordinal \omega.
=== ω + 1 ===
 \begin{align}
 &\text{omegaPlus1}\left(\right)=\text{succ}\circ\left[\text{omega}\right]\\
 \end{align}
Function omegaPlus1 returns \omega+1.
=== 2ω ===
 \begin{align}
 &\text{2omega}\left(\right)=\gamma\left(f,\text{omega}\left(\right)\right)\\
 &f\left(x,y\right)=\alpha\left(g_1,g_2,x,y,y,0\right)\\
 &g_1\left(x,y\right)=x\\
 &g_2\left(x,y\right)=f\left(\text{succ}\left(x\right),\text{pred}\left(y\right)\right)\\
 \end{align}
Function 2omega returns 2\omega.
Category:Languages
Category:Uncomputable
Category:Unimplemented
Category:2020