Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!usc!wuarchive!uunet!mstan!sethb
From: sethb@Morgan.COM (Seth Breidbart)
Newsgroups: comp.theory
Subject: Re: Paradox of the non-recursive computer
Message-ID: <3250@ylum.Morgan.COM>
Date: 8 May 91 22:14:46 GMT
References: <11943@uwm.edu>
Organization: Morgan Stanley, & Co., Inc. / New York City, NY
Lines: 50

In article <11943@uwm.edu> markh@csd4.csd.uwm.edu (Mark William Hopkins) writes:
|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).

Or, T(0) = T

|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")

Well, "exists" may not be the right word.

|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?

Define "computing".  You have a machine that from time to time outputs
a statement.  Why do you say it is "computing"?

|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?

Well, if I can observe it for only a finite time (=finite number of
state transitions), then I can't tell it isn't a finite state
automaton programmed to do exactly what I've observed.  Of course, the
same holds true for observing any machine.  If you can only observe a
Turing Machine for a finite amount of time, you can't prove it's not a
finite automaton.

However, for any particular Turing Machine, I can eventually show that
your machine is not the same as that Turing Machine.  I can even give
you an upper bound on how long it will take.

|Hence a paradox.

Where?

Seth		sethb@fid.morgan.com