Beware of the Train

I was pleasantly astonished to see Peter Norvig comment on my recent post about the Stanford online courses - with 160,000 students competing for his attention, that's dedication! I completely take his point that I'm only a small part of the intended audience, and what works best for me is probably not what works best for the students they really want to reach.

Nevertheless, the course has sped up in the last couple of weeks to the point where I'm finding it pleasantly stretching. Today I tweeted:

I take it back: #aiclass is covering the Oxford 1st-year logic course in <1wk. The good bits of the syllabus, anyway :-)

I want to expand on that remark a bit. There were actually three first-year Oxford logic courses:

• "Introduction to Symbolic Logic", taught in the first term to all Philosophy students (including those like me who were studying Maths and Philosophy), and also a few others like Classics students. This covered propositional logic, first-order predicate logic, proof tableaux, and endless pointless arguments about the precise meaning of the word "the" and whether or not the symbol → accurately captures the meaning of the English word "if". This is the course I was talking about on Twitter. I found it unbearably slow-paced, but I remember a couple of folk who'd given up maths years before and couldn't handle being asked to do algebra again. "The alarm is sounding and Mary called" was fine, but "A & M" was apparently unintelligible to them.
  
  According to a legend which was told to me by the Warden of New College and is thus of unquestionable veracity, a class of ItSL students were once sent to the Wykeham Professor of Logic's graduate-level logic seminar due to a scheduling error. The WPoL walked in, saw the expected roomful of youngsters, and started "Let L be a language recursively defined over an alphabet X..." The poor undergrads, still in their first week (and quite possibly at their first class) of their undergraduate careers, must have started to entertain grave doubts about their ability to handle this "Oxford" place. When the WPoL was eventually informed of the mistake, he is supposed to have meditatively said "I thought they seemed rather ill-prepared..."


• "Elements of Deductive Logic", taught in the second term to those studying (Maths|Physics) and Philosophy. This bumped the mathematical content up a notch, covering (for instance) completeness and consistency theorems for the languages that had been introduced in ItSL. There was also a rather handwavy treatment of modal logic, and lots more philosophical wrangling about what it all meant and how relevant it was to the broader philosophical project. This was one of the most intense courses I did in my four years as an undergrad.


• There was an introduction to symbolic logic buried somewhere in the first-year computer science course - without the philosophy, I'm assuming.

Maths students were expected to pick the basics of logic up in the course of learning real analysis, as is traditional.

I always thought they'd have been better splitting ItSL and EoDL into two more evenly-sized courses - perhaps one heavily mathematical one, to be shared with the CS students (and perhaps incorporating some digital electronics), followed by a purely philosophical one to be taken by the (Maths|Physics) & Philosophy students. Meanwhile the algebra-phobes could do a single course more tailored to their level. I'm guessing that resource availability ruled this idea out, though.

There was also a two-term second-year maths course called "b1 Foundations", which was set theory, logic (up to, IIRC, the Löwenheim–Skolem theorem and Skolem's paradox) and some computability theory. This was compulsory for Maths & Philosophy students, but I didn't take it because I'd given up philosophy by then and was sick of the whole thing. In light of my subsequent career, this was probably a bad decision.

Most people know the story of the three blind men and the elephant. There were three wise blind men (the story goes) who had never before encountered an elephant. One day, an elephant was brought before them, and they were asked to describe it. The first wise man felt the trunk, and said "Elephants are like snakes", the second felt a leg, and said "Elephants are like tree-trunks", and the third felt an ear and said "Elephants are like bats".

This story gave rise to the title of the mathematician Peter Johnstone's epic work Sketches of an Elephant: A Topos Theory Compendium. Topoi, you see, can be described from several different viewpoints, and it's not at all obvious that the different descriptions all describe the same object.

As is so often the case, the story of the blind men and the elephant has a dual version, which is less well-known but (IMHO) equally interesting. It concerns three wise, blind elephants, who had never before encountered a human being. One day, a human was brought before them, and they were asked to describe it. The first elephant stepped forward, and felt the human with its front hooves for a while.

"Humans," the elephant pronounced, "are flat".

And both the other elephants agreed.

I once told the dual story to Peter Johnstone. He didn't appear to enjoy it.

OK, it looks like the gender theory quotation thread has reached the end of its life-cycle, so it's time to reveal the answer. Yes, that's right: I knew where the quotation came from all along, and was using it... not really to test you, but to test the author's assumptions. I'm sorry if any of you feel betrayed by this - if it helps, I think you all passed :-)

Anyway, ( Spoilers ho! )

Here's something that's been bugging me for a while: why are computers useful?

