Re: [PO] halting problem reading comprehension

From: Mitch Harris (harrisq_at_tcs.inf.tu-dresden.de)
Date: 09/01/04 

Date: Wed, 01 Sep 2004 10:04:13 +0200

Peter Olcott wrote:
> "Mitch Harris" <harrisq@tcs.inf.tu-dresden.de> wrote in message news:2piqurFl9je6U1@uni-berlin.de...
>>Peter Olcott wrote:
>
>>Now my counterclaim using your standards. Diag is the TM
>>that yours cannot possibly correctly process (for those who
>>have a logical bent, my argument is of course specious
>>because Diag is a hypothetical construction based on the
>>hypothetical existence of a TM for Halt).
>>Here are my reasons:
>>
>>1) if your Halt doesn't output its answer in a usable form,
>>then it is not correct.
>
> Not quite. This is not wrong, it just needs some qualification.
> As long as it can output the answer for every input in a
> usable form, then it is correct.

That didn't sound any different to me. Can you qualify some
more?

>>2) The construction of Diag is perfectly allowable (all you
>>attempts at "detecting" self reference are irrelevant).
>
> That remains to be seen. If it means that I can't achieve
> 1) then you are correct, if it does not mean that I can not
> achieve 1), then you are incorrect.

Lots of negatives in there. What does it mean for you to
achieve a conditional? That just doesn't make sense.

Do you mean if you can achieve the property of preventing
Halt's output from being used? You can't prevent that,
because, if you did, it wouldn't be a correct Halt analyzer.

> Diag() must be converted
> to a TM that my TM can not possibly process correctly for
> this to be shown.

No need for the conversion. It already is a TM such that
your or any TM, that purportedly computes Halt, cannot
correctly compute its halting status. 

-- 
Mitch Harris
(remove q to reply)

Relevant Pages

  • Re: [PO] halting problem reading comprehension
    ... Diag is the TM ... >>that yours cannot possibly correctly process (for those who ... >>hypothetical existence of a TM for Halt). ... it just needs some qualification. ...
    (comp.theory)
  • Re: [PO] halting problem reading comprehension
    ... What if your standard doesn't actually do that? ... > an input that my method can not correctly process. ... allow Diag to call itself (since Halt is really an arbitrary ... it is Diag callling diag that is ...
    (sci.logic)
  • Re: [PO] halting problem reading comprehension
    ... What if your standard doesn't actually do that? ... > an input that my method can not correctly process. ... allow Diag to call itself (since Halt is really an arbitrary ... it is Diag callling diag that is ...
    (comp.theory)
  • Re: [PO] Re: Attempt to Refute the Halting Problems Refutation
    ... > do halt on their own code, but which don't produce the result 0, aren't ... > because we defined D to halt no matter what input it's given. ... diag cannot be computed by any computer program. ...
    (sci.logic)
  • Re: [PO] halting problem reading comprehension
    ... > that yours cannot possibly correctly process (for those who ... > because Diag is a hypothetical construction based on the ... > hypothetical existence of a TM for Halt). ... > 1) if your Halt doesn't output its answer in a usable form, ...
    (comp.theory)