From ag33@cse.Buffalo.EDU Mon Feb 26 12:21:32 2007 Received: from hadar.cse.Buffalo.EDU (root@hadar.cse.Buffalo.EDU [128.205.32.1]) by castor.cse.Buffalo.EDU (8.13.6/8.12.10) with ESMTP id l1QHLWQg019432 for ; Mon, 26 Feb 2007 12:21:32 -0500 (EST) Received: from pollux.cse.buffalo.edu (root@pollux.cse.Buffalo.EDU [128.205.35.2]) by hadar.cse.Buffalo.EDU (8.13.6/8.12.10) with ESMTP id l1QHLVxa008278 for ; Mon, 26 Feb 2007 12:21:31 -0500 (EST) Received: from pollux.cse.buffalo.edu (ag33@localhost [127.0.0.1]) by pollux.cse.buffalo.edu (8.12.10+Sun/8.12.9) with ESMTP id l1QHLVxX023735; Mon, 26 Feb 2007 12:21:31 -0500 (EST) Received: (from ag33@localhost) by pollux.cse.buffalo.edu (8.12.10+Sun/8.12.8/Submit) id l1QHLUJO023734; Mon, 26 Feb 2007 12:21:30 -0500 (EST) Date: Mon, 26 Feb 2007 12:21:30 -0500 (EST) From: Albert Goldfain To: "William J. Rapaport" cc: CSE584-SP07-LIST@LISTSERV.BUFFALO.EDU Subject: Re: HALTING PROBLEM In-Reply-To: <200702260022.l1Q0MtnW019715@castor.cse.Buffalo.EDU> Message-ID: References: <200702260022.l1Q0MtnW019715@castor.cse.Buffalo.EDU> MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII X-DCC-Buffalo.EDU-Metrics: castor.cse.Buffalo.EDU 1335; Body=0 Fuz1=0 Fuz2=0 Status: R Content-Length: 1387 > 3. Would it be possible to write a program for a TM that would allow > the TM to "understand" the proof that HP is undecidable? > > This is in part an empirical question and in part a matter > of what one means by "understand". I think it can be done, > and Albert is writing his dissertation on a closely related > topic. I'll let him elaborate. The word "understand" is both vague (not clear what it means) and ambiguous (used in many different ways in different texts). To help answer your question, consider what it would mean for *you* to understand that the proof that HP is undecidable. Consider the following: 1. Could you explain the proof to someone else? 2. Could you rephrase the proof in a way that didn't rely on the diagonalization argument? 3. Could you answer questions about the concepts involved in the proof? 4. Could you explain why the contradiction arrived at in the proof is a logical contradiction? 5. Could you explain what proofs by contradiction show in general? None of these five things *is* understanding, but any of them might be considered a *feature* of understanding. The more features you can address empirically, the more "understanding" we might say that you have. Now just replace "you" with "A UTM" and consider what might count as a UTM "explanation" "rephrasing" "question-answering" etc... (not an easy decision believe me :-))