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

Lucid Meets Prolog

I remember when, a long time ago, Logic Programming was just starting out. The logic programmers would go to the functional programming gatherings and hang around the sidelines, hoping to convince everyone that logic programming was a kind of functional programming worthy of attention.

Then came the Japanese “Fifth Generation” project (which was based on Prolog) and the situation was reversed. Functional programmers would loiter in the hallways at Logic Programming conferences trying to convince everyone that functional programming was a kind of logic programming worthy of attention.

Neither side ever succeeded, partly because of serious technical difficulties. Functional programming is deterministic; a program has only one answer. Adding nondeterministic operators (like McCarthy’s amb(a,b), which returns either a or b) messes up the least fixed point semantics. Attempts to handle this with a “power domain” construct never really worked.

Continue reading

Posted in research | 1 Comment

Universal Hybrid Calculus

The Universal Hybrid Calculus (UHC) is a simple logical formalism that has the power of the monadic predicate calculus but has no bound variables. Natural language statements (which also do not use variables) can be formulated more directly in the UHC. In particular, the UHC, like natural language, uses quantifier phrases (such as some Greeks or all mortals) rather than quantifiers and variables.

(This is joint work with my PhD student Omar Alaqeeli)

The UHC is based on the simplest of the modal logics, S5. S5 can be explained (in a nonstandard way) as follows: there is a nonempty universe of individuals (say, people). Properties of individuals are denoted by property constants, which are upper case letters. For example, M might denote the property of being mortal, and G the property of being Greek. Boolean combinations of property constants also denote properties in the obvious way; so that e.g. G∧M denotes the property of being Greek and Mortal.

Continue reading

Posted in research | Leave a comment

I deduce you are studying logic

This summer I was at LC2015, the big European logic conference (it was great). I was sitting listening to a talk with one of my logic buddies when the speaker mentioned “deontic logic”, which is a fancy Greek name for the logic of obligations.

A thought popped into my mind; I turned to my friend and whispered, “you ought to study deontic logic”. Ha ha ha! A self-referential statement!

My friend wasn’t exactly convulsed with laughter but never mind. A whole research program opened up before me – self descriptive “studying <adjective> logic” sentences.

Continue reading

Posted in musings | 18 Comments