From owner-cse584-sp07-list@LISTSERV.BUFFALO.EDU Sun Feb 25 20:23:59 2007 Received: from ares.cse.buffalo.edu (ares.cse.Buffalo.EDU [128.205.32.79]) by castor.cse.Buffalo.EDU (8.13.6/8.12.10) with ESMTP id l1Q1NxMj021755 for ; Sun, 25 Feb 2007 20:23:59 -0500 (EST) Received: from front3.acsu.buffalo.edu (upfront.acsu.buffalo.edu [128.205.4.140]) by ares.cse.buffalo.edu (8.13.6/8.13.6) with SMTP id l1Q1NsaH059597 for ; Sun, 25 Feb 2007 20:23:54 -0500 (EST) Received: (qmail 26654 invoked from network); 26 Feb 2007 01:23:54 -0000 Received: from mailscan5.acsu.buffalo.edu (128.205.6.137) by front3.acsu.buffalo.edu with SMTP; 26 Feb 2007 01:23:54 -0000 Received: (qmail 11200 invoked from network); 26 Feb 2007 01:23:53 -0000 Received: from deliverance.acsu.buffalo.edu (128.205.7.57) by front1.acsu.buffalo.edu with SMTP; 26 Feb 2007 01:23:53 -0000 Received: (qmail 10232 invoked from network); 26 Feb 2007 01:23:37 -0000 Received: from listserv.buffalo.edu (128.205.7.35) by deliverance.acsu.buffalo.edu with SMTP; 26 Feb 2007 01:23:37 -0000 Received: by LISTSERV.BUFFALO.EDU (LISTSERV-TCP/IP release 14.5) with spool id 3551477 for CSE584-SP07-LIST@LISTSERV.BUFFALO.EDU; Sun, 25 Feb 2007 20:23:37 -0500 Delivered-To: CSE584-SP07-LIST@LISTSERV.BUFFALO.EDU Received: (qmail 13321 invoked from network); 26 Feb 2007 01:23:07 -0000 Received: from mailscan8.acsu.buffalo.edu (128.205.7.55) by listserv.buffalo.edu with SMTP; 26 Feb 2007 01:23:07 -0000 Received: (qmail 19185 invoked from network); 26 Feb 2007 01:23:07 -0000 Received: from hadar.cse.buffalo.edu (128.205.32.1) by smtp4.acsu.buffalo.edu with SMTP; 26 Feb 2007 01:23:07 -0000 Received: from hadar.cse.Buffalo.EDU (ag33@localhost [127.0.0.1]) by hadar.cse.Buffalo.EDU (8.13.6/8.12.10) with ESMTP id l1Q1N6mL010930 for ; Sun, 25 Feb 2007 20:23:06 -0500 (EST) Received: (from ag33@localhost) by hadar.cse.Buffalo.EDU (8.13.6/8.12.9/Submit) id l1Q1N68S010928; Sun, 25 Feb 2007 20:23:06 -0500 (EST) MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII X-UB-Relay: (hadar.cse.buffalo.edu) X-PM-EL-Spam-Prob: : 7% Message-ID: Date: Sun, 25 Feb 2007 20:23:06 -0500 Reply-To: Albert Goldfain Sender: "Philosophy of Computer Science, Spring 2007" From: Albert Goldfain Subject: TM encoding schemes and a loss of generality To: CSE584-SP07-LIST@LISTSERV.BUFFALO.EDU Precedence: list List-Help: , List-Unsubscribe: List-Subscribe: List-Owner: List-Archive: X-UB-Relay: (hadar.cse.buffalo.edu) X-DCC-Buffalo.EDU-Metrics: castor.cse.Buffalo.EDU 1335; Body=0 Fuz1=0 Fuz2=0 X-Spam-Status: No, score=-2.6 required=5.0 tests=AWL,BAYES_00 autolearn=unavailable version=3.1.7 X-Spam-Checker-Version: SpamAssassin 3.1.7 (2006-10-05) on ares.cse.buffalo.edu X-Virus-Scanned: ClamAV 0.88.6/2653/Sun Feb 25 16:24:16 2007 on ares.cse.buffalo.edu X-Virus-Status: Clean Status: R Content-Length: 2221 I think there is at least one sense in which the universal turning machine (UTM) is "hard-wired" and not general. The UTM's inputs are an integer-encoded TM and an integer i. Let's call the encoding scheme Turing devised from Turing (1936)e "TuringEnc", and write: UTM(TuringEnc(TM),i) computes TM(i) Now if we came up with another encoding based on Godel numbering, call it "GodelEnc", it is clear that UTM(GodelEnc(TM),i) will not behave correctly (i.e., it might accidentally produce TM(i) for some i, but certainly not for all i). Now one might claim that there is a TM that could simulate the encoding scheme (since it is a function)...call this TM_TuringEnc so UTM(TuringEnc(TM_TuringEnc),i) should do the job right? wrong! because "i" here has to be a TM (Turing machines *are* the domain of the encoding function). Thus, for any encoding function to be computable, we must arrange for it to take as input an integer-encoded TM *that uses yet another encoding scheme* (the regress would be a vicious one). Assumed pre-encoded TM input I/P: enc(TM) i \ / | UTM | / \ O/P: TM(i) ---------------------------------- Encoder "machine" is needed with some other scheme enc2 I/P: enc2(TM) \ / | encoder | / \ enc(TM) i \ / | UTM | / \ O/P: TM(i) If this is correct then each UTM must have hard-wired the decoding-scheme complementary to the encoding scheme used. This would yield a set of UTMs: UTM_TuringEnc UTM_GodelEnc And this looks really familiar :-P UTM_PC UTM_Mac The PC and Mac can run each other's programs only when Apple and Microsoft share "encoding schemes" (or they are reverse engineered :)) So I believe saying "A UTM is general" is really elliptical for "A UTM is general for TMs encoded by some particular encoding scheme". I believe the human brain suffers from the same "hard-wiredness". If you replace the "encoding scheme" with the presentation of our "perceptual input" it is pretty clear that UTM_HumanBrain *expects* patterns of neuron firings as "input" rather than cats, mice, and cheese :) Albert From owner-cse584-sp07-list@LISTSERV.BUFFALO.EDU Sun Feb 25 22:11:17 2007 Received: from ares.cse.buffalo.edu (ares.cse.Buffalo.EDU [128.205.32.79]) by castor.cse.Buffalo.EDU (8.13.6/8.12.10) with ESMTP id l1Q3BHPW023872 for ; Sun, 25 Feb 2007 22:11:17 -0500 (EST) Received: from front3.acsu.buffalo.edu (upfront.acsu.buffalo.edu [128.205.4.140]) by ares.cse.buffalo.edu (8.13.6/8.13.6) with SMTP id l1Q3B8Xm064172 for ; Sun, 25 Feb 2007 22:11:08 -0500 (EST) Received: (qmail 21967 invoked from network); 26 Feb 2007 03:11:08 -0000 Received: from mailscan7.acsu.buffalo.edu (128.205.6.158) by front3.acsu.buffalo.edu with SMTP; 26 Feb 2007 03:11:08 -0000 Received: (qmail 25465 invoked from network); 26 Feb 2007 03:11:07 -0000 Received: from deliverance.acsu.buffalo.edu (128.205.7.57) by front2.acsu.buffalo.edu with SMTP; 26 Feb 2007 03:11:07 -0000 Received: (qmail 1788 invoked from network); 26 Feb 2007 03:10:58 -0000 Received: from listserv.buffalo.edu (128.205.7.35) by deliverance.acsu.buffalo.edu with SMTP; 26 Feb 2007 03:10:58 -0000 Received: by LISTSERV.BUFFALO.EDU (LISTSERV-TCP/IP release 14.5) with spool id 3553150 for CSE584-SP07-LIST@LISTSERV.BUFFALO.EDU; Sun, 25 Feb 2007 22:10:58 -0500 Delivered-To: CSE584-SP07-LIST@LISTSERV.BUFFALO.EDU Received: (qmail 5370 invoked from network); 26 Feb 2007 03:10:46 -0000 Received: from mailscan8.acsu.buffalo.edu (128.205.7.55) by listserv.buffalo.edu with SMTP; 26 Feb 2007 03:10:46 -0000 Received: (qmail 12989 invoked from network); 26 Feb 2007 03:10:45 -0000 Received: from castor.cse.buffalo.edu (128.205.32.14) by smtp1.acsu.buffalo.edu with SMTP; 26 Feb 2007 03:10:45 -0000 Received: from castor.cse.Buffalo.EDU (rapaport@localhost [127.0.0.1]) by castor.cse.Buffalo.EDU (8.13.6/8.12.10) with ESMTP id l1Q3AiCo023854 for ; Sun, 25 Feb 2007 22:10:44 -0500 (EST) Received: (from rapaport@localhost) by castor.cse.Buffalo.EDU (8.13.6/8.12.9/Submit) id l1Q3Aisv023853 for CSE584-SP07-LIST@LISTSERV.BUFFALO.EDU; Sun, 25 Feb 2007 22:10:44 -0500 (EST) X-UB-Relay: (castor.cse.buffalo.edu) X-PM-EL-Spam-Prob: : 7% Message-ID: <200702260310.l1Q3Aisv023853@castor.cse.Buffalo.EDU> Date: Sun, 25 Feb 2007 22:10:44 -0500 Reply-To: "William J. Rapaport" Sender: "Philosophy of Computer Science, Spring 2007" From: "William J. Rapaport" Subject: Re: TM encoding schemes and a loss of generality To: CSE584-SP07-LIST@LISTSERV.BUFFALO.EDU Precedence: list List-Help: , List-Unsubscribe: List-Subscribe: List-Owner: List-Archive: X-UB-Relay: (castor.cse.buffalo.edu) X-DCC-Buffalo.EDU-Metrics: castor.cse.Buffalo.EDU 1335; Body=0 Fuz1=0 Fuz2=0 X-Spam-Status: No, score=-2.5 required=5.0 tests=AWL,BAYES_00 autolearn=unavailable version=3.1.7 X-Spam-Checker-Version: SpamAssassin 3.1.7 (2006-10-05) on ares.cse.buffalo.edu X-Virus-Scanned: ClamAV 0.88.6/2653/Sun Feb 25 16:24:16 2007 on ares.cse.buffalo.edu X-Virus-Status: Clean Status: R Content-Length: 722 ------------------------------------------------------------------------ Subject: Re: TM encoding schemes and a loss of generality ------------------------------------------------------------------------ Albert wrote: | | I think there is at least one sense in which the universal turning | machine (UTM) is "hard-wired" and not general. I think Albert meant "Turing" machine. Otherwise, he would seem to be talking about a very strange sort of lathe :-) More seriously, The point is that a UTM is "general-purpose" or "universal" in the sense that it can compute what any other TM can compute, as long as that TM is encoded in the UTM's "language". There are different UTMs. But they all have the same "power".