 Page 1 of 1 [ 2 posts ]
 Print view Previous topic | Next topic
Exercise [16.17]
Author Message

Joined: 22 Apr 2010, 15:52
Posts: 43
Location: Olpe, Germany
My solution:
Attachment: Exercise_16_17.pdf [26.13 KiB]

29 Aug 2010, 13:00 Joined: 12 Jul 2010, 07:44
Posts: 154
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 proof-by-contradiction given earlier.

15 May 2011, 09:15 Page 1 of 1 [ 2 posts ]