Gödel, Grammar, Go – the Limits of Rules and Facts

More than eighty five years ago  Kurt Gödel proved, roughly speaking, that no fixed set of a formal facts (like 23+14=37) and rules (like x+y = y+x) can establish the truth or falsity of every theorem about arithmetic over the counting numbers.

This result, known as Gödel’s Theorem, has a lot of formal and informal consequences. It means there is no computer program that can infallibly decide whether or not a statement about arithmetic is true or false. It means we will never know everything about arithmetic, though we may know more and more as time goes on. It means, however, that this knowledge will not come about purely as a result of manipulating formal facts and rules. We will have to rely on other sources, including experiment.

Even more interesting is the fact that this situation – the limits of facts and rules – reappears in other domains, including games, natural language, and even psychology.

Continue reading

Posted in Uncategorized | Leave a comment

Logic without Bound Variables

I’ve already described the relatively simple Monadic Hybrid Calculus that allows you to say simple things formally without bound variables. For example, sG may mean “Socrates is Greek”, [G]M “all Greeks are Mortal”, and the conclusion “Socrates is Mortal”, sM.

The MHC has a big brother, the Hybrid Predicate Calculus (HPC), which (apparently) has the power of full predicate logic. But at a certain point, it gets weird!

Continue reading

Posted in Uncategorized | Leave a comment

My Video Career

A while back I decided that it would easy and useful to video record  some lectures. Little did I know!

Continue reading

Posted in Uncategorized | Leave a comment

Al-Khwarizmi Schmal-Khwarizmi


I  like  true/false exam questions and through my career have thought up hundreds of them. Every now and then, for comic relief and to inflate the grades, I include some that are ridiculously easy. However, I’ve never found one that is so ridiculous that everyone gets it right. I always had a few takers. Here are some of my favourites.

Continue reading

Posted in Uncategorized | 1 Comment

Extensional Higher Order Prolog

One big issue in the logic programming vs functional programming debate is logic programming’s (or at least the original Prolog’s) restriction to first order logic. To functional programmers this constraint is intolerable; even the simplest Haskell programs are higher order (although this is often due to currying).

Can this be fixed? Yes, but you have to be careful.

Continue reading

Posted in research | 2 Comments

Department of Redundancy Department

If you ever took an English course. you learned that “redundancy” is a bad thing. It means useless, wasted repetition. If you live in the UK you dread being made “redundant” because it means your boss has no use for you and has laid you off.

Only in engineering can it have a positive connotation – for example, a redundant duplicate backup system can be a good idea for safety and reliability. It’s repetition but it’s not useless or wasted.

In fact redundancy is widely used in practice and duplication/backup is only the simplest form. I discovered this trying to make sense of a multi-topic introductory computer science course.

Continue reading

Posted in musings | Leave a comment

Wadge Degrees

When I was a young grad student at UC Berkeley, I invented what are now called “Wadge degrees”. Not to mention “Wadge reducibility”, “Wadge games”, “Wadge’s Lemma” and the “Wadge hierarchy”  (there’s a Wikipedia entry on the latter).

“So”, I am often asked, “what is this all about?”

Short answer: Wadge reducibility is a simple  way to compare the complexity of two properties (sets) of real numbers. If A and B are two such sets, A≤WB (or simply A≤B) iff there is a continuous total function f such that for all reals a

a is a member of A iff f(a) is a member of B

Continue reading

Posted in research | Leave a comment