----- Original Message ----- From: "Joshua Bell" <[EMAIL PROTECTED]> To: "Brin-L" <[EMAIL PROTECTED]> Sent: Tuesday, March 12, 2002 11:33 PM Subject: Re: SCOUTED: Science Meets Spirituality, and Wireless Nanotech VR
> "Dan Minette" <[EMAIL PROTECTED]> wrote: > > > >From: "William T Goodall" <[EMAIL PROTECTED]> > > > > > It hasn't. Every undergraduate in computer science learns (I assume) > >about > > > Turing Machines, the Halting Problem, Godel, Skolem, predicate calculus > >and > > > etcetera and so forth. Anyone who does an advanced degree in AI knows > >all > > > this stuff backwards. > > > >Formal systems are actually complete? There exists a universal Turing > >Machine? > > Do you claim that humans can *always* answer the question "this program will > or will not halt in finite time" given any program and its inputs? No. And I should probably clarify what I wrote, because I may have used nomenclature in a non-standard manner (the nomenclature was used from memory). By "Universal Turing Machine, I define a machine that can determine when every other Turing machine will stop. The reason this is important is that it is tied into the proof of true statements in a formal system. My understanding of what Godel proved is "every formal system at least as complicated as arithmetic will have true statements that cannot be proven within the system." These statements are (usually always?) self-referential statements. Humans have means of handling these statements. Humans can find ways to prove these statements outside of the formal system. This is one of the main arguments against considering human thinking as algorithmic: we can handle these self-referential statements. Its not that humans can make such predictions; they can't. Its that the ability to handle what humans do algorithmically involves the completeness of algorithms. That's why the question of a universal Turing machine is important. Dan M.
