Showing posts with label Alan Turing. Show all posts
Showing posts with label Alan Turing. Show all posts

Saturday, April 5, 2025

ML-friendly problems and unexpected consequences

This started out as "one more point before I go" in the previous post, but it grew enough while I was getting that one ready to publish that it seemed like it should have its own post.


Where machine learning systems like LLMs do unexpectedly well, like in mimicking our use of language, it might not be because they've developed unanticipated special abilities. Maybe ML being good at generating convincing text says as much about the problem of generating convincing text as it does about the ML doing it.

The current generation of chatbots makes it pretty clear that producing language that's hard to distinguish from what a person would produce isn't actually that hard a problem, if you have a general pattern-matcher (and a lot of training text and computing power). In that case, the hard part, that people have spent decades trying to perfect and staggering amounts of compute power implementing, is the general pattern-matcher itself.

We tend to look at ML systems as problem solvers, and fair enough, but we can also look at current ML technology as a problem classifier. That is, you can sort problems according to whether ML is good at them. From that point of view, producing convincing text, recognizing faces, spotting tumors in radiological images, producing realistic (though still somewhat funny-looking) images and videos, spotting supernovas in astronomical images, predicting how proteins will fold, along with many other problems, are all examples of pattern-matching that a general ML-driven pattern-matcher can solve as well as, or even better than, our own naturally evolved neural networks can.

Not knowing a better term, I'll call these ML-friendly problems. In the previous post, I argued that understanding the structure of natural languages is a separate problem from understanding what meaning natural language is conveying. Pretty clearly, understanding the structure of natural languages is an ML-friendly problem. If you buy that understanding meaning is a distinct problem, I would argue that we don't know one way or another whether it's ML-friendly, partly, I would further argue, because we don't know nearly as much about what that problem involves.


From about 150 years ago into the early 20th century, logicians made a series of discoveries about what we call reasoning and developed formal systems to describe it. This came out of a school of thought, dating back to Leibniz (and as usual, much farther and wider if you look for it), holding that if we could capture rules describing how reasoning worked, we could use those rules to remove all uncertainty from any kind of thought.

Leibniz envisioned a world where, "when there are disputes among persons, we can simply say: Let us calculate, without further ado, to see who is right". That grand vision failed, of course, both because, as Gödel and others discovered, formal logic has inescapable limitations, but also because formal reasoning captures only a small portion of what our minds actually do and how we reason about the world.

Nonetheless, it succeeded in a different sense. The work of early 20th-century logicians was essential to the development of computing in the mid-20th century. For example, LISP -- for my money one of the two most influential programming languages ever, along with ALGOL -- was based directly Church's lambda calculus. I run across and/or use Java lambda expressions on a near-daily basis. For another example, Turing's paper on the halting problem used the same proof technique of diagonalization that Gödel borrowed from Cantor to prove incompleteness, and not by accident.


Current ML technology captures another, probably larger, chunk of what naturally-evolved minds do. Just as formal logic broke open a set of problems in mathematics, ML has broken open a set of problems in computing. Just as formal logic didn't solve quite as wide a range of problems as people thought it might, ML might not solve quite the range of problems people today think it might, but just as formal logic also led to significant advances in other ways, so might ML.


Saturday, November 4, 2017

Surrender, puny humans!

A while ago, Deep Mind's AlphaGo beat human champion Lee Sedol at the game of go.  This wasn't just another case of machines beating humans at games of skill.

Granted, from a mathematical point of view it was nothing special.  Games like go, chess, checkers/draughts and tic-tac-toe, can in theory be "solved" by simply bashing out all the possible combinations of moves and seeing which ones lead to wins for which players.

Naturally the technical definition of "games like go, etc." is a bit, well, technical, but the most important stipulations are
  • perfect information -- each player has the same knowledge of the game as the others
  • no random elements
That leaves out card games like poker and bridge (imperfect information, random element) and Parcheesi (random element) and which-hand-did-I-hide-the-stone-in (imperfect information), but it includes most board games (Reversi, Connect 4, Pente, that game where you draw lines to make squares on a field of dots, etc. -- please note that most of these are trademarked).