A bit of an odd question, you might think, and I'm going to need to explain some background. First, you need to know that there are problems that computers can't solve, even in principle. A classic example is the halting problem: given a program and its input, can you predict whether or not the program will terminate? Alan Turing showed that it's impossible to write a program that will do this correctly in all cases. A co-worker of mine was once asked to do precisely this by a client...

Next, you need to know a bit about infinity, and ( the surprising behaviour of infinite sets )

Armed with this knowledge, we can see that Turing didn't need to exhibit an actual example of an uncomputable problem: he could have shown that some problems are uncomputable much more easily. Consider the following problem: you have some subset X of the natural numbers. X might be the set of even numbers, or the set of prime numbers, or the set of perfect numbers, or the set of Fibonacci numbers, or something like that. You want to write a program which will accept a number as input, and output "Yes!" if the number is in X, and "No!" if not. Now, by a close relative of Cantor's diagonal argument, there are uncountably many subsets of the natural numbers. But every program in your favourite programming language is a finite sequence chosen from an alphabet of finitely many symbols, so there can only be countably many programs! Hence, there must be some subsets X for which there is no such program. [I'd like to thank Jeff Egger for introducing me to this argument]. In fact, it's much worse than that - if you were to pick a subset at random, the probability that it would be computable would be 0. Not 1%, or 0.01%, or 0.000000001%, but actually zero. You need to be quite careful about how you define probability for this statement to make sense, but it's true. [Edit: having discussed this with an actual analyst, it turns out the truth is more complicated than I'd thought. There may be reasonable ways to define the probability measure on the space such that the probability of computability is non-zero. However, there is at least one way of defining a probability measure such that my statement is true - see my reply to benparker below.]

This seems like quite a contrived and artificial problem, but it's not really: lots and lots of useful problems can be re-stated in this form, with a judicious choice of X. We're not worried about how efficient the solution would be, only that one exists; hence, if the "subset of N" form of the problem is incomputable, so was the original form.

Hence my original question: why are computers useful? If the probability of a computer being able to answer our questions is zero in theory, how come they are so useful in practice? My former colleague aside, most of us don't need to worry about computability in our day-to-day coding: we can pretty much assume that there is a solution to our problem, and that finding it is the hard part.

I don't really know the answer, but it seems to me that it must have something to do with approximations. We're finite creatures, and we're usually happy with finite answers - we'll approximate an infinite decimal to one with ten (or thirty, or five hundred, or at most a few billion) decimal places, we'll just ask for the first few elements of an infinite sequence, we'll approximate the movement of continuous fluids by thousands of discrete chunks, and so on. This can lead to errors and problems, but usually these can be dealt with or lived with. Also, since we're finite, we're only capable of creating a finite amount of data for our computers to search through and manipulate. If we restrict the problem above to finite subsets of the natural numbers, the picture becomes a lot better: now there are only countably many subsets to choose from. We might still have probability zero, but it's not enforced in the way it was before.

In practice, as I said, the probability of their being a useful computable approximation to our original problem seems to be near to 100%. This strikes me as something close to miraculous. Is this just a mirage? Do we not encounter uncomputability because we subconsciously shy away from it, just as 19th-century scientists largely failed to notice the ocean of nonlinearity that they were swimming in? Or are the computable functions somehow dense in the uncomputable ones, in the way that the (countable) rational numbers are dense in the (uncountable) real numbers?

Closely related to the No True Scotsman fallacy is Sliding Definition Ploy¹. It goes like this: "for the sake of argument", give a slightly-odd definition to some common term, like Mind, or Freedom, or Justice, or Beauty. Deduce some consequences from that definition (ideally, this stage should take a while, to overflow your audience's input buffers). Claim that these deductions tell you something about the ordinary meaning of the term you started with. Better yet, don't claim it; just proceed as if they do.

SDP is, unfortunately, endemic to philosophy, or at least was when I last took a look. In philosophy, one of the big problems is that all the really interesting ideas you want to talk about (Truth, Justice, Ethics, Vision, Desire, the Soul, Mind, Body, even simple things like "looking"²) are ill-defined. The other big problem, of course, is that you can't do experiments on most of these things (even if you're the sort of philosopher who believes we can trust our senses and the sort who's prepared to accept the validity of the scientific method, which is by no means all of them). So you're left with pure reasoning. Mathematicians can get away with relying on pure reasoning, because they're working with abstract things that are precisely defined. Sorta³. So, in order to get any traction at all on their problems, philosophers often have to provide definitions of common terms. This allows the unscrupulous philosophers⁴ to insert a Sliding Definition Ploy or two.

SDP is also common in arguments about politics: we're all in favour of Liberty, Justice, etc, but these terms are all ill-defined, and by choosing definitions carefully, it's easy to show that your opponent is opposed to any given Good Thing. zompist has written more about this in one of his rants, in which he also elaborates on the linguistic problems with definitions.

There are lots more standard logical fallacies: Wikipedia has a list (Googling will reveal several others), and here's infidels.org's guide to logic and fallacies, which also has what looks like a good section on what logic is, what it isn't, and what it's useful for.

[By the way, I am no longer eating salted porridge. I am now about to tuck into a sausage sandwich. An organic venison sausage sandwich, no less, filled with sausages from the farmers' market at Queen's Park yesterday :-) ]

