FOM: 70:Efficient Formulas and Schemes

[Raatikainen Panu A K]

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 ?

Panu Raatikainen
Assistant Professor
Department of Philosophy
University of Helsinki
Finland

E-mail: panu.raatikainen at helsinki.fi