FOM: 70:Efficient Formulas and Schemes
Raatikainen Panu A K
Praatikainen at elo.helsinki.fi
Tue Nov 2 03:37:37 EST 1999
This is very interesting. These notions of efficiency are exactly the
same (well, not alpha efficiency) that I pursued a couple of years
ago. But my motivation came from the philosophy of science,
where simplicity has played an important role. E.g. Hans
Reichenbach considered various notions of simplicity of a theory,
and the simplest of the logically equivalent variants was one.
My quick observation was (although I guess this may be obvious
for Friedman, let me state it anyway):
FACT. The property of being efficient is not decidable; in fact, it
is not even r.e. It is co-r.e.
Take some simple contradiction, say P(a) & -P(a), with complexity
6 . If one manages to demostrate that a sentence/theory more
complex than this is efficient, one has also demonstrated that the
sentence or theory is consistent (for if it is inconsistent, it is
logically equivalent to a shorter formula P(a) & -P(a), and therefore
not efficient). But the set of consistent sentences is not r.e., and
consequently the set of efficient sentences and theories is not r.e.
Of course, it is easy to see that the set of non-efficient
sentences/theories is r.e. One simply enumerates all the theorems
of predicate logic, and is a theory T is non-efficient, one eventually
meets a theorem T <-> S, where S is simpler than T.
(I hope I got it all right ...)
Note that I was thinking only of efficiency of sentences and beta
efficiency of theories, not alpha efficiency .
Any comments, any criticism ?
Department of Philosophy
University of Helsinki
E-mail: panu.raatikainen at helsinki.fi
More information about the FOM