¹ The term is due to John Puddefoot, AFAIK.
² I know a philosopher who recently wrote a paper on the difference between "looking" and "watching". Or possibly "watching" and "seeing". Or something like that. It's subtle stuff.
³ At the risk of being accused of SDP myself, this is probably the best definition of mathematics we have.
⁴ A depressingly large subset, from what I can see.

Fascinating idea, courtesy of bruce_schneier: the correct legal framework for dealing with terrorism is the one already in use for dealing with pirates. Apparently, piracy is a crime defined in international law, and pirates can be arrested anywhere and by anyone. This would, apparently, both deter states from harbouring terrorists, and deter the US, UK, China and others from abusing the term "terrorist" to crack down on their own populations, deny human rights to terrorist suspects and so on. Full article here. r_e_mercia and mi_guida (and any others, of course), a penny for your thoughts.

Yesterday I found a mistake in a paper ("A General Coherence Result" by John Power, if you're interested). The mistake itself is trivial - an equation failed to typecheck, it took about a minute to fix and another couple of minutes to be sure that it really was an error, and the mistake had no knock-on effects - but this still disquiets me. This was a paper by a highly-regarded mathematician, presenting a significant result, that had passed refereeing and been published. The paper's written in a very clear style, uses a notation that makes that kind of error immediately obvious, and it's only nine pages long! I read the whole thing in a couple of hours, and I wasn't reading it that closely. If an error that obvious, and that simple to find and fix, can make it through to a published paper, then we are all doomed. Forget worries about errors in the 11,000-page proof of the classification of finite simple groups (see Marcus du Sautoy's excellent New Scientist article), if we can't keep errors out of something only 9 pages long then the entire notion of peer-review (and possibly even proof) becomes bunk, and the only thing to be done with things like the finite simple group proof is to burn them, lest anyone be tempted to take them seriously. I've mentioned my idea for statistical estimation of error rates in proofs before - anyone else care to proffer ideas? It occurs to me that the FSG proof is of a similar size (and probably a greater complexity) to the Linux kernel: Debian's bug database reveals about 300 open kernel bugs, but that's probably only the tip of the iceberg.

[By the way, there's what looks like a good article in the New Yorker on the Perelman-Yau Fields Medal snafu.]

Another idea/problem of which everyone should be aware.

The problem is simple: a philosopher has an axe (bear with me here). He uses it for a while, until the blade wears out and has to be replaced. He uses it for a bit longer, until the handle breaks. The head's still OK, so he puts it on a new handle.

Is the axe he has now the same axe as the one he started with?

Wikipedia calls this the Ship of Theseus paradox, and gives examples from fields as diverse as rock music and automobile registration fraud, some with serious consequences. It's a problem that often comes up in discussions of the feasibility of Star Trek-style matter transference. Like so many important philosophical problems, the answer depends on what your definition of "is" is, and these are seriously deep waters. As a mathematician, it depends on what context you're operating in: sometimes two things can be the same for one purpose but different for another. Two groups can have the same elements, and thus be the same for the purposes of set theory, but have quite different algebraic structure. Or vice versa - two groups might happen to have different names for their elements, but exactly the same structure, in which case we'd call them the same group. Topologists will frequently say that two objects are "the same" when they're homotopic, which is a very weak condition - for instance, Euclidean n-dimensional space is homotopic to a single point for all n. This can all be made precise using category theory: each category will have a different notion of isomorphism, and you say that two things are "the same" when they're isomorphic in the appropriate category. But then you get into higher categories, and it all goes wrong: in a 2-category, the moral notion of "the same" isn't isomorphism but rather equivalence...

By the way, I once mentioned the Philosopher's Axe to an ice climber. He said that ice-axe heads wear out all the time, and that when you replace the handle then you've got a new axe, regardless of whether you then put an old head on it :-)

[By the way, it seems my Lie Algebras lecture wasn't as bad as I'd thought. Catharina said I'd done well to get the whole theorem into one lecture, albeit one that ran nearly half-an-hour over time...]