Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!zaphod.mps.ohio-state.edu!wuarchive!udel!haven.umd.edu!socrates.umd.edu!socrates!rockwell From: rockwell@socrates.umd.edu (Raul Rockwell) Newsgroups: comp.theory Subject: Re: Paradox of the non-recursive computer Message-ID: Date: 10 May 91 04:04:24 GMT References: <11943@uwm.edu> <11977@uwm.edu> Sender: rockwell@socrates.umd.edu (Raul Rockwell) Organization: Traveller Lines: 29 In-Reply-To: markh@csd4.csd.uwm.edu's message of 9 May 91 02: 43:56 GMT me: er... while it may exist for formal theories, I don't see how that me: makes it more powerful than a TM. me: In other words, what's the paradox?? Mark William Hopkins: > It's a replication of the Goedel's Completeness proof. It "computes" > a Complete theory consistent with the axioms of arithmetic (let's > say) in the sense that it will arrive at an answer for any > proposition in finite time. > No Turing Machine has that ability. No turing machine has the ability to determine if a wf is consistent with a formal theory??? But all you have to have is a good model. For example, if your formal theory is equivalent to predicate calculus then it is a simple matter for a turing machine to determine if a wf is consistent. > Yet at all finite times it has only "computed" a finite subset > (which IS actually recursively computeable), so that at any given > time it is never more powerful than even a Finite State Machine, let > alone a Turing Machine. Well, that's mostly hand waving, but it tends to show that what you are talking about is turing computable. Raul Rockwell