Halting problem

From Esolang

This article is a stub, which means that it is not detailed enough and needs to be expanded. Please help us by adding some more information.

The halting problem is to determine, given a program and its input, whether the program will halt or loop forever. On Turing machines, which have no constraints on memory, the halting problem can be shown to be unsolvable. The same is thus true for any Turing-complete programming language, such as Brainfuck.

The halting problem is however solvable for finite state machines: whenever a state change occurs, you compare the new state of the FSM against all previous states. If you find a match, the program will not halt. Since the machine has a finite number of states, it is guaranteed to either halt or return to a previous state at some point. This is how the Smallfuck to lookup table compiler works.