FOM: 70:Efficient Formulas and Schemes
Stephen Fenner
fenner at cs.sc.edu
Wed Nov 3 11:04:28 EST 1999
On Tue, 2 Nov 1999, Raatikainen Panu A K wrote:
> 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.
You show that the beta-efficient sentences/theories form a subset of the
consistent ones, but this doesn't imply that the former is noncomputable
(or non-r.e.) simply because the latter is. Nevertheless, you're right
that the set is co-r.e., and it's a reasonable guess that that it's
non-r.e. as well.
This set (of beta-efficient sentences/theories), which I'll call bE, seems
to be closely related to the set R of Kolmogorov random strings. R is
co-r.e. and Turing-equivalent to the halting problem. It also bears some
resemblance to the set MIN of minimal programs:
MIN = { e | the partial function computed by the e'th Turing machine is
different from that of the i'th machine, for all i < e }.
A lot is known about MIN. In particular, it is Turing-equivalent to 0''
(the halting problem relative to the halting problem).
CONJECTURE: bE is recursively isomorphic to (a different coding of) bE.
Steve
More information about the FOM
mailing list