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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): n\ge1 function definitions $ f_{1},\dots ,f_{n} $ such that for all Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): i\in\{1,\dots,n\}

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): f_i:\omega_1^{m_i}\to\omega_1

where Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): \omega_1 is the set of all countable ordinal numbers and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): m_i\ge0 is the arity of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): 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: Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): 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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): 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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): \circ
• Operator Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): \alpha
• Operator Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): \beta
• Operator Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): \gamma

Operator $ \circ $

For any Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): i,k\in\{1,\dots,n\} and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): j_1,\dots,j_k\in\{1,\dots,n\} such that Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): m_{j_1}=\dots=m_{j_k}=p for some Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): p

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): f_i\circ\left[f_{j_1},\dots,f_{j_k}\right]=g

where

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): 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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): \alpha

For any $ i,j\in \{1,\dots ,n\} $ such that Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): m_i=m_j=p for some Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): p

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): \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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): \beta

For any Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): i\in\{1,\dots,n\} and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): m_i\ge1

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

where Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): y is the smallest ordinal number for which Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): f_i\left(x_1,\dots,x_{m_i-1},y\right)=0

Operator Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): \gamma

For any Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): i\in\{1,\dots,n\} and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): m_i\ge1

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): \gamma\left(f_i,x_1,\dots,x_{m_i-1}\right)\stackrel{\mathrm{def}}=y

where Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): 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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): 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

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): \begin{align}    &\text{zero}\left(\right)=0\\  \end{align}

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

Successor

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): \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

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): \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.

ω

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): \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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): \omega .

ω + 1

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): \begin{align}    &\text{omegaPlus1}\left(\right)=\text{succ}\circ\left[\text{omega}\right]\\  \end{align}

Function omegaPlus1 returns $ \omega +1 $.

2ω

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): \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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): 2\omega .