Path: ...!weretis.net!feeder8.news.weretis.net!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: olcott <polcott2@gmail.com>
Newsgroups: comp.theory,sci.logic
Subject: Re: Can an abort decider be defined that cannot be fooled by any
 pathological input?
Date: Wed, 27 Mar 2024 22:58:53 -0500
Organization: A noiseless patient Spider
Lines: 638
Message-ID: <uu2ptu$37bas$13@dont-email.me>
References: <utoboa$5f03$1@dont-email.me> <utopik$89n1$1@dont-email.me>
 <uts4hn$15g1s$2@dont-email.me> <uts6bp$15q0v$1@dont-email.me>
 <uts79p$164d3$2@dont-email.me> <uts819$1682g$1@dont-email.me>
 <utschj$17h7c$1@dont-email.me> <utt2f8$32apl$1@i2pn2.org>
 <utt3qt$1cuoq$1@dont-email.me> <utt4h2$32apl$3@i2pn2.org>
 <utt5bv$1d2ks$2@dont-email.me> <utt5v2$32apk$11@i2pn2.org>
 <utt7e1$1dpmh$1@dont-email.me> <utt8fg$32apl$6@i2pn2.org>
 <utt8oq$1dv6f$2@dont-email.me> <uttank$32apk$12@i2pn2.org>
 <uttdbr$1evji$1@dont-email.me> <uttdpd$32apk$14@i2pn2.org>
 <uttfeo$1j1tv$1@dont-email.me> <utucdh$33t24$1@i2pn2.org>
 <utups3$1t1bi$1@dont-email.me> <utvvl1$35q21$6@i2pn2.org>
 <uu02ni$2jvdi$1@dont-email.me> <uu2ep7$374vo$6@i2pn2.org>
 <uu2jd6$36okm$1@dont-email.me> <uu2kvb$374vn$4@i2pn2.org>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Thu, 28 Mar 2024 03:58:55 +0100 (CET)
Injection-Info: dont-email.me; posting-host="481a4c8f2cd1b5f60f5d8b2395b87ce0";
	logging-data="3386716"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1+j4vBB/h5KUEMqoL0pOMv7"
User-Agent: Mozilla Thunderbird
Cancel-Lock: sha1:yljRzsvP2C7xWFZVu8khKEYaJJQ=
In-Reply-To: <uu2kvb$374vn$4@i2pn2.org>
Content-Language: en-US
Bytes: 28432

