The Road to Reality http://www.roadtoreality.info/ 

Exercise [16.17] http://www.roadtoreality.info/viewtopic.php?f=19&t=1657 
Page 1 of 1 
Author:  jbeckmann [ 29 Aug 2010, 13:00 ] 
Post subject:  Exercise [16.17] 
My solution: Attachment: 
Author:  deant [ 15 May 2011, 09:15 ] 
Post subject:  Re: Exercise [16.17] 
I think you can summarize the argument a little more simply than you've put it. Given the definitions in the problem hint (and also noting that (a) Q is recursive even if T is not, (b) T is not related to Tt in any way, and (c) that the "n" in "action of T applied to n..." is a constant, and is not the same as the variable "n" in the sentence beginning "Take the modulo 2 sum...", which probably should have been written "r", instead): Tt, Ts represent identical subsets of N <=> Tt(r)=Ts(r) for all r <=> Q(r)=0 for all r <=> Turing machine action T(n) does not halt within any finite time r Since we established earlier that we cannot in general know if an arbitrary Turing machine action T(n) is going to halt or not, we therefore cannot determine in general if Tt and Ts represent identical subsets. QED  Note that a more "intuitive" explanation of why we can't determine if two sets are identical is this: To check that Tt(r)=Ts(r) for ALL r and for arbitrary recursive Turing machines Tt and Ts, we are required to check equality for each r = 1, 2, 3, ... etc.; And since there's an infinite number of such checks to make, no Turing machine could ever do them all in finite time: So no effective Turing machine can decide whether any two such arbitrary recursive sets are identical or not, in all cases. The above paragraph does not constitute an actual proof; it's only a kind of plausibility argument, but it might help visualize where the problem lies, moreso than the rigorous proofbycontradiction given earlier. 
Page 1 of 1  Archived: 07 Aug 2014 
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group http://www.phpbb.com/ 