Monday, January 21, 2019

Are you a Turing Machine?

A few days ago, regular commenter Publius drew my attention to a paper by a fellow named Selim G. Akl entitled "The Myth of Universal Computation."  In it Akl claims to exhibit functions that are computable, but not by a Turing machine.

If this claim were to pan out it should be big news because Turing machines are supposed to be "universal", that is, capable of computing any computable function.  The universality of Turing machines has been the bedrock of computer science for eighty years.  And yet you have almost certainly never heard of Selim G. Akl.

IMHO the obscurity in which Akl's work has languished is well-deserved, and I'm more than a little inclined to let these sleeping bogons lie.  But if Publius is citing Akl that means that this is probably making the rounds in the Christian-industrial network and so someone is going to have to debunk it sooner or later.  It's a dirty job, but I guess somebody's gotta do it, so it might as well be me.

It's a lot easier to talk about computability nowadays than it was in Turing's time because computing is now ubiquitous and hence familiar.  Modern consumers have some intuitions about what it means for one computer to be "more powerful" than another, and some idea of what makes one computer more powerful than another: More memory.  Bigger disk.  Faster processor.

What about having "Intel inside"?  Is there anything an Intel processor can do that (say) an AMD processor can't?  It turns out the answer depends on what you mean by "do".  There is nothing that an Intel processor can display on a screen that an AMD (or any other brand of) processor can't.  An Intel processor might be faster, and that might matter to you, but if you disregard time, all processors are essentially equivalent, and their limitations are defined almost entirely by how much memory they have.

One the other hand, if you don't ignore time then the details of the processor architecture do matter.  Some processors, for example, have more than one "core", the part of the processor that actually does the work.  If a processor has only one core then it can only do one thing at once.  It can give the appearance that it is doing multiple things simultaneously by switching rapidly back and forth between multiple tasks, but a processor with multiple cores can do multiple things literally at the same time, with concomitant performance improvements not just from the parallelism but also from the elimination of the switching overhead.  Similarly, if you care about security, some processors provide better protections than others against programs interfering with each other, or doing things like sending your banking credentials to Romanian hackers.

What if we ignored all of these practical considerations and considered only what a computer could do in principle if we could make it as powerful as we wanted?  Such a super-duper computer (SDC) would have two characteristics: it would run ridiculously fast, and it would have a ridiculous amount of memory.  How fast?  How much?  You name it.  Yottahertz.  Ziggybytes.  The only constraint, if we want this computer to be even remotely plausible as a model of anything that could exist in the real world, is that these numbers be finite.  They can be unbounded, that is, we need not commit ourselves to any particular numbers, but they can't be infinite.

As an aside, we actually can make some plausible estimates of upper bounds for these numbers in our universe.  For example, barring some major breakthrough in our understanding of physics, a real computer could never have a clock rate faster than the Planck frequency of 10^43 hertz (To put this in perspective, a single photon at this frequency has about the same energy as a ton of TNT) nor more bits of memory than there are elementary particles in the universe (about 10^80).  But we are in thought-experiment land and here we are not bound by puny physical constraints.  Want a googolplex of RAM?  A clock rate equal to Graham's number?  You got it.

It turns out that when you buy a super-duper computer in thought-experiment land the details of the architecture no longer matter.  No matter what the details of your architecture, all super-duper computers have the exact same limitations.  And yes, super-duper computers do have limitations, the most famous of which is that they cannot compute the halting function for super-duper computers.

Note that I did not say that super-duper computers can't "solve the halting problem."  This is because there is no such thing as "the" halting problem; there are a lot of different halting problems, an infinite number of them in fact.  They are all of the form: will a given program halt or run forever on some particular input on some particular computer?  Notice that there are three parameters here: the program, the input, and the computer.  There are many (in fact, an infinite number of) halting problems for which a solution is easily found.  But to compute the halting function for a particular computer you have to solve all of the instances of the halting problem for that computer.

Turing's central result with respect to the halting problem is not that the halting function can't be computed, it is that no computer can compute its own halting function.  I'm not going to go through the proof (you can find a concise presentation at the bottom of this page).  The only thing that matters is that the proof is completely general.  It applies to any model of computation, not just Turing machines.

Note in particular that the result does not apply to one computer computing the halting function for a different computer.  A super-duper computer can easily compute the halting function for your MacBook Pro.  This is because your MBP only has a paltry terabyte of disk space and a few measly gigabytes of RAM and runs as a snails-pace of a few gigahertz.  A super-duper computer can, for example, simulate your MBP and keep track of all the states that the MBP goes through as it runs until one of two things happens: either the program halts, or the machine enters a state that it was previously in.  If the latter happens, the MBP is in an infinite loop.  Because there are only a finite number of possible states your MBP can be in, one or the other must happen sooner or later.

