Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]


Groups > comp.software-eng > #1602

Re: A non-halting decider is defined [ 2020-11-11 version ]

Subject Re: A non-halting decider is defined [ 2020-11-11 version ]
Newsgroups comp.theory, comp.ai.philosophy, comp.software-eng
References (2 earlier) <tKednXr4xevQtDHCnZ2dnUU78T3NnZ2d@brightview.co.uk> <1904ff20-b029-4ca6-89b9-615f5984e00do@googlegroups.com> <4RXqH.261071$d95.207052@fx06.iad> <81b63906-3740-4840-abe3-acfbec62209do@googlegroups.com> <3eKdnTKBs4GCwjHCnZ2dnUU78N-dnZ2d@brightview.co.uk>
From olcott <NoOne@NoWhere.com>
Date 2020-11-11 17:48 -0600
Message-ID <0cSdnZbejdHT5THCnZ2dnUU7-InNnZ2d@giganews.com> (permalink)

Cross-posted to 3 groups.

Show all headers | View raw


On 11/11/2020 4:01 PM, Mike Terry wrote:
> On 11/11/2020 21:00, David Kleinecke wrote:
>> On Wednesday, November 11, 2020 at 12:29:55 PM UTC-8, Richard Damon 
>> wrote:
>>> On 11/11/20 1:59 PM, David Kleinecke wrote:
>>>> On Wednesday, November 11, 2020 at 10:11:29 AM UTC-8, Mike Terry wrote:
>>>>> On 11/11/2020 17:06, olcott wrote:
>>>>>
>>>>> <.. snip content already addressed many times in other posts ..>>
>>>>>
>>>>>  > NEW MATERIAL ADDED HERE
>>>>>
>>>>> <.. snip content already addressed many times in other posts ..>>
>>>>>
>>>>>
>>>>> Please stop spamming this newsgroup.
>>>>>
>>>>> Mike.
>>>>
>>>> I have been following this argument for the laughs. But they
>>>> have been few and far between.
>>>>
>>>> One thing I don't understand: Linz defines H as any halt
>>>> decider - what gives anyone the right to write code for
>>>> it?
>>>>
>>>
>>> One way to disprove a non-existance proof is to provide an example of an
>>> instance. Linz put forward that no halt decider can correctly decide his
>>> H_Hat, which is built based on the halt decider being tested.
>>>
>>> If you COULD create a specific halt decider that did correctly predict
>>> what H_Hat would do, that would be a proof that Linz was wrong, and that
>>> there must be something incorrect in his argument (though, because
>>> Linz's argument is so basic, it likely means there is an error in your
>>> decider).
>>>
>>> This is the case, apparently with PO's 'proof'. He has tried changing
>>> the wording of the definition a bit to something that sounds close
>>> enough that it  might be good enough, bue then doesn't even match his
>>> modified definition.
>>>
>>> The problem is that he as taken a rule for detecting some types of
>>> non-halting behavior as being true axiomatically when it is NOT true,
>>> and throws up all sorts of smoke and mirrors to try to defend it, to the
>>> point of believing his rule more than actual observations.
>>>
>>> Yes, there is likely some very modified versions of the halting problem
>>> that his proof could be used to show that Linz's proof doesn't apply to
>>> that modified problem, but these are cases where we likely already know
>>> that Linz doesn't apply (Linz only applies to UNIVERSAL halt detectors,
>>> a halt detector that claims to be able to handle ANY Turing Machine). It
>>> also turns out that those modified versions are also likely not very
>>> interesting to actually want such a partial halt decider.
>>
>> OK - I think I grasp that.
>>
>> But all that is required is to provide the code for a universal
>> halt detector in any old language. For a while now what proports
>> to be the code of such a detector has been posted and copied. It
>> is a joke - a wrapper around two programs that apparently someone
>> thinks do the work of a universal halt detector.
>>
> 
> PO is not claiming to have a /universal/ halt detector.
> 
> Linz's proof goes along these lines:
> 1)  Suppose H is a universal halt decider
> 2)  Construct from H this new program H^. [Details in Linz proof,
>      but crucially, /every/ H has its own corresponding H^.]
> 3)  Then we show that due to the way H^ was constructed from H,
>      H incorrectly decides halting for the input pair (H^, H^).
>      [..contradicting (1)]
> 
> PO's argument was (is?) that he had his own H and an H^, where H^ is 
> correctly derived from H according to Linz specifications, and yet his H 
> /correctly/ decides the halting status of input (H^,H^).  /If/ that were 
> possible, it would indicate faulty logic in the Linz proof, although PO 
> has never been able to indicate which part of the proof reasoning is 
> faulty.

You mean that I have NEVER indicated this more than fifty times:

The new criterion measure can not be fooled by an input that does the 
opposite of whatever the halt decider decides.

   Now we construct a new Turing machine D with H as a
   subroutine. This new TM calls H to determine what M
   does when the input to M is its own description <M>.
   Once D has determined this information, it does the
   opposite. That is, it rejects if M accepts and accepts
   if M does not accept. The following is a description of D.
   http://www.liarparadox.org/sipser_165.pdf

Sipser, Michael 1997. Introduction to the Theory of Computation. Boston: 
PWS Publishing Company (165-167)

When we change the criterion measure from:
(a) Does machine M halt on its input w?

To this new criterion measure:
(b) Does the simulation of the input M on input w have to be forced to 
stop to prevent its infinite execution?

Then an input that does the opposite of whatever the halt decider 
decides has no effect what-so-ever on this decision because the input 
was forced to stop before it could have any effect on this decision.


> So... his H is not meant (or required) to be a /universal/ halt decider, 
> just a halt decider for its "nemesis" input (H^,H^).  He is trying to 
> show that the /reasoning/ of the Linz proof must be faulty, because that 
> reasoning gives a faulty conclusion in the one case of his H, H^ programs.
> 
> Of course, it does not, and PO has actually admitted that for his 
> specific H,H^  :
> a) H^(H^) halts,
> b) H(H^,H^) decides "never halts".
> [I.e. exactly in line with Linz proof]

> He thinks he has invented his own (rather bizarre) new decider condition 
> (let's call that PO-decision), with corresponding class of inputs C_PO 
> which are the inputs (P,I) which satisfy his PO-decision.

The new criterion measure still divides inputs into halting and 
not-halting thus still directly relevant to the halting problem.

> Indeed, it's the case that for his code:
> a) (H^,H^) is not in C_PO,
> b) H(H^,H^) decides "not in C_PO".
> 
> I think he wants to claim this contradicts Linz, but of course, Linz 
> says nothing whatsoever about C_PO or PO-condition, /even if PO could 
> rigorously define the class/, which he's quite incapable of.  And there 
> are many much less contorted conditions than PO-condition which /can/ be 
> decided correctly, so it's all just hot air.  Not that PO can understand 
> that...
> 
> Mike.
> 


-- 
Copyright 2020 Pete Olcott

"Great spirits have always encountered violent opposition from mediocre 
minds." Einstein

Back to comp.software-eng | Previous | Next — Next in thread | Find similar | Unroll thread


Thread

Re: A non-halting decider is defined [ 2020-11-11 version ] olcott <NoOne@NoWhere.com> - 2020-11-11 17:48 -0600
  Re: A non-halting decider is defined [ 2020-11-11 version ] Jeff Barnett <jbb@notatt.com> - 2020-11-11 17:33 -0700

csiph-web