# 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 $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) . 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$ .