Now, the cost of actually carrying out this procedure is ridiculously high.  An SDC trying to compute the halting function for a machine with N bits of memory would need 2^N bits of memory.  But this doesn't matter.  We're in thought-experiment-land where resources are free.  We can have as much memory as we need as long as it's finite, and 2^N is finite for any finite N.  There might be better, more efficient algorithms for computing the halting function, but Turing's proof shows that such an algorithm would require M>N bits of memory to compute the halting function for a machine with N bits of memory.

Can we imagine a meta-super-duper computer that could compute the halting function for a super-duper computer?  Remember, an SDC's memory is unbounded.  At any given point in time an SDC can only be using a finite amount of memory, but there is no upper bound on this finite number the way there is for your MBP.   An MBP can be "maxed out" to the point where you can't add any more memory to it.  But an SDC has no such constraint.  We know (per Turing) that to compute the halting function on an SDC we somehow need a machine that is more powerful, and it's not clear how we would get more powerful than an SDC.

Happily, we don't actually need to say how we would do it.  We can just define a meta-super-duper-computer as one that can compute the halting function for an SDC somehow without actually specifying how it does this.  This is a legal maneuver in thought-experiment land.  It's actually no different than how we defined an SDC in the first place.  We never said how an SDC has access to an unbounded amount of memory, only that it does.

As an aside, we actually can describe how an MSDC could compute the halting function for an SDC.  For example, one possibility is to say that every operation that an MSDC performs takes half the time as the preceding operation.  The effectively allows an MSDC to perform an infinite number of operations in a finite amount of time, and that is enough for it to be able to compute the halting function.  Filling in this kind of detail can make you feel warm and fuzzy that you're reasoning still bears some relation to reality, but it's not necessary.  And in fact this is false comfort because we actually left the realm of physical reality back when we imagined an SDC, because SDCs do not and cannot really exist.

But whatever, back to thought-experiment-land.  An MSDC defined in this way is called an oracle for the halting problem for SDCs.  An MSDC can -- by definition! -- compute the halting function for an SDC, but not, of course, for an MSDC.  Remember, Turing's proof is completely general.  No computer can compute its own halting function.  It applies to MSDCs and SDCs and MacBook Pros and your pocket calculator.  But nothing stops us from imagining halting problem oracles and meta-oracles and meta-meta oracles, just as nothing stopped us from imagining a super-duper computer in the first place.

What does all this have to do with Turing Machines?  Well, it turns out that a Turing Machine is a super-duper computer.  It can run arbitrarily fast (as long as it's not infinitely fast) and it has an unbounded memory, and that's all it takes to make an SDC.  This is what is meant by the slogan "Turing machines are universal."  By the time you get to SDC territory, the details of the architecture no longer matter they way they do in the real world.  All SDCs have the same repertoire of capabilities and restrictions, and those capabilities and restrictions are exactly those of Turing machines, and also of dozens of others of computational models that have been proposed over the years that all turn out to be equivalent to each other.  Yes, there is an infinite hierarchy of more powerful machines that we can imagine on top of SDCs/TMs.  But since SDCs/TMs are already vastly more powerful than anything we could ever hope to actually build, they are a useful place to stop.  If a TM can't do something, no computer we can ever build can do it.

Again, just as an aside, consider for a moment the implications if we could build an oracle for the halting problem.  This machine could answer any mathematical question.  Want to figure out whether the Goldbach conjecture is true?  Just write a TM program that systematically searches for counterexamples and feed it to a halting oracle.  If the oracle says that the program runs forever, the conjecture is true.

So back to Akl.  He describes three kinds of functions that he claims are computable, but not by TMs.  As we have already seen, there is really not much sport in this.  We already know that the halting function for TMs can't be computed by TMs, but can be computed by a halting oracle.  The only thing that would be interesting is if these new functions that were not computable by TMs could be computed by something less magical than a halting oracle, a human brain for example, or a machine that we would actually have some hope of building.  And in fact some of Akl's functions can be computed by real physical systems!

So why isn't this bigger news?

It's because Akl's functions are not functions.  A function is a mathematical object with a very precise definition: it is a (possibly infinite) set of ordered tuples that defines a map from inputs to outputs.  Sets are static.  They don't change with time.  But we are interested in computation, and computation is a process, and processes are inherently embedded in time (that's what makes them proccesses rather than states).  Turing's model of computation is one that starts with the input to a function and ends with the output of the function having been computed without imposing any constraints on what happens in between other than that the time between the beginning and end of the process must be finite.

