This is a cops-and-robbers challenge based around defining languages and proving they are Turing complete.
This is the cops' thread. The robbers' thread is here.
As a cop, you will prepare two things:
A formal specification of a programming language, or other computational system. (Computational systems are defined below.)
A proof that your system is Turing complete, according to the somewhat strict definition below.
You will post your specification of your language, and the robbers will try to "crack" it by proving its Turing completeness. If your submission is not cracked within one week you can mark it as safe and post your proof. (Your answer can be invalidated if someone finds a flaw in your proof, unless you can fix it.)
This is a popularity-contest, so the winner will be the answer that has the most votes, and which is not cracked or invalidated. The challenge is open-ended - I won't be accepting an answer.
For the sake of this challenge, a computational system will be defined as four things:
A "program set"
P. This will be a countably infinite set, e.g. strings, integers, binary trees, configurations of pixels on a grid, etc. (But see the technical restriction below.)
An "input set"
I, which will also be a countably infinite set, and need not be the same set as
P(although it can be).
An "output set"
O, which similarly will be a countably infinite set, and may or may not be the same as
A deterministic, mechanistic procedure for producing an output
oare members of
Orespectively. This procedure should be such that it could, in principle, be implemented on a Turing machine or other abstract model of computation. The procedure may, of course, fail to halt, depending on the program and its input.
O must be such that you can express them as strings in a computable manner. (For most sensible choices this will not matter; this rule exists to prevent you from choosing strange sets, such as the set of Turing machines that don't halt.)
Turing completeness will be defined as the following:
- For any computable partial function
O, there exists a program
Psuch that given
i, the output is
f(i)has a value. (Otherwise the program doesn't halt.)
The word "computable" in the above definition means "can be computed using a Turing machine".
Note that neither rule 110 nor bitwise cyclic tag are Turing-complete by this definition, because they don't have the required input-output structure. Lambda calculus is Turing complete, as long as we define
O to be the Church numerals. (It is not Turing-complete if we take
O to be lambda expressions in general.)
Note that you don't have to provide an implementation of your language, but you are welcome to include one in your answer if you like. However, you shouldn't rely on the implementation to define the language in any way - the spec should be complete in itself, and if there is a contradiction between the spec and the implementation this should be treated as a bug in the implementation.