Transfinity

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 $n\geq 1$ 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}\geq 0$ 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\leq j\leq 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}\geq 1$

$\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}\geq 1$

$\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{aligned}&{\text{zero}}\left(\right)=0\\\end{aligned}}$

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

Successor

${\begin{aligned}&{\text{succ}}\left(x\right)=\gamma \left(f,x\right)\\&f\left(x,y\right)=x\\\end{aligned}}$

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

Predecessor

${\begin{aligned}&{\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{aligned}}$

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

ω

${\begin{aligned}&{\text{omega}}\left(\right)=\gamma \left(f\right)\\&f\left(x\right)=x\\\end{aligned}}$

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

ω + 1

${\begin{aligned}&{\text{omegaPlus1}}\left(\right)={\text{succ}}\circ \left[{\text{omega}}\right]\\\end{aligned}}$

Function omegaPlus1 returns $\omega +1$.

2ω

${\begin{aligned}&{\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{aligned}}$

Function 2omega returns $2\omega$.