Unhaltingfuck

From Esolang
Jump to navigation Jump to search

UnHaltingFuck 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 an UnHaltingFuck program that doesn't halt. The specific Gödel encoding is not specified since it doesn't affect any interesting properties of the language.

Computational Class

UnHaltingFuck is uncomputable. This can be shown as follows:

  • There exists an UnHaltingFuck program that halts (for instance, the empty program)
  • There exists an UnHaltingFuck program that doesn't halt (for instance, if the program encoded by the Gödel number 0 is the empty program, [])
  • Consider the subset of UnHaltingFuck programs in which cells take only one of two values, which are the Gödel numbers of those two programs. That is, whenever a + or - is used it is immediately followed by enough +s or -s to bring the value in the current cell to one of those values. This language can be trivially translated to and from Boolfuck, which is known to be Turing-Complete.
  • Since there exists a Turing-Complete subset of UnHaltingFuck, the question of whether an UnHaltingFuck loop runs or not is uncomputable in general.

HaltingFuck

UnHaltingFuck implies a sister language, Haltingfuck, whose loops stop when the value in the current cell is the Gödel number of a HaltingFuck program that halts. This language is computable and sub-Turing-Complete.