Halting problem

This article is not detailed enough and needs to be expanded. Please help us by adding some more information.

I know nothing but my own ignorance.

-- Socrates

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.

1

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, halts 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.

2

There's actually another way to counter it, and you don't even need that program to put it in.

First, suppose that there is an algorithm that calls halts(p).

Then we build up a infinite loop:

void forever()
{
    forever;
}

And then we build up a program called "G":

void G()
{
    if (halts(G))
    {
        forever();
    }
    else
    {
        return;
    }
}

In program G, we call the halts() algorithm to determine whether G will be halt. If it halts, call the forever() program and let it run forever. But this just shows that G will not be halt, so halts(G) should be false, and we will halt at this time. But this just shows that halts(G) should be true, so ...... We're stuck in an endless loop. That is, whether halts (G) is true or not, we arrive at a contradictory conclusion. Therefore, our initial assumption is not true, that is, there is no universal algorithm that can determine whether any program can be halt (at least on a Turing-complete programming language).

Summary

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.