Transfinity

Paradigm(s) Functional User:Hakerh400 2020 Uncomputable Unimplemented .txt

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

Overview

Source code consists of ${\displaystyle n\geq 1}$ function definitions ${\displaystyle f_{1},\dots ,f_{n}}$ such that for all ${\displaystyle i\in \{1,\dots ,n\}}$

${\displaystyle f_{i}:\omega _{1}^{m_{i}}\to \omega _{1}}$

where ${\displaystyle \omega _{1}}$ is the set of all countable ordinal numbers and ${\displaystyle m_{i}\geq 0}$ is the arity of ${\displaystyle 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: ${\displaystyle f_{i}(x_{1},\dots ,x_{m_{i}}){\stackrel {\mathrm {def} }{=}}0}$
• Projection function: ${\displaystyle f_{i}(x_{1},\dots ,x_{m_{i}}){\stackrel {\mathrm {def} }{=}}x_{j}}$ for some ${\displaystyle 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 ${\displaystyle \circ }$
• Operator ${\displaystyle \alpha }$
• Operator ${\displaystyle \beta }$
• Operator ${\displaystyle \gamma }$

Operator ${\displaystyle \circ }$

For any ${\displaystyle i,k\in \{1,\dots ,n\}}$ and ${\displaystyle j_{1},\dots ,j_{k}\in \{1,\dots ,n\}}$ such that ${\displaystyle m_{j_{1}}=\dots =m_{j_{k}}=p}$ for some ${\displaystyle p}$

${\displaystyle f_{i}\circ \left[f_{j_{1}},\dots ,f_{j_{k}}\right]=g}$

where

${\displaystyle 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 ${\displaystyle \alpha }$

For any ${\displaystyle i,j\in \{1,\dots ,n\}}$ such that ${\displaystyle m_{i}=m_{j}=p}$ for some ${\displaystyle p}$

${\displaystyle \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 ${\displaystyle \beta }$

For any ${\displaystyle i\in \{1,\dots ,n\}}$ and ${\displaystyle m_{i}\geq 1}$

${\displaystyle \beta \left(f_{i},x_{1},\dots ,x_{m_{i}-1}\right){\stackrel {\mathrm {def} }{=}}y}$

where ${\displaystyle y}$ is the smallest ordinal number for which ${\displaystyle f_{i}\left(x_{1},\dots ,x_{m_{i}-1},y\right)=0}$

Operator ${\displaystyle \gamma }$

For any ${\displaystyle i\in \{1,\dots ,n\}}$ and ${\displaystyle m_{i}\geq 1}$

${\displaystyle \gamma \left(f_{i},x_{1},\dots ,x_{m_{i}-1}\right){\stackrel {\mathrm {def} }{=}}y}$

where ${\displaystyle y}$ is the smallest ordinal number such that ${\displaystyle \forall z\in \mathbb {N} \left(f_{i}\left(x_{1},\dots ,x_{m_{i}-1},z\right). Note that ${\displaystyle 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

{\displaystyle {\begin{aligned}&{\text{zero}}\left(\right)=0\\\end{aligned}}}


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

Successor

{\displaystyle {\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

{\displaystyle {\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.

ω

{\displaystyle {\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 ${\displaystyle \omega }$.

ω + 1

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


Function omegaPlus1 returns ${\displaystyle \omega +1}$.

2ω

{\displaystyle {\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 ${\displaystyle 2\omega }$.