On 3/27/2024 9:34 PM, Richard Damon wrote:
> On 3/27/24 10:07 PM, olcott wrote:
>> On 3/27/2024 7:48 PM, Richard Damon wrote:
>>> On 3/26/24 11:10 PM, olcott wrote:
>>>> On 3/26/2024 9:18 PM, Richard Damon wrote:
>>>>> On 3/26/24 11:33 AM, olcott wrote:
>>>>>> On 3/26/2024 6:43 AM, Richard Damon wrote:
>>>>>>> On 3/25/24 11:29 PM, olcott wrote:
>>>>>>>> On 3/25/2024 10:01 PM, Richard Damon wrote:
>>>>>>>>> On 3/25/24 10:53 PM, olcott wrote:
>>>>>>>>>> On 3/25/2024 9:08 PM, Richard Damon wrote:
>>>>>>>>>>> On 3/25/24 9:35 PM, olcott wrote:
>>>>>>>>>>>> On 3/25/2024 8:30 PM, Richard Damon wrote:
>>>>>>>>>>>>> On 3/25/24 9:12 PM, olcott wrote:
>>>>>>>>>>>>>> On 3/25/2024 7:47 PM, Richard Damon wrote:
>>>>>>>>>>>>>>> On 3/25/24 8:37 PM, olcott wrote:
>>>>>>>>>>>>>>>> On 3/25/2024 7:22 PM, Richard Damon wrote:
>>>>>>>>>>>>>>>>> On 3/25/24 8:11 PM, olcott wrote:
>>>>>>>>>>>>>>>>>> On 3/25/2024 6:47 PM, Richard Damon wrote:
>>>>>>>>>>>>>>>>>>> On 3/25/24 1:33 PM, olcott wrote:
>>>>>>>>>>>>>>>>>>>> On 3/25/2024 11:16 AM, Fred. Zwarts wrote:
>>>>>>>>>>>>>>>>>>>>> Op 25.mrt.2024 om 17:04 schreef olcott:
>>>>>>>>>>>>>>>>>>>>>> On 3/25/2024 10:48 AM, Fred. Zwarts wrote:
>>>>>>>>>>>>>>>>>>>>>>> Op 25.mrt.2024 om 16:17 schreef olcott:
>>>>>>>>>>>>>>>>>>>>>>>> On 3/24/2024 3:51 AM, Fred. Zwarts wrote:
>>>>>>>>>>>>>>>>>>>>>>>>> Op 24.mrt.2024 om 05:55 schreef olcott:
>>>>>>>>>>>>>>>>>>>>>>>>>> Can an abort decider be defined that cannot be 
>>>>>>>>>>>>>>>>>>>>>>>>>> fooled by any pathological input?
>>>>>>>>>>>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>>>>>>>>>>>> 01 int D(ptr x)  // ptr is pointer to int 
>>>>>>>>>>>>>>>>>>>>>>>>>> function
>>>>>>>>>>>>>>>>>>>>>>>>>> 02 {
>>>>>>>>>>>>>>>>>>>>>>>>>> 03   int Halt_Status = H(x, x);
>>>>>>>>>>>>>>>>>>>>>>>>>> 04   if (Halt_Status)
>>>>>>>>>>>>>>>>>>>>>>>>>> 05     HERE: goto HERE;
>>>>>>>>>>>>>>>>>>>>>>>>>> 06   return Halt_Status;
>>>>>>>>>>>>>>>>>>>>>>>>>> 07 }
>>>>>>>>>>>>>>>>>>>>>>>>>> 08
>>>>>>>>>>>>>>>>>>>>>>>>>> 09 void main()
>>>>>>>>>>>>>>>>>>>>>>>>>> 10 {
>>>>>>>>>>>>>>>>>>>>>>>>>> 11   H(D,D);
>>>>>>>>>>>>>>>>>>>>>>>>>> 12 }
>>>>>>>>>>>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>>>>>>>>>>>> Of all of the elements of the set of H(D,D) 
>>>>>>>>>>>>>>>>>>>>>>>>>> where H simulates its
>>>>>>>>>>>>>>>>>>>>>>>>>> input there are matched pairs of otherwise 
>>>>>>>>>>>>>>>>>>>>>>>>>> identical elements that
>>>>>>>>>>>>>>>>>>>>>>>>>> only differ by whether they abort their 
>>>>>>>>>>>>>>>>>>>>>>>>>> simulation or not.
>>>>>>>>>>>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>>>>>>>>>>>> The half of these that don't abort are 
>>>>>>>>>>>>>>>>>>>>>>>>>> incorrect because all deciders
>>>>>>>>>>>>>>>>>>>>>>>>>> must halt. This makes the other half correct 
>>>>>>>>>>>>>>>>>>>>>>>>>> about the abort/no abort
>>>>>>>>>>>>>>>>>>>>>>>>>> decision.
>>>>>>>>>>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>>>>>>>>>>> No. The other, aborting, half is just wrong, 
>>>>>>>>>>>>>>>>>>>>>>>>> because it aborts when it is not needed. So, 
>>>>>>>>>>>>>>>>>>>>>>>>> the half that aborts is wrong and it may be 
>>>>>>>>>>>>>>>>>>>>>>>>> argued that it is better to not abort something 
>>>>>>>>>>>>>>>>>>>>>>>>> that halts on its own and that 
>>>>>>>>>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>>>>>>>>>> At least two software engineers with masters 
>>>>>>>>>>>>>>>>>>>>>>>> degrees in computer science
>>>>>>>>>>>>>>>>>>>>>>>> disagree.
>>>>>>>>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>>>>>>>>> Two is not many, considering that with Google for 
>>>>>>>>>>>>>>>>>>>>>>> any invalid idea it is easy to find a several 
>>>>>>>>>>>>>>>>>>>>>>> people with a master degree supporting it.
>>>>>>>>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>>>>>>>>>> Exactly what are you software engineering skills?
>>>>>>>>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>>>>>>>>> I have been professionally programming since 1986 
>>>>>>>>>>>>>>>>>>>>>>> in several languages. (Non professionally I 
>>>>>>>>>>>>>>>>>>>>>>> started programming in 1975). Since about 1990 I 
>>>>>>>>>>>>>>>>>>>>>>> programmed in C and since about 2000 in C++.
>>>>>>>>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>>>>>>>>>> I have been a professional C++ software engineer 
>>>>>>>>>>>>>>>>>>>>>>>> since Y2K.
>>>>>>>>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>>>>>>>>> I'm sorry to hear that olcott has been so smart, 
>>>>>>>>>>>>>>>>>>>>>>> but now he does not even sees what even a 
>>>>>>>>>>>>>>>>>>>>>>> beginner sees.
>>>>>>>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>>>>>>>> Can D correctly simulated by H terminate normally?
>>>>>>>>>>>>>>>>>>>>>> 01 int D(ptr x)  // ptr is pointer to int function
>>>>>>>>>>>>>>>>>>>>>> 02 {
>>>>>>>>>>>>>>>>>>>>>> 03   int Halt_Status = H(x, x);
>>>>>>>>>>>>>>>>>>>>>> 04   if (Halt_Status)
>>>>>>>>>>>>>>>>>>>>>> 05     HERE: goto HERE;
>>>>>>>>>>>>>>>>>>>>>> 06   return Halt_Status;
>>>>>>>>>>>>>>>>>>>>>> 07 }
>>>>>>>>>>>>>>>>>>>>>> 08
>>>>>>>>>>>>>>>>>>>>>> 09 void main()
>>>>>>>>>>>>>>>>>>>>>> 10 {
>>>>>>>>>>>>>>>>>>>>>> 11   H(D,D);
>>>>>>>>>>>>>>>>>>>>>> 12 }
>>>>>>>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>>>>>>>> *Execution Trace*
>>>>>>>>>>>>>>>>>>>>>> Line 11: main() invokes H(D,D);
>>>>>>>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>>>>>>>> *keeps repeating* (unless aborted)
>>>>>>>>>>>>>>>>>>>>>> Line 03: simulated D(D) invokes simulated H(D,D) 
>>>>>>>>>>>>>>>>>>>>>> that simulates D(D)
>>>>>>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>>>>>>> Even a beginner sees that, if the H that aborts is 
>>>>>>>>>>>>>>>>>>>>> chosen, simulated H(D,D) aborts and returns false 
>>>>>>>>>>>>>>>>>>>>> (unless aborted). So simulated D halts (unless 
>>>>>>>>>>>>>>>>>>>>> aborted).
>>>>>>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>>>>>> I am estimating that you must be fibbing about your 
>>>>>>>>>>>>>>>>>>>> programming skill.
>>>>>>>>>>>>>>>>>>>> The D simulated by any implementation of H (that 
>>>>>>>>>>>>>>>>>>>> aborts or does not
>>>>>>>>>>>>>>>>>>>> abort its simulation) shown above cannot possibly 
>>>>>>>>>>>>>>>>>>>> reach its own line 04
>>>>>>>>>>>>>>>>>>>> also shown above.
>>>>>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>>>>> But that isn't the question.
>>>>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>>>> *That <is> the abort decision question*
>>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>>> But you agreed that a correct abort decider oly NEEDS 
>>>>>>>>>>>>>>>>> to abort its simulation if the correct simulation by a 
>>>>>>>>>>>>>>>>> pure correct simulator of the input given to H (which 
>>>>>>>>>>>>>>>>> doesn't change, so for this case, still calls that 
>>>>>>>>>>>>>>>>> original H) will never reach a final state.
>>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>>>>> The question is does that machine described by the 
>>>>>>>>>>>>>>>>>>> input Halt when run, or, alternatively, does its 
>>>>>>>>>>>>>>>>>>> correct simulation (not just by H) run forever (and 
>>>>>>>>>>>>>>>>>>> thus needs to be aborted)?
>>>>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>>>> Since you know that H(D,D) must abort its simulation 
>>>>>>>>>>>>>>>>>> to prevent its
>>>>>>>>>>>>>>>>>> own infinite execution I don't understand why you 
>>>>>>>>>>>>>>>>>> would lie about it.
>>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>>> But an H that doesn't abort and an H that does abort 
>>>>>>>>>>>>>>>>> are looking at different inputs "D", since you agree 
>>>>>>>>>>>>>>>>> that the behavior of D changes based on the H that it 
>>>>>>>>>>>>>>>>> is using.
>>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>> Not at all. Of the infinite set of every possible 
>>>>>>>>>>>>>>>> implementation of
>>>>>>>>>>>>>>>> H where H(D,D) simulates its input everyone that chose 
>>>>>>>>>>>>>>>> to abort is
>>>>>>>>>>>>>>>> necessarily correct.
>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>> I don't understand why you persist in lying about this.
>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>>>> I really want to get on to the next step and see if 
>>>>>>>>>>>>>>>>>> any input can
>>>>>>>>>>>>>>>>>> fool an abort decider into making the wrong abort 
>>>>>>>>>>>>>>>>>> decision.
>>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>>> But you need to get this step right first.
>>>>>>>>>>>>>>>>>
========== REMAINDER OF ARTICLE TRUNCATED ==========