Haltingfuck

From Esolang
Jump to navigation Jump to search

HaltingFuck is a language very much like Brainfuck, with one key difference: instead of loops stopping when the value in the current cell is zero, they stop when the value in the current cell is the Gödel number of a HaltingFuck program that halts. The specific Gödel encoding is not specified since it doesn't affect any interesting properties of the language.

Computational Class

Perhaps surprisingly, HaltingFuck is computable. While it's very easy to write a HaltingFuck program that halts (for instance, the empty program), in order to write a HaltingFuck program that doesn't halt it is necessary to first write a HaltingFuck program that doesn't halt. This is because any HaltingFuck program that doesn't halt must contain at least one loop that starts with the current cell containing the Gödel number of a non-halting program. Since it is impossible to construct a non-halting program, every loop in a HaltingFuck program runs exactly zero times, and since every loop in a HaltingFuck program runs exactly zero times, it is impossible to construct a non-halting program.

UnHaltingFuck

HaltingFuck implies a sister language, Unhaltingfuck, whose loops stop when the value in the current cell is the Gödel number of an UnHaltingFuck program that doesn't halt. This language is uncomputable.