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