The Constructability of Artificial Intelligence - Bruce Edmonds

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' (e.g. Cutland, 1980: 81) 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 1936).

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 a theoretically implementation but not an effective implementation 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 implement all such theoretically realisable implementations, there must be some arbitrary or non-computable element. If it is arbitrary or non-computable one can not say that it is effective. Thus at least some theoretically implementations are not systematically realisable (as in "implemented as result of a deliberate plan to do so").

The Constructability of Artificial Intelligence - Bruce Edmonds - 17 JUN 99

[Next] [Previous] [Top] [Contents]

Generated with CERN WebMaker