The Language That Explodes

The Language That Explodes, created by User:ais523 in 2021, is intended to create interesting conceptual problems about computability classes, whilst being entirely useless in practice. It is Turing-complete in the sense that for every program with input and output in any Turing-complete language, there is some corresponding program in The Language That Explodes that maps the same inputs to the same outputs; however, it is usually uncomputable to determine what that program is (in fact, the language has decidable haltability).

One way to think about it is that the language itself is computable, but the language uses an uncomputable encoding.

Definition

A program in The Language That Explodes consists of a string of 1s, followed by a string of 2s.

• The string of 1s is a Unary program.
• The length of the string of 2s must be a solution to the Busy Beaver problem for Unary; specifically, its length must be equal to the maximum number of brainfuck commands that run during the execution of any halting Unary program that's no longer than the string of 1s.

If the string of 2s has the correct length, then the The Language That Explodes program behaves the same way as the Unary program that is formed by the string of 1s.

If the string of 2s has an incorrect length, this is undefined behaviour.

Computational class

Being able to compile arbitrary Unary programs into The Language That Explodes requires solving the halting problem for Unary, which is impossible. The compilation does conceptually exist, but there is no way to find it. Despite the uncomputable nature of writing a program in The Language That Explodes (with the exception of a few simple programs), executing a program is trivially easy, thanks to the undefined behaviour if the string of 2s is incorrect – you can just ignore it and write a Unary interpreter.

The halting problem for The Language That Explodes is trivially easy to solve – simply run the Unary program for a number of brainfuck commands equal to the given number of 2s. If it doesn't halt in that time, it can't halt at all.

A side effect of all this (and the fact that inspired the language) is that The Language That Explodes has a Busy Beaver function that grows (slightly) sub-linearly.