Path: ...!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!eternal-september.org!.POSTED!not-for-mail
From: olcott <polcott333@gmail.com>
Newsgroups: comp.theory
Subject: Re: How do computations actually work?
Date: Wed, 28 May 2025 09:31:01 -0500
Organization: A noiseless patient Spider
Lines: 171
Message-ID: <10176n6$39etk$1@dont-email.me>
References: <Ms4XP.801347$BFJ.668081@fx13.ams4>
 <100l09v$2tae8$5@dont-email.me> <100l1ov$2ul3j$1@dont-email.me>
 <100l3jh$2v0e9$1@dont-email.me> <100l5c8$2ul3j$2@dont-email.me>
 <100l75g$2vpq3$1@dont-email.me> <100l887$2ul3i$2@dont-email.me>
 <100l9gh$30aak$1@dont-email.me> <100lc4o$30pgm$1@dont-email.me>
 <100ld1u$312c9$1@dont-email.me> <100lg4g$31jt3$1@dont-email.me>
 <100lkdv$32ib3$1@dont-email.me> <100lmif$32v06$1@dont-email.me>
 <100lmp3$32ven$1@dont-email.me> <100m319$38k55$2@dont-email.me>
 <87jz69xlpx.fsf@nosuchdomain.example.com> <100mder$39slu$2@dont-email.me>
 <100oipb$3oge1$1@dont-email.me> <100onkd$3t5cb$1@dont-email.me>
 <100p6vj$3vlgq$1@dont-email.me> <100q6b1$5buc$2@dont-email.me>
 <100rtvq$ji9l$1@dont-email.me> <100sod2$p071$6@dont-email.me>
 <100umo8$1a058$1@dont-email.me> <100vaoj$1d5lg$9@dont-email.me>
 <100ve0m$1e53o$1@dont-email.me> <10125hp$22da5$18@dont-email.me>
 <1013t5k$2hgid$1@dont-email.me> <1014mdi$2lsi8$8@dont-email.me>
 <1016ee6$352ij$1@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Wed, 28 May 2025 16:31:03 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="f5dbd82c61536f260449484ef7088f69";
	logging-data="3455924"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX19NiDopF7WcYne1/yTUDzBg"
User-Agent: Mozilla Thunderbird
Cancel-Lock: sha1:3fO7WnbZpshWIgG0CH0jsl5vIaI=
X-Antivirus: Norton (VPS 250528-2, 5/28/2025), Outbound message
In-Reply-To: <1016ee6$352ij$1@dont-email.me>
X-Antivirus-Status: Clean
Content-Language: en-US
Bytes: 8865

