User:Orisphera/Completeness

User:Orisphera finds the definitions for Turing completeness that they've found vague. This page shows the definition that they think best matches the examples they've found and some other definitions.

What is a programming language?

Orisphera has many non-equivalent definitions for the term "programming language." They differ by several parameters.

All of these definitions require a set of possible inputs as a part of the language. Some languages have split input, i.e., one consisting of two parts, called the program and the main input.

Languages can be never halting or sometimes halting. Technically, you can describe never halting languages as sometimes halting ones that never halt; the difference is that the definition of sometimes halting languages allows them to halt.

Languages can be interactive and non-interactive. Interactive languages can get input while running, and for non-interactive languages, all input is fixed on start. For interactive languages with split input, the program is fixed, and only the main input can be supplied at runtime.

Languages can have sequential output, output on halt, or no output at all. Never halting languages with output on halt and no output are the same.

Black box programming languages are functions that take an input as the argument and return the output and whether it halts. (Note that they don't have to be computable as functions to be computable.) Never halting languages, as the name suggests, never halt.

Languages with sequential output can give output that is infinite to the right if they don't halt. Languages with output on halt only return output if they halt. Languages with no output return no output at all. That means that only one never halting non-interactive black box language with no output exists for every input set.

In order to describe some models, they had to come up with the definition for iterative programming languages.

Iterative programming languages consist of three parts: the input function, the step function, and the output function. It also has a set of states. The input function takes the input as the argument and converts it to a machine state. The step function takes a state as the argument and returns another state. The output function takes a state as the argument and returns:

• For languages with sequential output - the (maybe empty) output, which is all concatenated together to get the final output, and whether it should halt on this step.
• For languages with output on halt - the output or a special value (probably the set of possible outputs) meaning that it doesn't halt on this step.
• For languages with no output - whether it should halt on this step.
• For never halting languages with sequential output - the (maybe empty) output, which is all concatenated together to get the final output.
• Never halting languages with no output or output on halt (which are, as stated above, the same) don't have the output function.

To run an iterative programming language, you first evaluate the input function for the given input and then apply the step function to the previous result until the output function for it returns a value that says that the program should halt. For never halting PLs, you apply it forever.

Interactive languages also have interactive input and can be though of as always having split input. Interactive iterative PLs take a piece of interactive input as an additional argument for some states. Black box interactive languages take (a prefix of) the interactive input as an additional argument, and their output is the concatenation of the output for all the prefixes, from the shortest (length 0) to the longest. If it halts for some interactive input, it should halt without output for all the interactive inputs that have it as a proper prefix. Interactive PLs can be executed with a function (interactor) that gives it interactive input depending on its past output. They can't rely on a specific interactor to be complete; they have to work for all interactors.

Definitions for completeness

TCbRED

TCbRED is the only definition here that matches all the examples Orisphera has seen and, in particular, the 2-state 3-color universal never halting Turing machine.

It uses the term "simple (function)." Orisphera doesn't know exactly what it is, but there are some axioms that they assume it follows.

An iterative programming language is computable iff all the function it's made of are simple. A computable iterative PL is TCbRED iff its step function can be used in a language equivalent to any computable iterative PL.

Note that this definition relies on how the language works. This is required to consider never halting languages with no output.

Full completeness

Orisphera has two equivalent definitions for computable black box languages: ones that are equivalent to a computable iterative programming language, and ones that have an interpreter in a reference fully complete language. You can use bf as a reference fully complete language.

Orisphera calls a computable (as a BBL) language L with split input fully complete if you can get any computable language with the same output set and the input set equal to the main input set of L by setting its program to a constant value.

Completeness by halting

Orisphera calls a sometimes halting language complete by halting if there are computable functions to translate it into a reference complete by halting language and vice versa in any way that translates halting programs into halting programs and vice versa. You can use bf or TM as a reference complete by halting language.