Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!uwm.edu!csd4.csd.uwm.edu!markh From: markh@csd4.csd.uwm.edu (Mark William Hopkins) Newsgroups: comp.theory Subject: Re: Paradox of the non-recursive computer Message-ID: <11977@uwm.edu> Date: 9 May 91 02:43:56 GMT References: <11943@uwm.edu> Sender: news@uwm.edu Organization: University of Wisconsin - Milwaukee Lines: 15 In article rockwell@socrates.umd.edu (Raul Rockwell) writes: >er... while it may exist for formal theories, I don't see how that >makes it more powerful than a TM. > >In other words, what's the paradox?? 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. 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.