Analysis is stepwise, discrete, and finite. If god wishes to step down from his pompous perch in the heavens and argue any of these points, it is welcome to do so. But at as long as human, &/or humanly accessible, intelligence is all we have access to, then these points are not subject to even the abstract possibility of dispute. To dismiss one potential objection, artificial intelligence (“AI”) is entirely human produced, and absolutely subservient to the rules of computation and complexity that any other humanly accessible intelligence might be. It might be able to grind through problems faster than ordinary human minds. But it can only grind through the same class of problems (computable) in a meaningful amount of time (complexity) that humans are otherwise able to do so. The previous distinction highlights a difference that we must bear in mind: what is computable is about what is possible in the abstract, while complexity deal with what is possible in the concrete. Fans of the television series Numb3rs, might recall that the mathematician brother, Charlie, when he was stressed out, turned to the (in)famous problem of “P vs. NP.”i This puzzle has to do with the complexity issue of what is merely abstractly possible, and what is imaginably practical. This deserves a few extra words, because it brings us muzzle up to the difference between the merely possible, and the potential/actual.
The “P” in the above formulation basically stands for “polynomial.” Which is to say, it represents a level of complexity that is still simple enough that it can be calculated with a polynomial formula in mathematical terms. Polynomial formulae can get pretty damned big – in human terms – which is why a computer, crushing terms at staggering speeds, can burn through such problems faster than any human, than any imaginable team of humans, could ever hope to do. Computer programs that defeat grand master chess players do so by brute force; they just stomp through every possible combination of moves out to some staggering length of possible moves and then make a decision.
(Consider the difference between a rock rolling down hill, and a formula calculating the rock’s path. The rock makes no calculations, it just rolls. The formula and calculator must engage a shockingly huge number of combinations and parameters to even begin to approximate the rock’s behavior. Humans are the rock; computers are the calculator.)
I mentioned the idea of a “Turing Machine” above. This is named after the brilliant logician Alan Turing, who originally formulated it.ii This is arguably the most elementary form of computable analysis possible. The arguable part comes from the fact that there are alternative basic models, but there are no reasons to believe they ultimately give different images of what is computable. The claim that they are in fact all equivalent is called Church’s Thesis, named for the great 20th C. logician Alonzo Church. I should add that, while none but a few outliers (if any exist) doubt that Church’s Thesis is true, no proof of it has ever come out. Just as with the “P vs. NP,” also mentioned above.
Every basic TM can handle even the most exotic computation any of your devices performs. Look at that photo-realistic scenery in that game you’re playing; the same result could be achieved with a machine composed of a very long paper tape, a writing scribe on that tape, and an alphabet of a few characters. The latter, TM, would be less efficient than you computer or mobile device. But that loss of efficiency would be calculated by a polynomial equation – again, the “P” in the above “P vs. NP”. So what the hell is the “N” all about?
The “N” stands for “nondeterministic.” In a basic “P” computation, ever step follows in an absolutely deterministic way from all the other steps, regardless of how polynomially complicated those steps might be in moving from a TM to an actual computer. And here’s [a/the/one of the] kicker(s): That stupid TM can model that Nondeterministic Polynomial, but your laptop, your tablet, your cellphone, the government’s biggest supercomputer CANNOT. NP problems are theoretically solvable – they are computable – but actually computing/solving such problems would require more time, space, matter, and energy than exist in this or any possible universe. NP problems are “computable” in the abstract, but they are intractable in practice.
Using standard computing methods, that is. And assuming that P ≠ NP (which has not been proven, but which no one doubts).
And one other assumption as well. But we’ll get to that in the “part 2” essay that will follow this one.
NP problems can be pretty exotic. For example, the encryption that all of your computer systems use – for contacting and protecting your banking info, for masking your ID if you use a VPN or a secure browser, for stopping nosey neighbors from checking which porn channels you habitually visit – are all built around problems about large prime numbers (numbers that are only divisible by one and themselves), that cannot be solved in “P” limited computation. But they can also be seemingly simple.
The classic example is the “traveling salesman problem.”iii A traveling salesman (surprise!) must visit a number of cities, with various nonlinear (not a single straight line) paths connecting them. Problem: what is the most efficient route for the salesman to travel? The problem is NP, which means that it rapidly becomes absolutely intractable. Computer game enthusiasts encounter this problem all the time. The game has assigned multiple quests to the player; what is the most efficient way of tackling those quests? Sorry, bucko, you’re like that funny fish they serve in Boston (scrod).
Like the season finale of a TV show you were foolish enough to get hooked on, this essay ends on a cliff hanger. I’ll say more in my next entry, and hopefully say enough to reach a relative conclusion.
– – – – – – – – – –
i Numb3rs was not as bad as many shows in which the “scientist” is an expert in every branch of science without limit or qualification. But it still made Charlie an expert in far more areas of mathematics than any possible genius could ever possibly be.
ii Alan Turing is also the man who headed the team that cracked the Nazi’s Enigma code machine. No single action or actor did more to secure the victory of the Allies in the Second World War. But because he was gay, after the war Turing was hounded, tormented, and tortured by society and the government until he ultimately committed suicide. So you’ll forgive me if I refuse to show anything short of blatant, seething contempt for homophobes of all stripes and nations.
iii My mind absolutely refuses to accept that “traveling” has only one “l”.