```X-Message-Number: 23876
References: < var s1 = "20040412090001.88893.qmail"; var s2 = "rho.pair.com"; var s3 = s1 + "@" + s2; document.write("<a href='mailto:" + s3 + "'>" + s3 + "</a>"); >
From: Peter Merel < var s1 = "peter.merel"; var s2 = "mac.com"; var s3 = s1 + "@" + s2; document.write("<a href='mailto:" + s3 + "'>" + s3 + "</a>"); >
Subject: Easy Godel and Turing Workarounds
Date: Tue, 13 Apr 2004 10:10:14 +1000

Godel's incompleteness theorem provides a procedure that, for any
sufficiently powerful formal system, creates a statement in that system
which cannot be consistently proved by that system.

It is generally concluded from Godel that all formal systems are either
incomplete or inconsistent. But in fact Godel's theorem assumes the law
of the excluded middle. That law holds that any statement in a
sufficiently powerful formal system is either true, or otherwise its
negation is true.

In a formal system that includes the value "ambiguous", Godel's theorem
presents no difficulty. Of course almost all set theory, and so almost
all mathematics, is based on the excluded middle. Mathematicians
generally rather ignore the framing problem explicated by Godel than
start creating number systems all over again with an inclusive middle.
So we're asked to accept the present quagmire as the ne plus ultra.
Best response to that: balderdash!

The General Halting Problem is similarly trite. Turing's original 1936
proof declaims that the halting problem only afflicts the "A Machine",
an abstract computing device with several unrealistic assumptions built
in. These are:

* No external signals sent or received. The A Machine has no
interaction with the outside world; consequently it is not equivalent
to any computer available for use by humans. Turing describes but
proves nothing about the function of the "C Machine", which does
interact with external signals.

* Infinite independent states. The A Machine includes an infinite
length static tape. As described in
http://www.cryonet.org/cgi-bin/dsp.cgi?msg=22106 and its sequelae,
there is no necessary reason to think physical infinities exist.
Plainly the halting "problem" does not apply to a machine with finite
states. Likewise it does not apply to machines whose encodings of state
are not purely static or purely independent; quantum entanglement is
sufficient but actually not necessary to the construction of machines
that violate this assumption. A simple pin-sort in an old card reader
violates it, as do most address busses, MUXes, and so on.

* One toggle per iteration. The A Machine's "read write head" can only
alter one cell on its paper tape per iteration. But all digital
computers available to us alter many of their states per iteration, and
there is no obvious physical limit to this parallelism.

In other words the "generality" of Turing's proof relies on another
framing failure. The General Halting Problem, and with it most of
modern computer science, rests on no empiricism. It is probably fair to
think that Turing is relevant but not prescriptive concerning the
limits of the abilities of Von Neumann architecture computers. But VN
based his architecture explicitly on Turing's abstraction; there are
many other practicable architectures. The Field Programmable Gate Array
is a very commonly deployed one for which Turing is completely
irrelevant.

As for natural C machines - flowers and butterflies for example - it
seems best we junk Turing and Godel and start over considering
computers as signal processors rather than state machines.

Peter Merel.

Rate This Message: http://www.cryonet.org/cgi-bin/rate.cgi?msg=23876

```