Are There Problems That Computers Can't Solve?

Den Den 12 May 2020
Are There Problems That Computers Can't Solve?

Are there problems that computers can’t solve? Even if you work with the cleverest programmers, even if you have infinite time and energy and more computing power than could possibly ever exist in the universe, are there some things that it will always be impossible for a computer to work out? The short answer is: yes! The long answer would be an entire lecture series in introductory computer science. The fairly short answer that I hope I haven’t simplified too much… is the rest of this article.

One of the great things about old computers was that the operating system, the first thing you got when you switched them on, was also somewhere that you could just write code. So if you were a shop assistant selling these in the 80s, you would have to watch out when the kids weren’t in school, because while you were distracted, some nerd could slip in and quietly type in something like this.

> 10 PRINT "Something rude"
> 20 GOTO 10
> RUN

And suddenly your display model was endlessly typing out "Something rude" until you hit the ‘break’ key or turned the computer off and on again. That is a really simple example of a program that will never halt. And it is deliberately written that way.

But programs that never halt can also be written accidentally: we’ve all had that moment where something we’re working on freezes, stuck in an endless loop doing... something? And you have that horrible moment of trying to remember whether you saved recently or not. It would be brilliant to be able to analyze code, any code, and say definitively: "yes", eventually it’ll halt or "no", there’s a point in there where it’ll keep looping forever, if this happens. Which sounds like a simple problem. It’s actually impossible. Literally, mathematically, impossible. And how we found that out comes from before electronic computers were even invented.

In the early twentieth century, a mathematician named David Hilbert posed a series of problems that he thought mathematics should be able to answer. One of them came to be known as the “Decision Problem.” Which is, in short: "Can we determine if any given statement”, meaning absolutely any logical statement or problem in the universe, “is provable or non-provable?” Given enough time, could we find an answer to everything?

Hilbert was optimistic that the answer would be yes. Other mathematicians proved him wrong. One of those mathematicians was Alan Turing. And to explain his proof, we first need to look at the tool that he used to make it.

Turing was looking at the mechanization of logic and computation. A “computer”, at this point, wasn’t an electronic thing, it was a job description, people who sat in rooms doing specific calculations over and over and over, they were called computers. Because they computed. Turing was fascinated by the idea of automating that process. The dream was if everything could be encoded into numbers and if we had mechanical methods for working with those numbers, then, maybe, anything could be solved.

He came up with a hypothetical calculating machine, which ended up being named after him. A Turing Machine would be made of, first: a tape. This tape would be, thanks to this existing in magical hypothetical philosophy land, infinitely long, and divided into cells. In modern terms, that’s computer memory.

Next, a read-write head, which can move left or right over that tape, reading what’s there or changing it. Then it has a state register and a table of instructions, which in modern terms are the code.Are There Problems That Computers Can\'t Solve?

There’s a lot of complicated stuff that I’m glossing over there about how it all works, but in short: it’s some code. The machine follows that code, which might include instructions like “move left”, “move right”, “change what’s on this bit of the tape”, or “read what’s on this bit of the tape”, and which instructions are used can depend on what those bits of tape say.

Eventually, the Turing machine reaches the end of its instructions and it halts. Or it enters an endless loop. It was, basically, the minimum possible computer. But it turns out it’s also every computer. Any program that you write in any programming language can be converted into something that can run on a Turing machine.

So using that machine, Turing restated the Decision Problem: "Can we determine if any given program will halt or not halt?" Same question, phrased differently. Will the machine find a solution, prove a statement, or will it keep running forever? Remember, the big question that we’re trying to answer is: is there any question that a computer cannot solve?

So, Turing proposed a series of steps. And yes, I know, this is a deliberate simplification, I know there are lots of subtle things I’m skipping over. But: Turing proposed a series of steps.

First: imagine that we come up with a Turing machine, a program, that can look at some code, and figure out if that program will halt. At this point we don't need to know how that machine actually does it, let’s just assume that it works somehow. Let's call this machine, this program, "Halts". "Halts" takes the code for a program as its input, and outputs one of two answers: “Yes”, that program halts. Or “No”, it loops forever. So far, so good, right?

So, we’re going to bolt another machine, another program, on the end of “Halts”. And depending on the output from “Halts”, it’ll do one of two things. If “Halts” outputs ‘yes’, knowing that the program you've fed in will eventually stop, then that machine goes into an infinite loop. Maybe it just prints something rude over and over. And if Halts outputs a 'no', if Halts works out the code we’ve fed in would loop forever, then this new machine just halts. Okay? So if Halts reads the code and says “that’ll halt”, then the new machine loops. If Halts says a program will loop, the new machine halts. We'll put a box around both of those and call this whole new machine "Opposite". Because it does the opposite of whatever code you feed in.

With all that set up, here’s where Turing springs the trap. He proposes that we take this new combined program, Opposite, we take its code, and we feed its own code into itself. What will it do? Let's step through the logic. If it thinks the answer is: this code will halt, then it will loop. But then the answer is: it’ll loop. So it’ll halt. But then it’ll halt. So it’ll loop. But then, it’ll… daaagh. And it vanishes in a puff of logic. To be clear, that’s not a loop in itself. That’s a paradox. That’s a logical, mathematical impossibility. And that is Turing’s answer to the Decision Problem. If you ever have a program that can determine, for certain, whether any particular program will halt or loop, you can easily tweak it a little, let it contradict itself, and cause that paradox. And that’s impossible. So, a program to do that can not exist.

Which means there is definitely an exception, there is definitely at least one thing that computers cannot ever solve, even given infinite time and power. The answer to the decision problem, the answer to the question “Can we determine if every program will halt or not halt?” is: no.

There are obviously a lot of programs where you can easily tell at a glance if they’ll halt or not. This code will loop forever. This code will exit and halt. The Decision Problem isn’t about whether you can tell if some programs will halt or loop. That's easy. It’s about every program. It’s about the fundamental fact that there are definitely some things that computers cannot ever possibly solve. Which came as a blow to those mathematicians like David Hilbert who believed that pure mathematics had the ability to solve anything. Computers seemed like amazing machines that could calculate any problem thrown at them, if given enough time. But even before the first digital computer existed, Alan Turing had worked out that they do still have limits.

Comments (0)

    No comments yet

You must be logged in to comment.