Halting problem

From Esolang
Jump to: navigation, search
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 proof is actually relatively simple. It can be done by proof of negation.

Suppose that there is an algorithm that can decide if other programs, given certain inputs, will end or not. Let's use a C-like syntax, for demonstration purposes. Say that this algorithm is a function declared like so:

bool doesHalt(program, input) {
    //How the program and its arguments are represented doesn't actually matter.
    ...
}

Now let's say we have another function that takes a program as input, like so:

void selfLoop(program) {
    if (doesHalt(program, program)) {
        infiniteLoop();  //Doesn't matter what happens in this function, just that it will never end
    }
    else {
        return;
    }
}

If the program, passed as an argument, loops forever when given itself as input, then selfLoop will loop forever. Otherwise, it will end.

Here's the kicker. What happens if we do this?

selfLoop(selfLoop);

Inside that function call, we'll see doesHalt(selfLoop, selfLoop) be run. That statement will return whether or not selfLoop(selfLoop) runs forever when given itself as input. So if selfLoop(selfLoop) eventually halts, selfLoop(selfLoop) should run forever.

Wait, what? That can't be right. We've come upon a contradiction, a statement that cannot be true. Thus, the halting problem cannot be solved for Turing machines.

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.