Akl's "functions" don't meet this criterion.  The way Akl comes up with things that TMs can't do is not by defining a function that a TM can't compute, but by adding constraints to the computational process that TMs can't fulfill.  Again, there is no sport in this.  You don't need anywhere near Akl's level of sophistication to show an example of this.  Here's a simple one: a TM cannot satisfy the constraint that the number of symbols on its tape must be even at every stage of the computation.  If the number of symbols is even, then as soon as the TM writes one additional symbol to the tape the constraint is violated.

But, you say, that is just so obviously stupid.  You can easily fix that (assuming you would even want to) by (for example) allowing the TM to write two symbols to the tape as a single step.  And you would be absolutely correct.  But every one of Akl's examples amounts to nothing more than a more complicated version of this exact same thing: a constraint of some sort that a machine has to obey during the computational process that a TM as normally defined can't meet, but which a minor variation on the TM theme easily can.  Specifically, all it takes is redefining what it means for a machine to make a "step", and more specifically, to allow multiple "classic" TM steps to be combined into a single meta-step.

Seriously, that is what all the fuss is about.  (Now perhaps you understand why I was reluctant to take up this topic in the first place.)

But I actually think that all of the preceding discussion is a bit of a red herring, and that there is really something deeper going on here.  A hint of this is provided by Publius's reference to Searle's Chinese Room, and an essay entitled "The Empty Brain" with the log-line, "Your brain does not process information, retrieve knowledge or store memories. In short: your brain is not a computer."  Here's the thesis:
Computers, quite literally, process information – numbers, letters, words, formulas, images. The information first has to be encoded into a format computers can use, which means patterns of ones and zeroes (‘bits’) organised into small chunks (‘bytes’). On my computer, each byte contains 8 bits, and a certain pattern of those bits stands for the letter d, another for the letter o, and another for the letter g. Side by side, those three bytes form the word dog. One single image – say, the photograph of my cat Henry on my desktop – is represented by a very specific pattern of a million of these bytes (‘one megabyte’), surrounded by some special characters that tell the computer to expect an image, not a word.
Quite simply, this essay betrays a deep ignorance of how computers work.  It is simply not true that data is stored in a computer in the straightforward manner that the author implies.  Images, for example, are hardly ever stored in raw form, with the rows of pixels corresponding in a straightforward manner to the contents of memory.  Images are invariably stored in compressed form, as jpgs or gifs, in which case the bits that represent the image appear more or less random to casual inspection.  Even text is nowhere near as straightforward as the author implies.  There may have been a time decades ago when all text was ascii and stored flat, but those days are long gone.  Nowadays we have unicode, PDF, HTML, base64-encoded, quoted-printable, and ten thousand other text formats, none of which map text to memory contents in a straightforward way.

Now, of course, if we scan your brain we won't find gifs and jpgs and pdfs.  Your brain processes information differently from your Macbook Pro.  But that doesn't mean that your brain is not a computer.  It (almost certainly) is.  Its architecture and software are very different from your MBP, and reverse-engineering it is very difficult.  But we have a pretty good handle on the basics: your brain is made of neurons that process electrical signals from your peripheral nervous system according to rules that comply with the laws of physics and so are expressible mathematically.  That's pretty much all it takes to make a computer.

It is true that your brain is not a Turing machine.  It is in fact much less powerful than a TM because a TM is a super-duper computer with unbounded memory and your brain isn't.  It is bounded.  We don't know exactly what the bound is, but there is no doubt that it's there.

It is actually not surprising that we don't fully understand our own brains. This is, in fact, impossible.  We are computers so, per Turing, we can't compute our own halting function.  But just because we can't do it doesn't mean it can't be done.  A halting oracle for the human brain is certainly possible in principle.  Whether it's possible in practice is an open question.  I'll give long odds against, but I wouldn't bet my entire life savings.

Monday, January 07, 2019

I watched Bird Box so you don't have to

If you like a badly made, entirely predictable, not-very-scary, high-concept pseudo-horror thriller that scrapes the very bottom of the genre-cliche barrel, then go ahead and watch Bird Box, the latest craze movie from Netflix.  If you just want to know what all the fuss is about (because FOMO) and what the title refers to, then read on.  I will save you two hours of your life that I wish I had back.

Needless to say, this post contains spoilers.  Not that this matters very much.  The Big Reveal at the end is exactly what you would expect from a movie that revolves entirely around people having to go about their daily lives blindfolded for five years.  And no, I have not yet given anything away, other than that you can in fact predict the ending after watching the first five minutes of the film.

