X-Message-Number: 23876
References: <>
From: Peter Merel <>
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 

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