Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!cs.utexas.edu!uwm.edu!zaphod.mps.ohio-state.edu!brutus.cs.uiuc.edu!apple!sun-barr!newstop!sun!amdahl!kp From: kp@uts.amdahl.com (Ken Presting) Newsgroups: comp.ai Subject: Re: Dear Roger, Summary: Randomizing devices supply *Carnap* information, not *Shannon* Keywords: Moravec, randomizing, Turing machines Message-ID: Date: 12 Feb 90 23:07:43 GMT References: <2206@castle.ed.ac.uk> Reply-To: kp@amdahl.uts.amdahl.com (Ken Presting) Organization: Amdahl Corporation, Sunnyvale CA Lines: 39 In article <2206@castle.ed.ac.uk> aipdc@castle.ed.ac.uk (Paul D. Crowley) writes: >I am a little confused by one part of this letter, which seems to >suggest that including a randomizing device increases the problem >solving capacity of a machine. I would have thought that that any >non-random machine wishing to solve the same problems could explore all >the paths that a random machine could take. I think you are correct. This slipped past me on the first reading, but now I think I know what's going on, at least partly. Moravec began the section with the randomizing technique by observing that the inability of an algorithm to add true unprovable theorems to an axiomatized theory is due to the finite information content of algorithms. He explained the significance of the randomizing device in terms of its potential for adding information to the system which is executing the algorithm. In support of your point, according to the Shannon/Weaver information theory, a channel which always transmits a random signal carries no information at all, if all "messages" are equiprobable. Not to mention that non-deterministic Turing machines are known to be equal to the deterministic variety, in terms of functions computed if not speed. I think the situation changes somewhat if the information source is not random. The logical procedure described by Moravec corresponds closely to some accounts of *scientific* reasoning (as opposed to mathematical), such as Popper's. So let's suppose Moravec's machine is a hypothesis- tester, and the signals it gets from the information source are like scientific observations, perhaps increasingly precise measurements of fundamental constants. Then, supposing that the system can make use of the input, it's information content can increase. But there are very serious problems with extending this process to full-scale science. If a constant coding scheme is used to represent the input measurements, the system would be unable to participate in major scientific conceptual changes, such as relativity or QM caused. Of course, there is always the old reliable (if mundane) technique for increasing the information content of a system, Data Entry. All by itself, this everyday event shows that real computers are different from abstract automata.