It’s bad enough we can’t know everything about the physical universe, even with more advanced technology.[1] Surely we can escape any such limits in the realm of logic and math, can’t we? Surprisingly, no, we still have unknowable things in logic, at least related to math and computation.
A few decades ago, I had heard about a few unsolved math problems. For example, at that time there was no formal proof for or against Fermat’s last theorem.[2] I figured that any unsolved math problems are solvable but just had not been solved yet. After all, humanity continues to learn new things about math just like in other fields. Sure enough, I later found out that Fermat’s last theorem has in fact been proven. But we’ll solve the others too, won’t we?
I’m surprised to find so many unsolved math problems listed in a Wikipedia article.[3] That “list” article actually has a list of lists of unsolved problems among the individual problems. At least the article also lists some problems that have been solved. That’s encouraging. Are the rest just a matter of time?
Also a few decades ago, I learned about the halting problem from theoretical computer science.[4] The halting problem basically proposes the task of finding a deterministic algorithm that can tell whether any possible given program (in a certain abstract programming language) will halt with an answer for a given input or will run forever. A deterministic algorithm is a logical, nonrandom, step-by-step procedure for performing some kind of computation. The intended result of that computation could be a number or yes/no or something else. So the halting problem involves creating such a step-by-step procedure to evaluate an arbitrary computer program, returning yes or no as to whether the given program would halt (with an answer) for a given input. The problem is being able to do this for any possible program, as in all possible programs.
Though having such an algorithm would really be nice, the intended goal of the problem itself was probably more to determine what is possible. In 1936, computer scientist Alan Turing proved that the halting problem is undecidable. That means it is not possible to create such a procedure to decide about the run/halt nature of any possible computer program, written in a suitable programming language. If we want an automatic way to evaluate any possible program for the ability to halt with a correct answer for a given appropriate input, that’s too bad. It’s impossible.
How bad is it really? The programming language used in the halting problem is assumed to be capable of implementing any possible computation. Such a programming language is called Turing complete, and nearly all modern programming languages meet that definition.[5] So we can’t have a fixed solution for determining whether arbitrary given software will function correctly for any given input. We may be able to create a program to correctly evaluate the correctness of other programs with some limitation, like a limited number of instructions, but there will always be programs possible that fall out of that category. Even if we had unlimited computing resources, we could not create such an automated program for evaluating all possible programs. Even the step-by-step procedure to perform such an evaluation is impossible.
I suppose in a way, this isn’t that surprising. Software is said to be one of the most complex creations of humankind. How can you prove that something so complex functions correctly? The famous Dutch computer scientist Edsger Djikstra said you can only prove the existence of bugs, not their absence.[6] And that was apparently back in 1969. Since then, both hardware and software have become much more complex. It brings no comfort to think that there is no way to construct at some point in time an automated means of checking the correctness of all future software. No matter how good the technology is at that time, programs can (eventually) be written that the technology cannot properly evaluate. The undecidability of the halting problem places a limit on what we can know about the correctness of software at a given time.
Fortunately, an imperfect solution can be good enough. Detecting computer viruses is said to be at least comparable to the halting problem if not equivalent or harder.[7] As a result, antivirus software can’t detect 100% of all computer viruses, but it can try to detect the most common ones and maybe the riskiest ones of today. Security software that is imperfect but good, is better than security software that is perfect but nonexistent (due to being impossible). Our imperfect antivirus software of today might seem to “take forever” when scanning the system or even just one file, we should feel at least a little lucky, since supposedly perfect antivirus software actually could take forever. Nonetheless, some things can’t be computed.
[1] https://oddstem.com/2019/07/12/the-physically-unknowable
[2] https://en.wikipedia.org/wiki/Fermat%27s_Last_Theorem
[3] https://en.wikipedia.org/wiki/List_of_unsolved_problems_in_mathematics
[4] https://en.wikipedia.org/wiki/Halting_problem
[5] https://en.wikipedia.org/wiki/Turing_completeness
[6] https://history.computer.org/pioneers/dijkstra.html
(c) Copyright 2019 by Mike Ferrell
Odd STEM 
One thought on “The Logically Unknowable (Part 1)”