Are There Problems That Computers Can't Solve?

Are there

problems

that

computers

can't

solve

? Even if you work with the smartest programmers, even if you have infinite time and energy and more computing power than could ever exist in the universe, are there some things that will always be impossible for a computer to

solve

? The short answer is yes! The long answer would be an entire series of introductory computer science lectures. The fairly short answer that I hope I haven't oversimplified... is the rest of this video. One of the best things about old

computers

like these BBC Micros was that the operating system, the first thing you got when you turned them on, was also a place where you could just write code.

So if you were a clerk selling these in the '80s, you'd have to be careful when the kids were out of school, because while you were distracted, some nerd might come in and quietly write something like this. And suddenly, your screen model was endlessly typing something rude until you hit the "pause" key or turned the computer off and on. This is a really simple example of a program that will never stop. And it's deliberately written that way. But programs that never stop can also be written accidentally: we've all had that moment when something we're working on freezes, stuck in an endless loop doing... something?

And you have that horrible moment of trying to remember if you saved recently or not. It would be brilliant to be able to look at the code, any code, and say definitively: "yes" it will eventually stop or "no" there is a point where it will keep repeating forever, if this happens. Which seems like a simple problem. It's actually impossible. Literally, mathematically, impossible. And the way we discovered that comes from before electronic computers were invented. At the beginning of the 20th century, a mathematician named David Hilbert posed a series of

problems

that, in his opinion, mathematics should be able to answer.

One of them became known as... ...the, uh... the "Decision Problem." Which is, in short: "Can we determine whether a given statement"—that is, absolutely any logical statement or problem in the universe—"is provable or unprovable?" 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 the proof of it, we must first look at the tool. As he often did, Turing sought the mechanization of logic and computation. A “computer,” at this point, was not something electronic, it was a job description, people sitting in rooms doing specific calculations over and over again.

Over and over again, they were called computers. Because Turing was fascinated by the idea of ​​automating that process. The dream was that if everything could be encoded in numbers and if we had mechanical methods of working with those numbers, then, perhaps, 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, first of all: of a tape that, thanks to this, would exist in the land of hypothetical magical philosophy. 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 you have a state register and a table of instructions, which in modern terms is the code. There are a lot of complicated things I'm overlooking about how it all works, but in short: it's some code. The machine follows that code, which may include instructions such as "move left," "move right," "change what's on this piece of tape," or "read what's on this piece of tape." , and what instructions can be used. Depends on what those pieces of tape say. Finally, the Turing machine reaches the end of its instructions and stops. Or go into an endless loop. It was, basically, the smallest computer possible.

But it turns out that so are all computers. Any program you write in any programming language can be turned into something that can run on a Turing machine. So, using that machine, Turing reformulated the decision problem: "Can we determine whether a given program will stop or not?" Same question, asked differently. Will the machine find a solution, prove a claim, or continue to run forever? Remember, the big question we're trying to answer is: Are there any questions that a computer can't solve? So Turing proposed a series of steps. And yes, I know, looking at computer scientists, this is a deliberate simplification, I know there are a lot of subtle things I'm leaving out.

But Turing proposed a series of steps. First: Let's imagine we create a Turing machine, a program, that can look at some code and determine whether that program will stop. 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, "It stops." "Halts" takes the code of a program as input and generates one of two responses: "Yes", that program stops. Or "No," repeats forever. So far so good, right? So, let's screw another machine, another program, at the end of "Stops." And depending on the outcome of "Halts," he'll do one of two things.

If "Stops" generates "yes", knowing that the program you entered will eventually stop, then that machine goes into an infinite loop. Maybe just print something rude over and over again. And if Halts returns 'no', if Halts calculates that the code we entered will repeat forever, then this new machine simply stops. Well? So if Halts reads the code and says "that will stop" then the new machine loops. If Halts says a program will repeat, the new machine stops. We'll put a box around both of them and call this new machine "Opposite." Because it does the opposite of any code you enter.

With all that setup, this is where Turing springs the trap. He proposes that we take this new combined program. On the opposite side, let's take his code and introduce your own code to it. What will he do? Let's review the logic. If he thinks the answer is: this code will stop, then it will be repeated. But then the answer is: it will repeat itself. Then it will stop. But then it will stop. Then it will repeat. But then, it will be… daaagh. And it vanishes in a breath of logic. To be clear, that's not a loop per se.

That is a paradox. That is a logical and mathematical impossibility. And that is Turing's answer to the decision problem. If he ever has a program that he can determine, with certainty, whether a particular program will stop or repeat, he can easily modify it a little bit, let it contradict itself, and cause that paradox. And that is impossible. So there can't be a program to do that. Which means there is definitely an exception, there is definitely at least one thing that computers can never solve, even with infinite time and power. The answer to the decision problem, the answer to the question “Can we determine whether each program will stop or not?” it's not.

Now, there are obviously many programs where you can easily tell at a glance whether they will stop or not. This code will repeat forever. This code will exit and stop. The decision problem is not about knowing whether some programs will be stopped or repeated. That is easy. It's about each program. It comes down to the fundamental fact that there are definitely some things that computers will never be able to solve. Which was 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 presented to them, if given enough time.

But even before the first digital computer existed, Alan Turing had discovered that they still have limits.