From a practical point of view, there is sort of a pecking order:
  • Tic-tac-toe is so simple that you can write down the best strategy on a piece of paper.   Most people grow bored of it quickly since the cat always wins if everyone plays correctly, and pretty much everyone can.
  • Games like ghost or Connect 4 have been "strongly solved", meaning that there's a known algorithm for determining whether a given position is a win, loss or draw for the player whose turn it is.  Typically the winning strategy is fairly complex, in some cases too complex for a human to reasonably memorize.  A human will have no chance of doing better than a computer for such games (unless the computer is programmed to make mistakes), but might be able to do as well.
  • Checkers is too complex for humans to play perfectly, but it has been "weakly solved".  This means that it's been proved that with perfect play, the result is always a draw, but, not all legal positions have been analyzed, and there is currently nothing that will always be able to tell you if a particular position is a win for either side, or a draw.  In other words, for a weakly solved game, we can answer win/loss/draw for the initial position, and typically many others, but not for an arbitrary position.
  • Chess has not been solved, even in theory, but computer chess players that bash out large numbers of sequences of moves can consistently beat even the best human players.
In most cases the important factor in determining where a game fits in this order is the "branching factor", which is the average number of moves available at any given point.  In tic-tac-toe, there are nine first moves, eight second moves, and so on, and since the board is symmetrical there are effectively even fewer.  In many positions there's really only one (win with three-in-a-row or block your opponent from doing that).

In Connect 4, there are up to six legal moves in any position.  In checkers there can be a dozen or so.  In chess, a couple dozen is typical.  As with tic-tac-toe there are positions where there is only one legal move, or only one that makes sense, but those are relatively rare in most games.

In go, there are typically more than a hundred different possible moves, and go positions tend not to be symmetrical.  Most of the time a reasonably strong human player will only be looking at a small portion of the possible moves.  In order to have any hope of analyzing a situation, a computer has to be able to narrow down the possibilities by a similar amount.  But to beat a human, it has to be able to find plays that a human will miss.

I've seen go described as a more "strategic" game, one that humans can develop a "feel" for that computers can't emulate, but that's not entirely true.  Tactics can be quite important.  Much of the strategy revolves around deciding which tactical battles to pursue and which to leave for later or abandon entirely.  At least, that's my understanding.  I'm not really a go player.

AlphaGo, and programs like it, solved the narrowing-down problem by doing what humans do: collecting advice from strong human players and studying games played by them.  Historically this has meant a programmer working with an expert player to formulate rules that computers can interpret, along with people combing through games to glean more rules.

