Re: computability not in undergrad?

From: The Ghost In The Machine (ewill_at_aurigae.athghost7038suus.net)
Date: 07/27/04 

Date: Tue, 27 Jul 2004 08:09:54 GMT

In sci.logic, Mitch Harris
<harrisq@tcs.inf.tu-dresden.de>
 wrote
on 26 Jul 2004 20:17:40 GMT
<2ml774Foj8a8U1@uni-berlin.de>:
> The Ghost In The Machine <ewill@aurigae.athghost7038suus.net> wrote:
>>In sci.logic, Mitch Harris <harrisq@tcs.inf.tu-dresden.de> wrote
>>> Peter Olcott wrote:
>>>>
>>>> But it does not even mention diagonalization. You
>>>> guys have for so long insisted that this is crucial.
>>>
>>> That doesn't sound right. I don't think anyone has said that
>>> the diagonalization method is necessary for the theorem to
>>> be correct.
>>
>>Diagonalization AFAICT is not required for the Halting Proof,
>>but the input argument does have to be modified to reset
>>the tape for the simulated machine in order to close the loop.
>
> I'm confused. What loop?

The loop in this case is metaphorical. It can be phrased thusly:

WillHalt is fed the encoding of LoopIfHalts which discards its
second parameter and copies its first parameter which happens
to be LoopIfHalts, then runs WillHalt, which is fed the encoding
of LoopIfHalts which discards its second parameter and copies its
first parameter which happens to be LoopIfHalts, then runs WillHalt,
which is fed the ...

Anyway, you get the idea, I hope. Basically, the alleged WillHalt
computes LoopIfHalt's behavior incorrectly on a certain input.

> What do you mean by input argument (the
> initial contents of the tape)?

Correct, if the universe in question consists of Turing machines.
For infinite-integer infinite-register scenarios, it might
consist of initial values of the registers.

>
>>This might be construed as a form thereof, as the input
>>to WillHalt is of the form (EncodedMachine, EncodedInput);
>>the input to LoopIfHalts is of the form EncodedInput(EncodedMachine),
>>which means WillHalt will ultimately have to be called with
>>EncodedMachine, EncodedInput(EncodedMachine)
>>discarding the second parameter.
>>
>>Or something like that. :-)
>>
>>>
>>>> You would accept a proof based on state transition
>>>> diagrams?
>>>
>>> Sure, whatever it takes. It sounds interesting.
>>
>>I'm not at all sure what this means,
>
> "whatever it takes" = it doesn't matter what proof method is used as
> long as it is sound.
>
> "It sounds interesting" = I can't imagine a proof that involves
> talking about the details of the TMs states (except one that is really
> mimicking the diagonlization proof!) so hearing that kind of proof
> might show me some new cool tricks I never knew before.
>
>> but I have outlined in one of my prior posts (I'd have to find it)
>>a method by which one can construct LoopIfHalts from WillHalt, where
>>both are Turing machines.
>>
>>It's actually not that difficult. :-)
>
> google groups link?

Must I? :-) I don't use Google. However, it's either in here
or in sci.math.

>
> Mitch 

-- 
#191, ewill3@earthlink.net
It's still legal to go .sigless.

Relevant Pages