On 5/28/2025 2:36 AM, Mikko wrote:
> On 2025-05-27 15:40:33 +0000, olcott said:
> 
>> On 5/27/2025 3:29 AM, Mikko wrote:
>>> On 2025-05-26 16:40:25 +0000, olcott said:
>>>
>>>> On 5/25/2025 10:46 AM, Fred. Zwarts wrote:
>>>>> Op 25.mei.2025 om 16:50 schreef olcott:
>>>>>> On 5/25/2025 4:09 AM, Mikko wrote:
>>>>>>> On 2025-05-24 15:25:21 +0000, olcott said:
>>>>>>>
>>>>>>>> On 5/24/2025 2:54 AM, Mikko wrote:
>>>>>>>>> On 2025-05-23 16:04:49 +0000, olcott said:
>>>>>>>>>
>>>>>>>>>> On 5/23/2025 2:09 AM, Mikko wrote:
>>>>>>>>>>> On 2025-05-23 02:47:40 +0000, olcott said:
>>>>>>>>>>>
>>>>>>>>>>>> On 5/22/2025 8:24 PM, Mike Terry wrote:
>>>>>>>>>>>>> On 22/05/2025 06:41, Richard Heathfield wrote:
>>>>>>>>>>>>>> On 22/05/2025 06:23, Keith Thompson wrote:
>>>>>>>>>>>>>>> Richard Heathfield <rjh@cpax.org.uk> writes:
>>>>>>>>>>>>>>>> On 22/05/2025 00:14, olcott wrote:
>>>>>>>>>>>>>>>>> On 5/21/2025 6:11 PM, Richard Heathfield wrote:
>>>>>>>>>>>>>>> [...]
>>>>>>>>>>>>>>>>>> Turing proved that what you're asking is impossible.
>>>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>>> That is not what he proved.
>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>> Then you'll be able to write a universal termination 
>>>>>>>>>>>>>>>> analyser that can
>>>>>>>>>>>>>>>> correctly report for any program and any input whether 
>>>>>>>>>>>>>>>> it halts. Good
>>>>>>>>>>>>>>>> luck with that.
>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>> Not necessarily.
>>>>>>>>>>>>>>
>>>>>>>>>>>>>> Of course not. But I'm just reflecting. He seemed to think 
>>>>>>>>>>>>>> that my inability to write the kind of program Turing 
>>>>>>>>>>>>>> envisaged (an inability that I readily concede) is 
>>>>>>>>>>>>>> evidence for his argument. Well, what's sauce for the 
>>>>>>>>>>>>>> goose is sauce for the gander.
>>>>>>>>>>>>>>
>>>>>>>>>>>>>>> Even if olcott had refuted the proofs of the
>>>>>>>>>>>>>>> insolvability of the Halting Problem -- or even if he had 
>>>>>>>>>>>>>>> proved
>>>>>>>>>>>>>>> that a universal halt decider is possible
>>>>>>>>>>>>>>
>>>>>>>>>>>>>> And we both know what we both think of that idea.
>>>>>>>>>>>>>>
>>>>>>>>>>>>>>> -- that doesn't imply
>>>>>>>>>>>>>>> that he or anyone else would be able to write one.
>>>>>>>>>>>>>>
>>>>>>>>>>>>>> Indeed.
>>>>>>>>>>>>>>
>>>>>>>>>>>>>>> I've never been entirely clear on what olcott is claiming.
>>>>>>>>>>>>>>
>>>>>>>>>>>>>> Nor I. Mike Terry seems to have a pretty good handle on 
>>>>>>>>>>>>>> it, but no matter how clearly he explains it to me my eyes 
>>>>>>>>>>>>>> glaze over and I start to snore.
>>>>>>>>>>>>>
>>>>>>>>>>>>> Hey, it's the way I tell 'em!
>>>>>>>>>>>>>
>>>>>>>>>>>>> Here's what the tabloids might have said about it, if it 
>>>>>>>>>>>>> had made the front pages when the story broke:
>>>>>>>>>>>>>
>>>>>>>>>>>>>   COMPUTER BOFFIN IS TURING IN HIS GRAVE!
>>>>>>>>>>>>>
>>>>>>>>>>>>>   An Internet crank claims to have refuted Linz HP proof by 
>>>>>>>>>>>>> creating a
>>>>>>>>>>>>>   Halt Decider that CORRECTLY decides its own "impossible 
>>>>>>>>>>>>> input"!
>>>>>>>>>>>>>   The computing world is underwhelmed.
>>>>>>>>>>>>>
>>>>>>>>>>>>> Better?  (Appologies for the headline, it's the best I 
>>>>>>>>>>>>> could come up with.)
>>>>>>>>>>>>>
>>>>>>>>>>>>> Mike.
>>>>>>>>>>>>>
>>>>>>>>>>>>
>>>>>>>>>>>> There is a key detail about ALL of these proofs
>>>>>>>>>>>> that no one has paid attention to for 90 years.
>>>>>>>>>>>>
>>>>>>>>>>>> It is impossible to define *AN INPUT* to HHH that
>>>>>>>>>>>> does the opposite of whatever value that HHH returns.
>>>>>>>>>>>
>>>>>>>>>>> That is a key detail about HHH. Your HHH is not a part of 
>>>>>>>>>>> those proofs.
>>>>>>>>>>
>>>>>>>>>> All of the proofs work this same way.
>>>>>>>>>
>>>>>>>>> No, they don't. Some proofs derive the same conclusion with an 
>>>>>>>>> essentially
>>>>>>>>> different approach.
>>>>>>>>>
>>>>>>>>> However, in spite of the differences, they do share a common 
>>>>>>>>> fieature:
>>>>>>>>> your HHH is not a part of any of the proofs.
>>>>>>>>
>>>>>>>> All of the conventional proofs of the HP assume that
>>>>>>>> there is an *input D* that can actually do the opposite
>>>>>>>> of whatever value that HHH returns.
>>>>>>>
>>>>>>> Depends on what you mean by "conventional". If you merely mean 
>>>>>>> proofs
>>>>>>> that apply ordinary logic then there are proofs with a different
>>>>>>> strategy. If you mean only proofs that use the same strategy that
>>>>>>> Turing used then you are closer to the truth. But there is no 
>>>>>>> assumption
>>>>>>> about the exstence of such D. Its existence is proven.
>>>>>>>
>>>>>>
>>>>>> In seems that way until you pay much closer attention.
>>>>>>
>>>>>> int main()
>>>>>> {
>>>>>>    DDD(); // The HHH that DDD calls cannot report on the
>>>>>> }        // behavior of its caller because it cannot see
>>>>>>           // is caller.
>>>>>>
>>>>>> Even if HHH could see and report on the behavior of
>>>>>> its caller because its caller is not its input this
>>>>>> too is no good.
>>>>>
>>>>> It seems that way to you, until you pay somewhat closer attention.
>>>>
>>>> The HHH(DDD) must report on the behavior that its actual input
>>>> actually specified CANNOT BE VIOLATED.
>>>
>>> Of course it can. In fact HHH does violate that. DDD specifies a halting
>>> behaviour but HHH reports that DDD specifies a non-halting behaviour.
>>> That is a violation of that rquirement.
>>
>> If DDD simulated by HHH stops running for any
>> reason besides reaching its own "ret" instruction
>> final halt state THEN DDD HAS NOT HALTED.
> 
> Irrelevant. The requirement is that a halt decider predicts whether the
> complete execution of the computation described by the input will halt.
> 

Halting is defined as reaching a final state and
terminating normally.

int main()
{
   DDD(); // The HHH that DDD calls cannot
}        // see the behavior of its caller

*That is incorrect*
A termination analyzer must report on the basis
of the behavior that its input specifies and does
not give a rat's ass about the behavior of its caller.

_DDD()
[00002192] 55             push ebp
[00002193] 8bec           mov ebp,esp
[00002195] 6892210000     push 00002192
[0000219a] e833f4ffff     call 000015d2  // call HHH
[0000219f] 83c404         add esp,+04
[000021a2] 5d             pop ebp
[000021a3] c3             ret
Size in bytes:(0018) [000021a3]
========== REMAINDER OF ARTICLE TRUNCATED ==========