Turing Complete = Incomplete

I’ve talked about this a little bit before, but I’ll start over, since I have a new understanding of the problem now.

Gödel’s famous incompleteness theorem says that “any consistent, recursive set of axioms which can emulate arithmetic cannot be complete”. He showed this by essentially building a Turing machine (well, something equivalent to one) inside the logical proof system, and showing that there was a halting problem in that system.

I’ve been wondering this: You can show a system is incomplete by embedding arithmetic in it, so what other types of incomplete systems are there? Can you have an incomplete system which does not have arithmetic? Is it weaker than an arithmetic system (in which case, is there a minimal embedding that will get you to an incomplete system?), or just different?

Now I should take a moment to define my terms, because I’ve been using incomplete rather loosely. Incomplete means that there is a statement φ for which neither φ nor ¬φ is provable. The empty set of axioms is incomplete. That is of course not what I meant.

Definition: A consistent set of axioms A is called strongly incomplete if there is no recursive set of axioms R such that A ∪ R is complete.

Definition: A consistent set of axioms A is called recursively completable or weakly incomplete if it is not strongly incomplete, i.e. if there is a recursive set of axioms R such that A ∪ R is complete.

So above when I said “incomplete”, I meant “strongly incomplete”. I have a conjecture:

Conjecture: Every strongly incomplete set of axioms is capable of embedding arithmetic.

That would mean, in essence, that the only way you can be strongly incomplete is by being Turing complete. Intuitively I believe this conjecture, if only because of the appearance of the word “recursive” in the definition of strongly incomplete.

I have started to approach a proof, though I admit it’s somewhat out of my league. Still, it’s fun to explore. The best way to go about it I’ve found so far is to find a Turing complete system such as arithmetic, lambda calculus, group algebra, or diophantine equations and show that if a system is incapable of emulating that system, then it must be recursively completable.

You start with a set of axioms A and say, for example, for all wffs N(x), Z(x), S(x,y), the sentence ¬”N(x) means x is a number, Z(x) means x = 0, and S(x,y) means y = x + 1″ is consistent with A. The bit in quotes actually expands to a conjunction of four reasonably complex formulas, so its negation turns into a disjunction. Disjunctions are not very nice to work with from a proof standpoint. But it’s still a very powerful assumption, since this is for all wffs (with the desired number of free variables), so we can pick and choose ones that are convenient for our goal. We can also assume that the negation is actually provable in A, because if it’s just consistent, why not just add it to the set S we are using to complete A? We can actually add all of these negations to S (for all appropriate wffs) right off the bat, because the set is recursive.

As for how to show the rest of the completion, I’m stumped so far. I need some time to explore this system a bit; I’ve gone so far as to write down the expression of the axioms and negate them, playing around with different representations, but I haven’t really tried to get new consequences from them yet.

About these ads

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s