As I understand it (and I don't know anything more about Deep Mind or AlphaGo than the public), AlphaGo used machine learning techniques to automate this process, but the source material was still games played by human players.  [Re-reading this in light of a more recent post, I see I left out a significant point: AlphaGo (and AlphaZero) encode their evaluation of positions -- their understanding of the game -- as neural networks rather than explicit rules.  While a competent coder could look at the code for explicit rules and figure out what they were doing, no on really knows how to decode what a neural network is doing, at least not to the same level of detail -- D.H. Jan 2019]

The latest iteration (AlphaGo Zero, of course) dispenses with human input.  Rather than studying human games, it plays against itself, notes what works and what doesn't, and tries again after incorporating that new knowledge.  Since it's running on a pretty hefty pile of hardware, it can do this over and over again very quickly.

This approach worked out rather well.  AlphaGo Zero can beat the AlphaGo that beat Lee Sedol, making it presumably the strongest go player in the world.  [and it has since done the same thing with chess and shogi, though its superiority in chess is not clear-cut.  See the link above for more details.  -- D.H. Jan 2019]

On the one hand, this is not particularly surprising.  It's a classic example of what I call "dumb is smarter" on the other blog, where a relatively straightforward approach without a lot of built in assumptions can outperform a carefully crafted system with lots of specialized knowledge baked in.  This doesn't mean that dumb is necessarily smartest, only that it often performs better than one might expect, because the downside to specialized knowledge is specialized blind spots.

On the other hand, this is all undeniably spooky.  An AI system with no baked-in knowledge of human thought is able, with remarkably little effort, to outperform even the very best of us at a problem that had long been held up as something unreachable by AI, something that only human judgement could deal with effectively.  If computers can beat us at being human, starting essentially from scratch (bear in mind that the hardware that all this is running on is largely designed and built by machine these days), then what, exactly are we meat bags doing here?

So let's step back and look at the actual problem being solved: given a position on a go board, find the move that is most likely to lead to capturing the most stones and territory at the end of the game.

Put that way, this is a perfectly well-posed optimization problem of the sort that we've been using computers to solve for decades.  Generations, really, at this point.  Granted, one particular solution -- bashing out all possible continuations from a given position -- is clearly not best suited, but so what?  Finding the optimum shape -- or at least a better one -- for an airplane wing isn't well suited to that either, but we've made good progress on it anyway using different kinds of algorithms.

So "chess-style algorithms suck at go, therefore go is inherently hard" was a bad argument from the get-go.

From what I've seen in the press, even taking potential hype with a grain of salt, AlphaGo Zero is literally rewriting the books on go, having found opening moves that have escaped human notice for centuries.  But that doesn't mean this is an inherently hard problem.  Humans failing to find something they're looking for for centuries means it's a hard problem for humans.

We humans are just really bad at predicting what kinds of problems are inherently hard, which I'd argue is the same as being hard to solve by machine*.  Not so long ago the stereotype of a genius was someone who "knew every word in the dictionary" or "could multiply ten-digit numbers immediately", both of which actually turned out to be pretty easy to solve by machine.

Once it was clear that some "genius" problems were easy for machines, attention turned to things that were easy for people but hard for machines.  There have been plenty of those -- walking, recognizing faces, translating between speech and text, finding the best move on the go board.  Those held out for quite a long time as "things machines will never be able to do", but the tide has been turning on them as well thanks, I think, to two main developments:
  • We can now build piles of hardware that have, in a meaningful sense, more processing power than human brains.
  • With these new piles of hardware, techniques that looked promising in the past but never really performed are now able to perform well, the main example being neural network-style algorithms
At this point, I'm convinced that trying to come up with ever fuzzier and more human things that only human brains will ever be able to do is a losing bet.  Maybe not now, but in the long run.  I will not be surprised at all if I live to see, say
  • Real time speech translation that does as well as a human interpreter.
  • Something that can write a Petrarchan sonnet on a topic of choice, say the futility of chasing perfection, that an experienced and impartial reviewer would describe as "moving", "profound" and "original".
  • Something that could read a novel and write a convincing essay on it comparing the story to specific experiences in the real world, and answer questions about it in a way that left no choice but to say that in some meaningful sense the thing "understood" what it read.
  • Something that it would be hard to argue didn't have emotions -- though the argument would certainly be made.
[On the other hand, I also won't be shocked if these don't totally pan out in the next few decades --D.H. Feb 2019]

These all shade into Turing test territory.  I've argued that, despite Alan Turing's genius and influence, the Turing test is not necessarily a great test of whatever we mean by intelligence, and in particular it's easy to game because people are predisposed to assume intelligence.  I've also argued that "the Singularity" is an ill-defined concept, but that's really a different thread.  Nevertheless, I expect that, sooner or later, we will be able to build things that pass a Turing test with no trickery, in a sense that most people can agree on.

And that's OK.

Or at least, we're going to have to figure out how to be OK with it.  Stopping it from happening doesn't seem like a realistic option.

This puts us firmly in the territory of I, Robot and other science fiction of its era and more recently (the modern Westworld reboot comes to mind), which is one reason I chose the cheesy title I did.  Machines can already do a lot of things better than we can, and the list will only grow over time.  At the moment we still have a lot of influence over how that happens, but that influence will almost certainly decrease over time (the idea behind the Singularity is that this will happen suddenly, in fact nearly instantaneously, once the conditions are right).

The question now is how to make best use of what influence we still have while we still have it.  I don't really have any good, sharp answers to that, but I'm pretty sure it's the right question.


* There's a very well-developed field, complexity theory, dealing in what kinds of problems are hard or easy for various models of computing in an absolute, quantifiable sense.  This is largely distinct from the question of what kinds of games or other tasks computers should be good at, or at least better than humans at, though some games give good examples of various complexity classes.  One interesting result is that it's often easy (in a certain technical sense) to produce good-enough approximate solutions to problems that are provably very hard to solve exactly.  Another interesting result is that it can be relatively tricky to find hard examples of problems that are known to be hard in general.

Saturday, April 9, 2016

Primitives

Non sunt multiplicanda entia sine necessitate.

This is one of several formulations of Occam's razor, though Wikipedia informs us that William of Ockham didn't come up with that particular one.  Whatever its origins, Occam's razor comes up again and again in what we like to call "rational inquiry".  In modern science, for example, it's generally expressed along the lines of "Prefer the simplest explanation that fits the known facts".


If you see a broken glass on the floor, it's possible that someone took the glass into a neighboring county, painstakingly broke it into shards, sent the shards overseas by mail, and then had a friend bring them back on a plane and carefully place them on the floor in a plausible arrangement, but most likely the glass just fell and broke.  Only if someone showed you, say, video of the whole wild goose chase might you begin to consider the more complex scenario.

This preference for simple explanations is a major driving force in science.  On the one hand, it motivates a search for simpler explanations of known facts, for example Kepler's idea that planets move around the Sun in ellipses, rather than following circular orbits with epicyclets as Copernicus had held.  On the other hand, new facts can upset the apple cart and lead to a simple explanation giving way to a more complicated revision, for example the discoveries about the behavior of particles and light that eventually led to quantum theory.

But let's go back to the Latin up at the top.  Literally, it means "Entities are not to be multiplied without necessity," and, untangling that a bit, "Don't use more things than you have to", or, to paraphrase Strunk, "Omit needless things".  In the scientific world, the things in question are assumptions, but the same principle applies elsewhere.



The mathematical idea of Boolean Algebra underlies much of the computer science that ultimately powers the machinery that brings you this post to read.  In fact, many programming languages have a data type called "boolean" or something similar.

In the usual Boolean algebra, a value is always either True or False.  You can combine boolean values with several operators, particularly AND, OR and NOT, just as you can combine numbers with operations like multiplication, addition and negation.  These boolean operators mean about what you might think they mean, as we can describe them with truth tables very similar to ordinary multiplication or addition tables:

ANDTrueFalse
TrueTrueFalse
FalseFalseFalse

ORTrueFalse
TrueTrueTrue
FalseTrueFalse

NOTTrueFalse

FalseTrue

In other words, A AND B is true exactly when both A and B are true, A OR B is true whenever at least one of the two is true, and NOT A is true exactly when A is false.  Again, about what you might expect.

You can do a lot with just these simple parts.  You can prove things like "A AND NOT A" is always False (something and its opposite can't both be true) and "A OR NOT A" is always True (the "law of the excluded middle": either A or its opposite is true, that is, A is either true or false).

You can break any truth table for any number of variables down into AND, OR and NOT.  For example, if you prefer to say that "or" means "one or the other, but not both", you can define a truth table for "exclusive or" (XOR):

XORTrueFalse
TrueFalseTrue
FalseTrueFalse

If you look at where the True entries are, you can read off what that means in  terms AND, OR and NOT: There's a True where A is True and B is False, that is, A AND NOT B, and one where B is True and A is False, that is, B AND NOT A.  XOR is true when one or the other of those cases hold. They can't both hold at the same time, so it's safe to use ordinary OR to express this: A XOR B = (A AND NOT B) OR (B AND NOT A).  The same procedure works for any truth table.

In a situation like this, where we're expressing one concept in terms of others that we take to be more basic, we call the basic concepts "primitive" and the ones built up from them "derived".  In this case, AND, OR and NOT are our primitives and we derive XOR (or any other boolean function we like) from them.

Now consider the boolean function NAND, which is true exactly when AND is false.  Its truth table looks like this:

NANDTrueFalse
TrueFalseTrue
FalseTrueTrue

This is just the table for AND with True entries changed to False and vice versa.  That is, A NAND B = NOT (A AND B).

What's A NAND A?  If A is True, then we get True NAND True, which is False.  If A is False, we get False NAND False, which is True.  That is, A NAND A = NOT A.  If we have NAND, we don't need NOT.  We could just as well use AND, OR and NAND instead of AND, OR and NOT.

Since NAND is just NOT AND, and we can use NAND to make NOT, we don't need AND, either.  A AND B = (A NAND B) NAND (A NAND B).  So we can get by with just NAND and OR.

As it turns out, we never needed OR to begin with.  Quite some time ago, Augustus De Morgan pointed out that A OR B = NOT (NOT A AND NOT B), that is, A or B (or both) are true if both of them are not false, a rule which sometimes comes in handy in making "if" statements in code simpler (the other version of the rule, with the AND and OR switched, is also valid).  Using NAND, we can recast that as A OR B = (NOT A NAND NOT B), and we can get rid of the NOT, leaving A OR B = ((A NAND A) NAND (B NAND B)).

Summing up, we can build any boolean function at all out of AND, OR and NOT, and we can build all three of those out of NAND, so we can build any boolean function at all from NAND alone.

For example A XOR B = (A AND NOT B) OR (B AND NOT A).  We can use DeMorgan's rules to change that to (NOT (NOT (A AND NOT B) AND NOT (B AND NOT A))), that is, (NOT (A AND NOT B)) NAND (NOT (B AND NOT A)), or more simply, (A NAND NOT B) NAND (B NAND NOT A).  We can then replace the NOTs to get (A NAND (B NAND B)) NAND (B NAND (A NAND A)).

Yes, it's ... that ... simple.  Feel free to plug in all four combinations of A and B to check.

As silly as this may seem, it has real applications.  A particular kind of transistor lets current flow from its source terminal to its drain terminal when the voltage on a third terminal, called the gate, is high.  Put a high voltage on the source and let current flow either through the transistor or through an output for the whole thing.  Tie the gate of the transistor to an input.  If the voltage on the input is high, current will flow through the transistor and not to the output.  If the voltage on the input is low, current will flow to the output and not through the transistor.  That is, the output voltage will be high when the input voltage is not.  The whole thing is called a NOT gate (or inverter).

If you put two transistors in a row, then current will only flow through both of them when the voltage on both of the inputs is high, meaning it will flow through through the output, and the output voltage will be high, unless the voltage on both of the inputs is high.  The whole thing is called a NAND gate, and as we saw above, you can build any boolean function you like out of NANDs *.

In fact, we have it a bit easier here because we can build NOT A directly instead of as A NAND A, and for that matter we can build a three-input NAND  -- NOT (A AND B AND C) -- easily as well, but even if we couldn't, being able to build a NAND would be enough.



There are other cases where we can build up a whole system from a single primitive.  Notably, any computer program (technically, anything a Turing machine can compute) can be expressed in terms of a single instruction or, alternatively, a single "combinator".   This includes any boolean function, any numerical function, an HTML parser for web pages, whatever.  Of course, there's a difference between being able to express a computation in theory and being able to run it on your laptop or tablet.  We'll come back to that.

Before we go on to what all of this might mean, it's worth noting that many significant areas of thought haven't been reduced to simple primitives.  For example, chemistry is built from around a hundred elements (there are currently 118 on the periodic table, but you can't do meaningful chemistry with all of them).  An atom of any element is composed of protons, neutrons and electrons in varying numbers.

The Standard Model recognizes electrons as elementary, that is, primitive, while protons and neutrons are composed of quarks.  In all, it holds that there are 17 particles that everything is composed of  -- six quarks, six leptons (including the electron), four gauge bosons and the Higgs.  So far, no one has found anything simpler that these might be built up of, but not for lack of trying.

In mathematics, you typically start with a handful of axioms -- statements you assume to be true without proof -- and build from there.  There has been extensive work in reducing this to a minimal foundation, but the current formulation of set theory together with model theory has several important basic pieces, not one single concept to rule them all.  And, in fact, there are several ways of describing both set theory and model theory, not one single definitive way.

In short, some things can be reduced to a single primitive, but most can't.  Even when you can reduce something to a single primitive, there are typically several ways to do it.  For boolean algebra, you can just as well use NOR as NAND.  In computing there are several universal operations with little to pick among them.



In theory, there is no difference between theory and practice. But, in practice, there is. (attributed to Jan v/d Snepscheut)


If you can reduce any boolean function to NAND, is Boolean algebra in some meaningful sense really just NAND?  Is computing really just the study of a single instruction or operator?  If we're trying to reduce the number of entities involved, following Occam, is it not better to study a single operation than many?

I think most working mathematicians and computer scientists would answer "No" to all of the above.  A general Boolean algebra is a set of objects and operations that follow certain rules.  We noted above that A AND A = A.  In set theory, the union of a set with itself is that set, and there are other examples.  We would like to capture that common behavior somehow, and we do it by defining rules that hold for anything that behaves in the way we're interested in, that is, axioms.  In the case of Boolean algebra there are five (chase the link if you're interested).

It just so happens that in the simple case of True, False and the operations on them, NAND and NOR can be used to build all the others.  That's nice, but not essential.  It's of interest in building circuits out of transistors, but even then there's no requirement to build everything from one type of gate if you don't have to.  As noted above, it takes fewer transistors to build a NOT directly, and that's how real circuits are built.

Even from the point of view of Occam's razor, it's not clear that reducing everything to NAND is a good idea.  Yes, you have only one operation to deal with, but you can define one truth table just as easily as any other.  If you want to use XOR, it's simpler to define the truth table for it than to define the truth table for NAND and then define XOR in terms of it.

In computing, if you have the machinery to rigorously define one instruction or operation, you can define as many as you like with the same machinery.  It may be interesting or even useful in some situations that you can define some operations in terms of others, but it doesn't make the system more useful.  In practice, I don't care how many instructions the processor has.  I care very much if there's an easy way to talk to the network or write to a file, things which are not even mentioned in theoretical discussions of computing (nor should they be in most situations).

So why even bother?  Is reducing a system to a single primitive just an interesting academic exercise?  Not necessarily.  If you're trying to prove properties about circuits or programming systems in general, it can be useful to divide and conquer.  First prove, once and for all, that any circuit or program can be reduced to a single primitive, then prove all sorts of useful properties about systems using that primitive.  Since you only have a single operator or whatever to deal with, your proofs will be shorter.  Since you've proved your operator is universal, they'll be just as powerful.  Essentially you've said that when it comes to general properties of a system, adding new operators or whatever doesn't do anything interesting.

You don't have to reduce everything all the way to a single primitive for this to be useful.  If you can only reduce a system to five primitives, doing proofs using those five is still easier than doing proofs on an equivalent system with twenty.


In general, there's a tension between keeping a system minimal and making it easy to use.  A minimal system is easier to build and it's easier to be confident that it works properly.  A larger system is easier to use, as long as there's not too much to take in.  Typically there's a sweet spot somewhere in the middle.

There are sixteen possible boolean operators on two variables, and you can build any of them up from NAND (or NOR), but usually we focus on three of them: AND, OR and NOT.  These are enough to build anything else in a way that's straightforward to understand.  They also correspond fairly closely to familiar concepts.   In some useful sense, they minimize the number of things you have to deal with in normal cases, and William of Ockham can rest easy.

It doesn't only matter how many things you have.  It matters which things.




* As usual, there are a few more wrinkles to this.  You have to tie the output of the last (or only) transistor to ground for current to flow, you need a resistor next to the input, the output also needs to be tied to ground eventually, and so forth.

You may have noted that current is flowing through the two transistors in the NAND gate precisely when both inputs are high, that is, the current is flowing through them (and not to the output) when one gate voltage is high AND the other is.  You might think it would be simpler to build an AND than a NAND.  However,  the current will only flow if the drain of the last transistor is connected to a low voltage.   That voltage will be low regardless of what's happening on the gates.  To see a difference in voltages, we have to look at the voltage at the top, which will vary depending on whether current is flowing through the transistors (that's probably not too clear, but it's the best I can do).

Tuesday, June 17, 2014

Reading University and Mr. Turing's test

The BBC reports that a chatbot called Eugene Goostman has passed the Turing test, marking the first time in history that this has happened.  Or at least, that's what you'd gather from the headline (granted, it doesn't give the name of the chatbot).  The BBC, not having taken complete leave of its senses, explains that this is the claim of the team at the university of Reading that ran the test, and then goes on to cast a little well-deserved doubt on the idea that anything historic is going on.


So what's a Turing test?

Sixty-four years ago, Alan Turing published Computing Machinery and Intelligence, in which he posed a simple question: Can machines think?  He immediately dismissed the question as essentially meaningless and proposed an alternative: Can a machine be built which could fool a person into thinking that it (the machine) was a person?

In Turing's setup, which he called "the imitation game", there would be a judge who would communicate with two players, each claiming to be a person.  The judge and players would communicate via a "teleprinter" or other intermediary, so that it would not be possible to point at one of the players and say "That one's a machine, duh".  Turing goes into quite a bit of detail on points like this that we would take for granted now.  Your favorite instant messaging system is good enough for the task.  On the internet, nobody knows your'e a dog.

Later in the paper Turing makes a pretty audacious claim, considering it was made in 1950 and the supercomputers of the time had somewhere on the order of 16K of memory.  In case you've forgotten how to count that low, that's 1/32 of a megabyte, or about a millionth of the capacity of a low-end smartphone.  Turing's prediction:
I believe that in about fifty years' time [that is, by around the year 2000] it will be possible, to programme computers, with a storage capacity of about 109 [bits], to make them play the imitation game so well that an average interrogator will not have more than 70 per cent chance of making the right identification after five minutes of questioning.
109 bits is about 128 megabytes, not an unusual amount of RAM for a computer in the 2000s and a remarkably good prediction for someone writing in 1950.  Keep in mind that Turing wrote this well before Moore formulated Moore's law, itself a good source of misinterpretations.

Turing was a brilliant scientist.  He helped lay the groundwork for what we now call computer science, played a key role in pwning the German Enigma machine during World War II, and thought deeply about the question of intelligence and how it related to computing machinery.  However, he got this particular prediction spectacularly wrong.

It didn't take fifty years to beat the imitation game.  It took more like fifteen.

In the mid 1960s, Joseph Weizenbaum of MIT wrote ELIZA, which purported to be a Rogerian psychotherapist.  You can play with a version of it here.  To be clear, this program wasn't actually trying to do psychotherapy.  It was more like a parody of a "nondirective" therapist whose goal is to stay out of the way and let the patient do all the meaningful talking.  Was it able to fool anyone?  Yes indeed.  So much so that it inspired Weizenbaum, after seeing people confide their deepest secrets to the program, to write a book about the limitations of computers and artificial intelligence.

ELIZA neatly dodges the difficulties that Turing was trying to present to the developer by making the human do all the thinking.  Say "The kids at school don't like me" and ELIZA won't respond with "I know what you mean.  At my school there was this bully named ..." and give you a chance to probe for things only an actual human who had been to school would know.  It will respond with something like "Why do you think the kids at school don't like you?"  It's a perfectly reasonable response, but it reveals absolutely zilch about what the machine knows about the world.

That's fortunate, because the machine knows absolutely zilch about the world.  It's just taking what you type in, doing some simple pattern matching, and spitting back something based, in a fairly simple way, on whatever patterns it found.  This works great for a while, but you don't have to wander very far to see the man behind the curtain.  Answer "Because I am." to one of its "Why are you ...?" questions, and it is liable to answer "Do you enjoy being?", because it saw "I am X" and tried to respond "Do you enjoy being X?"  Except there is no X in this case.

The Eugene Goostman chatbot likewise dodges the difficult questions, but as far as I can tell it does it by acting flat-out batty.  Its website says as much, advertising itself as "The weirdest creature in the world".  When I first saw the Reading story on my phone, there were transcripts included.  These are somehow missing from the version I've linked to, but there is a snippet of a screenshot:
  • Judge: What comes first to mind when you hear the word "toddler"?
  • Goostman: And second?
  • Judge: What comes to mind when you hear the word "grown-up"?
  • Goostman: Please repeat the word to me 5 times
Sure, if you're told that you're chatting with an eccentric 13-year-old boy with English as a second language, you could take pretty much any bizarre response and say "meh ... sure, that sounds like something a 13-year-old eccentric non-native speaker might say ... close enough."  But so what?

The transcripts I saw on my phone were of a similar nature.  Apparently the Goostman website had run the chatbot online for a while, and you can find transcripts from people's interactions with it it on the web. The online version was soon taken down, perhaps from the sheer volume of traffic or, a cynic might say, because the game was up.

This is not the first time people have mistaken a computer for a human behaving outside the norm.  Not long after ELIZA, in 1972, psychiatrist Kenneth Colby, then at Stanford, developed PARRY (this was evidently still before mixed-case text had become widespread).  Unlike ELIZA, PARRY wasn't basically trolling.  It was a serious attempt to mimic a paranoid schizophrenic and so, if I understand correctly, to learn something about the mind of a person in such a state.

Colby had a group of experienced psychiatrists interview both PARRY and actual paranoid schizophrenics.  He then gave the transcripts to a separate group of 33 experienced psychiatrists.  They identified the real schizophrenics with 48% accuracy -- basically random chance and far below Turing's 70%.  That is, PARRY could fool the psychiatrists about 50% of the time, while Turing only expected 30%.

This was from transcripts they got to read over, not from a quick five-minute exchange.  For my money this is a stronger test than Turing's original, and PARRY passed it with flying colors.  Over forty years ago.  Eugene Goostman fooled 33% of the judges (one suspects that the number of judges was a small multiple of three) in five-minute interviews by spouting malarkey.  Not even carefully constructed paranoia, just random balderdash.  Historic?  Give. Me. A. Break.

By the way, if you're thinking "ELIZA is pretending to be a psychotherapist, PARRY is pretending to be a person with mental issues ... hmm ..." ... it's been done.


Thing is, Turing's test just isn't very good.  In attempting to control for factors like appearance and tone of voice, it limits the communication to language, and printed language at that.  In doing so, it essentially assumes that facility in language is the same as intelligence.

But this is simply false.  A highly-intelligent person can become aphasic, and there are cases in the literature of people who can speak highly-complex sentences with a rich vocabulary, but show no other signs of above-average intelligence.  And, as we've seen, it's been feasible for decades to write a computer program that does a passable imitation of human language without understanding anything at all.  I believe there are also documented cases of humans failing Turing tests, but that's a different issue.

It turns out that we humans have a natural tendency to attribute at least some level of intelligence to anything that looks remotely purposeful.  For example, there is an experiment in which people watch two dots on a screen.  I don't recall the exact details, but I think the following gets the gist:

One dot approaches the other and stops.  It then backs off and approaches again, faster.  The first dot is now touching the second, and both move slowly in the direction the first dot had been going.  Ask a person for a description, and they'll likely say that the first dot was trying to get past the second and finally tried pushing it out of the way.

Throw in language and the urge to attribute intelligence is nearly overwhelming.  "OK", one finds oneself thinking, "it's maybe not completely grammatical, and it doesn't make much sense, but that's got to be because the person talking is a bit ... off, not because they're not intelligent at all.  They can talk, for goodness' sake."

Whether something passes the Turing test in practice comes down more to a judge's ability to set aside intuition and look for artifacts of pattern-matching approaches, like the "Do you enjoy being?" example above.

This assumption that language facility was a good proxy for intelligence ran through a lot of early AI, leading to an emphasis on discrete symbol-smashing.  You have to start somewhere, it's clear that understanding language has a lot in common with other signs of intelligence, and a lot of useful work came out of efforts to develop good symbol-smashing tools, but to some extent this is more like looking for your lost car keys where the light is brightest.  Computers are good at smashing symbols, or more generally, dealing with discrete structures, which would include words and sentences.  That's basically their job.

It's now looking like probability and continuous math have more to do with how our minds actually work.  Being able to communicate in the (more-or-less) discrete medium of language came along relatively late in the evolutionary game, long after other aspects of intelligence, and language itself doesn't behave the way we assumed it did fifty years ago.  Science marches on.

There's another problem with the Turing test, something that looks like a strength at first:  It's free-form.  The judge is allowed to ask any questions that seem appropriate.  There is no checklist of abilities to test for.  If the respondent claims to have trainspotting as a hobby, there's no requirement to find out if they know anything about trains, or their schedules, or the sound of a locomotive or the smell of overheating brakes.

More generally, there is no requirement to test for, say, understanding of metaphor, or the ability to learn a new concept or glark the meaning of a word from context.  There is no requirement to determine if the respondent understands the basic properties of objects, space and time.  And so forth.

To be sure, there's an obvious objection to imposing requirements like this.  It would lead to "teaching to the test".  Contestants trying to pass such a variation of the Turing test would naturally try to build systems that would be able to pass the particular requirements.

But that could well be a good thing.  It's surely better than seeing people grab headlines by writing a bot that spouts gibberish.  As long as the requirements are phrased abstractly we can still leave it up to the judges' ingenuity to decide exactly what metaphor to try or what specific questions to ask about space, time and objects.  At the end of the test we can expect these requirements to be covered, or invalidate the judge's result if they aren't, which we can't with a free-form test.

The particular list I gave doesn't necessarily cover everything we might want to associate with intelligence, but a system that can understand metaphors, space and time, and can learn new concepts, can reasonably said to be "thinking" in a meaningful sense of the word.

Setting explicit requirements would also allow for variant tests that would accept forms of intelligence that were significantly different from ours.  For example, one very important part of being human is knowing what it's like to have a human body.   Being embodied as we are plays a large role in our cognition.  However, it's perfectly possible for something to be intelligent and, for example, not experience tastes and smells (indeed, some number of people have no such experience).

It seems reasonable to instruct the judges "We know this might be a machine.  Don't ask it what things taste like."  In the original Turing test, if the program came up with some plausible explanation for lacking taste and smell, a natural follow-up might be "What's it like not to be able to taste and smell?"  It's not clear that a machine would need to have a good answer to that in order to be intelligent.  If it didn't, the judge might have a good reason to think it was a machine even if it did in fact have some meaningful form of intelligence.  Either way the line of questioning is not helpful as a way of testing for intelligence.  In other words, distinguishing human from machine is not quite the same as distinguishing intelligent from unintelligent.

Hiding behind all this is one more shaky assumption: Something is either intelligent or it isn't.  Even though Turing properly speaks of probabilities of guessing correctly, there is still the assumption that a machine is either successfully imitating a human or it isn't.  Suppose, though, that a machine is really good at some area of knowledge and the judges happen to ask about that area 31% of the time.  That machine would pass the Turing test (in the popular but not-quite-accurate sense), but what does that mean?  Is it 31% intelligent?


I wouldn't lay much of this at Turing's feet.  He was doing pioneering work in a world that, at least as far as computing and our understanding of human cognition are concerned, was starkly different from the one we live in, and yet he managed to hit on themes and concepts that are still very much alive today.  Nor would I blame the general public for taking a claim of a historic breakthrough at face value.

But the claim itself?  Coming from a respected university?  Granted, they seem mostly hyped about the quality of their test and the notion that nothing else so far has passed a "true" Turing test.  But this seems disingenuous.  What we have here is, maybe, a more methodologically faithful version of Turing's test, which was passed by a mindless chatterbot.  The only real AI result here is that a Turing-style imitation-based test can be beaten by clearly unintelligent software.

This is not a new result.

[The Wikipedia article on Eugene Goostman makes a really good point that I never caught: Turing predicted a 30% success rate.  He didn't define that as some sort of threshold for intelligence.  Thus, fooling 30% of the judges doesn't mean that something "passes the Turing test and is therefore intelligent" It's just confirming Turing's prediction about how well machines would be able to win the imitation game.]