The Possible Irreducibility of Artificial Software Life - Bruce Edmonds

In the discussion below,

According to the above characterization "*L is reducible*" is interpreted as "*There is a program p that computes L*". This is not a constructive definition, it is sufficient that such a program *exists*, it does not mean that there would have to be any practical or systematic way of building such a program.

If whenever we could compute *L* (with a program *p*), we could also compute *p* from *L*, then the mere existence of such a program, *p*, would be sufficient - as we would also know that we could compute that program.

If, on the other hand, there were cases where there is a program *p* that computes *L*, but *there is no way* to compute that program *p* from *L*, then it is clear that it is, at the very least, highly misleading to say that "*L* is reducible". In such a case it may be possible to come across the program *p* by accident, but then we would still need to check that it was the correct program. Given the assumption above, this would not be even *semi-decidable* for if it were then we could use this to construct a program to compute *L*, which would contradict the assumption that *L* was not computable from *p*.

Below we show that, *given plausible limitations on our programming ability*, such cases do exist. Thus the above characterization of reducibility is too weak. Unless there is some calculating devices more powerful than a Turing machine, in order for *L* to reduce it, *we* (aided by computers etc.) must be able to find a program to compute it. If this is not to be the result of an unverifiable accident we must be able to somehow *compute the program that computes L*.

We can formalise the situation in the following way. *L* is a statement in some recursively axiomatized logic. So the statements in this logic can be effectively enumerated
. Similarly enumerate the possible programs
.

We then say,
, or
a *theoretical reduction*, if

Then define
, or
is an *systematically realisable reduction* if, in addition to condition (1),

The question then becomes, given any particular
, encoding a systematic method of building a programs from statements in this language, *"Are there pairs
that are a theoretical reduction but not a systematically realisable reduction?"*. In other words Is there a difference between the normal criterion of computability and such "systematically realisable computability"? The answer to this is *"Yes"*, as I now show

Theorem

Proof Outline

We consider a series of statements, indexed by the natural numbers, *n*, representing what I call the *limited halting problem*, i.e. *"for all
(fixed) program
halts given input
"*. Call this
, in contrast to the full halting predicate
(*"program
halts given input w"*). This is a finite function, hence it is computable in the sense that for each *n* there exists*1 a program
that decides
. Thus for each separate *n*,
is theoretically reducible.

If for all *n*
is a theoretical reduction then this would allow us to also decide
, since by the s-n-m theorem (page 81 of [1]) there is a computable function, *q*, such that
. Then
would be decided by
, and thus
would be computable, which we know is not the case (Turing [7]).

Thus for any
there is an
, and a program *q*,
but not
.

Here, you have to be careful about the indexing. What the above theorem does not say is that there is a pair that is theoretically reducible but not intentionally reducible given *any* program
. After all, given any particular pair one could simply add this as a special case in your plan represented by a program
*'* that would compute an index for a program to compute the first of the pair from the second. The point is that there is no *systematic* way of doing this short of adding special cases for all such cases (an infinite number of them). So if you are going to reduce *all* such theoretically reducible pairs, there must be some arbitrary or non-computable element. If it is arbitrary or non-computable one can not say that one intended its results. Thus at least some theoretically reducible statements are not systematically realisable reducible (as in "reduced as result of a deliberate plan to do so"). This is not very surprising given the string of uncomputability results this century, starting with Turing [7] and GÖdel [2].

What the above shows is that there is a real difference between was is *theoretically reducible* and what is *systematically realisable reducible* and that defining something as reducible if it is only theoretically reducible and not intentionally reducible is not sensible as there would be *no guarantee* that there was a *practical *way of performing this reduction*2. Thus just because a program *exists* does not mean that there is an systematic way of programming it. In a real sense there are programs that are unreachable using systematic means.

The Possible Irreducibility of Artificial Software Life - Bruce Edmonds - 20 MAY 97 [Next] [Previous] [Top] [Contents]

Generated with CERN WebMaker