[ 2 posts ] 
 Exercise [16.18] 
Author Message

Joined: 22 Apr 2010, 15:52
Posts: 43
Location: Olpe, Germany
Post Exercise [16.18]
Here my suggestion for a solution (needs discussion/verification):
Exercise_16_18.pdf [21.87 KiB]
Downloaded 202 times

03 Sep 2010, 17:22

Joined: 12 Jul 2010, 07:44
Posts: 154
Post Re: Exercise [16.18]
JBeckmann, you might want to clarify the exact relationship between PI1-sentences and the halting of Turing machine computations Tw(w) in your solution - i.e. How is the sentence "Tw(w) does not terminate" a PI1-sentence?

You might also want to point out that P can simply be constructed as the Turing machine that recursively enumerates all statements provable using F, and checks each one in turn to see if it matches the statement "Tw(w) does not terminate"; it halts (and returns 1) only if/when a match is found. Given a P defined like that, your footnotes 1 and 2 become irrelevant.


Apart from the above omissions, JBeckmann's solution is correct. However, he does not show how it follows from the argument given in the book, which is what the question is asking. My much longer solution (attached below) shows exactly how you could start from the argument in the book and end up with (essentially) JBeckmann's version of the proof. As an addendum, I also show how this is done much more directly if you start with a Turing/Cantor argument that's a little different from the one given in the text, suggesting that Penrose got mixed up and actually had this other argument in mind when he refers to "Turing's argument above" on p377, and probably also when he states on p376 that "A little consideration tells us that what we have learnt is that there is no general algorithm for telling us when a Turing machine action Tt(n) will fail to stop" ...since it actually takes more than "a little consideration" to draw that conclusion from the Turing/Cantor argument given on that page!

My solution:

File comment: MS Word 2010 version (original)
Exercise [16.18].docx [55.87 KiB]
Downloaded 103 times
File comment: PDF version
Exercise [16.18].pdf [220.05 KiB]
Downloaded 139 times
03 Jun 2011, 00:30
   [ 2 posts ]