I have previously mentioned the halting problem – a well-known problem in computer science and mathematics. I claimed that there is a language in which an algorithm that solves the halting problem can be constructed. If we assume that any given algorithm either halts or will run to infinity, then we can construct this simple algorithm:
1. Take an algorithm from input.
2. If it halts, return yes.
3. Otherwise, return no.
It’s a simple algorithm that returns “yes” if a given algorithm halts, and “no” if it doesn’t. But it what language is it written? In English. It requires the knowledge whether a given algorithm will halt. As we assumed, such a knowledge exists, but it has been proved that there is no deterministic algorithm (for Turing machines) that can contain such a knowledge. We can conclude that if this knowledge indeed exists, it is not computable, and therefore can’t be expressed in a finite number of bits (or computer files).
Suppose we try another approach:
1. Take an algorithm from input.
2. Run it one step at a time – either until it halts, or let it run infinite steps.
3. If it halts, return yes.
4. Otherwise, return no.
This algorithm would seem to work and return a correct answer for algorithms that halt, but it might get stuck in an infinite loop for algorithms that don’t halt. But if we allow it to run on a computer that can run infinite steps in finite time – it will always stop and return a correct answer. But the problem is – there is no such a computer.
But there are no Turing machines, either. A Turing machine has infinite memory. Since it has infinite memory, some programs might run for infinite time. In reality – no computer has infinite memory, and no computer program will run for infinite time (somebody will eventually turn off the computer). So lets forget about Turing machines, and check if we can solve the halting problem for real computers.
Real computers have a finite amount of memory. If we are given a real computer and an algorithm that runs on it – is it possible to determine whether this algorithm, when run on the real computer, will ever halt?
Of course it is! let n be the number of bits in this real computer’s memory – so the total number of different states the computer can be in is 2n. If a computer program hasn’t stopped after 2n steps, then it is stuck in an endless loop and will run forever. So I will revise my algorithm a little:
1. Take an algorithm from input.
2. Run it one step at a time – either until it halts, or let it run 2n steps.
3. If it halts, return yes.
4. Otherwise, return no.
This program will always stop and return a correct answer, although it might take a long time. It will also need to use a different computer (or virtual computer) to count the number of steps it is running, and this might take another n bits of memory as well. But I’m not trying to be efficient here. I’m trying to prove that this problem can be solved. And it can be solved.
So what can’t be solved? The question of whether algorithms halt on a Turing machine can’t be solved. The halting function (return yes for any algorithm that halts; no for any algorithm that doesn’t) can’t be computed. The corresponding number can’t be defined in the computer machine language. If there is such a knowledge, it can’t be expressed. Some things we are just not able to know.
But remember – we also don’t know if the googleth bit of the square root of 2 is 0 or 1 – and it is computable (at least in theory, on Turing machines). If something is theoretically computable, it still doesn’t mean that it can be computed in reality and within reasonable time. We just have to accept that some things we are not able to know. It would be boring if we knew everything. If we did, we would have nothing to learn.