Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!dali.cs.montana.edu!caen!uwm.edu!csd4.csd.uwm.edu!markh
From: markh@csd4.csd.uwm.edu (Mark William Hopkins)
Newsgroups: comp.theory
Subject: Paradox of the non-recursive computer
Message-ID: <11943@uwm.edu>
Date: 8 May 91 08:01:54 GMT
Sender: news@uwm.edu
Organization: University of Wisconsin - Milwaukee
Lines: 27

You can enumerate all the statements of a formal logic system, A0, A1, A2, ...
Consider a family of sets T0, T1, T2, ..., built on an axiom base T.  Each
set is incremented from the previous in the following way:

       T(n+1) = T(n) + [An] if statement An is consistent with Tn + axioms T.
       T(n+1) = T(n) + [not An] if statement An is inconsistent with Tn + T.

(T(-1) is set to the empty set).

Since each set is a finite set of statements, it's computeable.

Consider an abstract machine that correctly emulates T0, T1, T2, and so on.
It exists, according to the Axiom of Choice, but is more powerful than a
Turing Machine (and thus "non-computeable")

Yet at any point in time it has only "computed" a finite set and can thus be
emulated by a finite machine.  So is this machine actually computing or not?

My answer is yes.  It's a non-recursive computer.

And if you answer no, then the next obvious question is this: if you actually
had such a machine before you how would you recognize so, seeing that it only
calculates finite sets at finite times?  In other words, how can one ever
possibly hope to falsify the "no" position when it would take an infinite
amount of time to recognize a counter-example as being such?

Hence a paradox.