Zero

Zero is a language invented by Tailcalled. It was specifically designed to be literally impossible to program in and execute in the general case.

Zero has eight instructions, the same as in Brainfuck. To each instruction, a three-bit sequence is assigned:

Instruction	Bit Sequence	Brainfuck Character
Increment	000	+
Decrement	001	-
Next	010	>
Previous	011	<
Loop (begin)	100	[
Loop (end)	101	]
Output	110	.
Input	111	,

A sequence of such bit-triples with correct grammar will be called a pseudo-program.

Such a pseudo-program is turned into a Zero-program by pointwise xoring with the Halting sequence. The Halting sequence is defined as follows: the nth bit of the Halting sequence is 0 iff the nth pseudo-program (ordered first by length, then by lexicographic order of their binary sequences) halts when given an infinite stream of zeroes (null character, frequently written as \0) as input.

The following problems are equivalent to the Halting problem:

• Transliterating between Brainfuck and Zero
• Executing arbitrary Zero programs

The following problems are conjectured to be uncomputable:

• Determining if a Zero program is grammatically correct.
• Translating Brainfuck programs to Zero, possibly changing which instructions are executed (but not changing the observable effects)

Examples

Hello, World!

The example program on the Brainfuck page is 106 bytes long; we need to calculate the first 318 bits of the Halting sequence to convert it to Zero. The first 318 pseudo-programs are enumerated here: the entries marked with an asterisk trivially loop forever, and all other programs can be tested to halt. Thus bits 68, 105, and 302 are 1, and all others are 0. We XOR the first 318 bits of the Halting sequence together with the brainfuck program:

000000000000000000000000100010000000000000100010000000010000000000010000000000010000011011011011001101010000010000010001010010000100011101011001101010010110010001001001110000000000000000000000110110000000000110010010110011001110011110000000000110001001001001001001110001001001001001001001001110010010000110010000000110
000000000000000000000000000000000000000000000000000000000000000000001000000000000000000000000000000000000100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001000000000000000
==============================================================================================================================================================================================================================================================================================================================
000000000000000000000000100010000000000000100010000000010000000000011000000000010000011011011011001101010100010000010001010010000100011101011001101010010110010001001001110000000000000000000000110110000000000110010010110011001110011110000000000110001001001001001001110001001001001001001001001110010010001110010000000110

Computational class

Although the halting sequence is uncomputable, many of its bits can still be calculated, in particular the first 100000 are known, see external resources below.

Since there are brainfuck self-interpreters much shorter than this, e.g. Dbfi, it is possible to practically implement at least one Turing complete language in Zero, which by some definitions makes it itself Turing complete.

External resources

• A list of non-halting pseudo-programs and their indices in the Halting sequence (up to n=100000) can be found here.