Path: ...!weretis.net!feeder8.news.weretis.net!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail From: olcott 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: References: 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: 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 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 ==========