Undyne Programming Language Turing-completeness Proof

As of 8 April 2025, the Undyne Programming Language has been mistakenly categorize as a Finite state automata. This page has been made to prove that UPL is in fact Turing-complete.

Definitions

• The user is the entity which produce UPL code.
• The memory is a list of cells. The cells contain a byte of undefined length (32 bits by default).
• An arrow is an operation, as defined on the UPL's wiki page (Undyne Programming Language).

Tape

A Turing machine operates with an infinite tape where data is stored. Similarly, UPL also uses a tape (memory) that is 64 units in size by default, but this size can be adjusted by the user. This flexibility means that, theoretically, UPL can have infinite memory because there is no upper limit on the size of the memory.

Let's denote the size of the memory as defined by the user as x, where x is a natural number (x ∈ ℕ).

For any given size x, there exists a size x + 1. This means we can define a function f(x) such that f(x) = x + 1.

As x approaches infinity, the function f(x) also approaches infinity. Mathematically, this is expressed as:
lim_x→∞ ​f(x) = lim_x→∞ ​( x + 1 ) = +∞

Since lim_x→∞ ​f(x) is +∞, the maximum memory size definable by a user is effectively infinite. Even though the base state of the memory is 64 units, it is not constrained by this number or any other fixed limit and can theoretically be set without bound.

Head

As any Turing machine, UPL have an "head" which can write and "move" the tape. This is manifested in UPL with a pointer, which point to the current memory cell and can be moved with > and < arrows.

State register

A UPL program (Quiver file) is a list of "states" which will be applied to the memory. They are at first defined in the Head file, then ordered in the Quiver file.

Finite table of instructions

UPL contain a finite number of predefined instructions (see arrows creation section). These instructions can be set or not, used or not by the user.

Conclusion

As UPL uses the same instruction set as and expands the instruction set of Brainfuck, which is Turing complete; as UPL contains all the properties of a Turing machine; UPL is itself Turing complete.