Mark Proctor of the JBoss Rules team gave me the heads up about an interesting debate (here and here) about First Order Logic (FOL) and whether various BRE’s do or should support it. One question that has come up is whether BRE’s can still be said to be Turing Complete? Actually, the two questions — whether a BRE supports FOL and whether it is Turing Complete — are quite seperate.

Turing Complete

First the easy question: when is a system Turing Complete? From the Wikipedia:

In computability theory, an abstract machine or programming language is called Turing complete, Turing equivalent, or (computationally) universal if it has a computational power equivalent to (i.e., capable of emulating) a simplified model of a programmable computer known as the universal Turing machine. Being equivalent to the universal Turing machine essentially means being able to perform any computational task – though it does not mean being able to perform such tasks efficiently, quickly, or easily.

So, what is a Turing machine? Again you can look at the Wikipedia, but in a nutshell, it’s a tape with an infinite number of cells, a read/write head, a finite alphabet that the head can write to a cell, a finite number of ‘states’ that the machine can be in, and a finite number of rules that say things like “if you are in state 3 and the symbol on the tape is ’0′, the write a ’1′, move the head one cell to the right and change your state to 8.”

While this may seem like a silly sort of machine (just try to write a word processor with it), it can do anything, given the right number of states and the right set of rules, that a von Neuman style of computer — essentiall the sort of computer with which you are reading this blog — can do. It’s handy for proving certain theorems about computability and complexity. If you can write any Turing machine with your device, then it is said to be a Universal Turing Machine, i.e. if you can compute it with an algorithm, you can do it with your machine. It should be obvious that a BRE, even without First Order Logic, is a UTM. We can have a fact that tells us what our state is, another fact that tells us where our read/write head is, a set of facts that represent all of the cells we’ve seen so far, and our rules that govern how our state, head and cells are modified. Therefore a BRE is Turing Complete.

Of course there’s a small fly in the ointment. Up above we said that a turing machine had an “infinite” number of cells. Of course your computer can’t accomodate an infinite number of cells, since it has a finite amount of memory and storage. This is a rather important point, as it turns out. Anything program running on a modern computer with finite memory and storage is at best a Finit State Machine, basically the most primite of the interesting algorithms. But in principle, a BRE with infinite memory is Turing Complete.

First Order Logic

I’ll try to stay a little non-technical here, mostly because all of my math text books are in storage. First Order Logic (or First Order Predicate Logic) is an extension of regular propositional logic with the addition of the universal and existential quantifiers. That means we can write conditions in our rules that are true for all facts of a particular type in our fact base or which are true for at least one fact. I’ve written before why having First Order Logic built into your BRE is a good thing. In short, you can work around your BRE not having it, but you’ll lose the performance advantage of your rule execution algorithm in the process, such as RETE. And there are plenty of scenarios where you are looking at an event history of a customer or client that call for FOL.

You can see, however, that our simulation of a Turing machine above never called for a quantifier. Thus even a BRE without FOL is Turing Complete (if it has infinit memory, yada yada). I hope this explanation I hope this entry has been useful and not too geeky. Behind all of the hype behind BRE’s, it is sometimes useful to understand what exactly they are and what they can do.

Share/Bookmark