So in the first five minutes we learn that 1) Sandra Bullock has to take her two young children on a very dangerous journey down a river, 2) they have to wear blindfolds or they will die, and 3) they aren't taking anyone else with them.  Then we flash back five years to before They came and learn that They are... well, we never really find out what They are.  All we know is that if you catch a glimpse of one of Them you go crazy and kill yourself.  Which is actually a not-entirely-unreasonable premise for a horror movie, except for one thing: not only do we never learn what They are (aliens?  supernatural beings?  a defense department research project gone wrong?), not a single character in the film ever expresses even the slightest bit of curiosity about the answer to this question.  Our collection of protagonists makes exactly one attempt (and an extremely lame one at that) to figure out a way to actually "combat" Them.  I put "combat" in scare quotes because the only thing they actually do is try to find out if it's safe to look at Them through a security camera feed.  (You get two guesses what the answer turns out to be.)

Since you have now been adequately warned about spoilers I'll go ahead and tell you: the way they conduct this experiment is to strap a volunteer to a chair set up in front of the computer screen displaying the feeds from the security cameras.  And then they all leave this person alone in the room until they hear a thumping sound, which turns out to be the volunteer flailing around and, very conveniently, managing to tip the chair over at the precise moment that the rest of the crew bursts back into the room, and at the precise location where his fall will smash his skull open on some stonework and kill him so that no one has a chance to save him so they can ask any embarrassing (or, worse for the plot, enlightening) questions.

So the ground rules established for the world are: They are deadly to look at, even through a video camera, and they can (apparently) fly (Their arrival is always heralded by a gust of wind, rather like a dementor)... and that's it.  But They can't go inside.  That's all we ever learn.  Instead of a film about people trying to figure out how to fight these things, it's instead a movie about people flailing around trying to get to the grocery store when they can't see.  Seriously.  Like a full quarter of the movie is about this.

There are a few other elements that get thrown into the mix: not everyone who catches a glimpse of Them dies.  Some people get turned into psuedo-zombie evangelists who go around trying to get survivors to look at Them (because "They're beautiful!")  These pod-people can act like regular folks for a while, so it's hard to tell them apart from actual survivors who need help.  This leads to some heart-wrenching decision making that sometimes goes wrong.  Oh, and when They are nearby, birds will squawk and flap around, so Sandra Bullock acquires some pet birds, and before she goes down the river she puts them in a cardboard box with air holes (bird box, get it?) to take with them as an early warning system.  Not that this actually seems to do any good.  Despite having the birds around, it's not safe to look at the outside world even for a moment because, although They are not always present, They have a knack for showing up a the most inopportune moments, and the birds are apparently not reliable enough to allow taking even the slightest chance.  So there's a lot of time spent flailing around and paying out fishing line to try to find one's way back from whence one came.

Oddly, though, despite the fact that a lot of effort seems to go into finding ways to get around without being able to see -- including echolocation and the aforementioned fishing line trick -- one handy gadget that is unaccountably absent is a good long stick.  You'd think that after five years the heroes would either have the echolocation trick honed to a fine art, or they would have made themselves some nice white canes and they would never leave home without them.  But no.

Despite all this, Bird Box could still have been a reasonably satisfying thriller, except for one thing: because the opening scene includes only three characters, Sandra Bullock and her two kids, it's not hard to figure out the fate that befalls every other character that is introduced in the rest of the movie. So we don't have to wonder if the the black guy gets it.  The only thing we get to speculate about it when it will happen.  In what order will the other characters be dispatched so that we can finally get to the trip down the river and maybe see something that we didn't already know was coming half an hour ago.  (In retrospect, we should have turned this into a drinking game.  It would have helped take the edge off.)

Alas, the trip down the river is just as hackneyed and cliched as the setup.  Here is all you need to know: it's cold.  It takes a long time.  There are rapids.  Someone has to take their blindfold off to navigate the rapids.  Everyone ends up in the water, some more than once.  And neither children nor birds nor leading characters die.

Yes, the birds, still in their titular cardboard box, manage to somehow not only survive being dunked in a class 5 rapid, but to be recovered afterwards, still in the box (whose lid was not actually secured in any visible way), by people wearing blindfolds!  If that doesn't make you groan, nothing will.

In the end there is very little redemption.  Sandra Bullock has gotten a little less grinchy about being a mother, and at the end finally gives the kids proper names after having called them simply Boy and Girl for their entire lives.  But that's pretty much it.  Everyone else we've met is dead (and that's not even a spoiler!)  We are no closer to knowing anything about Them than we were at the beginning, so humanity is still fucked.

Except blind people.  I guess that's supposed to be the big reveal.

You're welcome.