Path: ...!weretis.net!feeder9.news.weretis.net!news.quux.org!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!eternal-september.org!.POSTED!not-for-mail From: dbush Newsgroups: comp.theory Subject: Re: DDD simulated by HHH cannot possibly halt (Halting Problem) Date: Thu, 10 Apr 2025 19:27:23 -0400 Organization: A noiseless patient Spider Lines: 101 Message-ID: References: MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit Injection-Date: Fri, 11 Apr 2025 01:27:23 +0200 (CEST) Injection-Info: dont-email.me; posting-host="051148395ecf80642a827d679b03fa46"; logging-data="62908"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX19qIHalE/QXGtpakGal7rqw" User-Agent: Mozilla Thunderbird Cancel-Lock: sha1:JtRJLjUjRQGEazI4Z2ZECSMOyWQ= In-Reply-To: Content-Language: en-US Bytes: 5713 On 4/10/2025 7:26 PM, olcott wrote: > On 4/10/2025 3:55 AM, Fred. Zwarts wrote: >> Op 10.apr.2025 om 03:47 schreef olcott: >>> On 4/9/2025 3:56 PM, dbush wrote: >>>> On 4/9/2025 4:35 PM, olcott wrote: >>>>> On 4/9/2025 1:58 PM, Fred. Zwarts wrote: >>>>>> Op 09.apr.2025 om 19:29 schreef olcott: >>>>>>> >>>>>>> On 4/8/2025 10:31 AM, Fred. Zwarts wrote: >>>>>>>> Op 08.apr.2025 om 17:13 schreef olcott: >>>>>>>>> On 4/8/2025 2:45 AM, Fred. Zwarts wrote: >>>>>>>>>> Op 08.apr.2025 om 06:33 schreef olcott: >>>>>>>>>>> >>>>>>>>>>> typedef void (*ptr)(); >>>>>>>>>>> int HHH(ptr P); >>>>>>>>>>> >>>>>>>>>>> int DD() >>>>>>>>>>> { >>>>>>>>>>>    int Halt_Status = HHH(DD); >>>>>>>>>>>    if (Halt_Status) >>>>>>>>>>>      HERE: goto HERE; >>>>>>>>>>>    return Halt_Status; >>>>>>>>>>> } >>>>>>>>>>> >>>>>>>>>>> int main() >>>>>>>>>>> { >>>>>>>>>>>    HHH(DD); >>>>>>>>>>> } >>>>>>>>>>> >>>>>>>>>>> *Simulating termination analyzer Principle* >>>>>>>>>>> It is always correct for any simulating termination >>>>>>>>>>> analyzer to stop simulating and reject any input that >>>>>>>>>>> would otherwise prevent its own termination. >>>>>>>>>> >>>>>>>>>> >>>>>>>>>> In this case there is nothing to prevent, because the finite >>>>>>>>>> string specifies a program that halts. >>>>>>>>> >>>>>>>>> int DD() >>>>>>>>> { >>>>>>>>>    int Halt_Status = HHH(DD); >>>>>>>>>    if (Halt_Status) >>>>>>>>>      HERE: goto HERE; >>>>>>>>>    return Halt_Status; >>>>>>>>> } >>>>>>>>> >>>>>>>>> This stuff is simply over-your-head. >>>>>>>>> HHH(DD) meets the above: *Simulating termination analyzer >>>>>>>>> Principle* >>>>>>>>> Anyone with sufficient competence with the C programming language >>>>>>>>> will understand this. >>>>>>>>> >>>>>>>> Everyone with a little bit of C knowledge understands that if >>>>>>>> HHH returns with a value 0, then DDD halts. >>>>>>> >>>>>>> DDD CORRECTLY SIMULATED BY HHH >>>>>>> NOT ANY OTHER DAMN DDD IN THE UNIVERSE NITWIT. >>>>>>> >>>>>> If HHH would correctly simulate DD (and the functions called by >>>>>> DD) then the simulated HHH would return to DD and DD would halt. >>>>> >>>>> Simply over your level of technical competence. >>>>> >>>>>> But HHH failed to complete the simulation of the halting program, >>>>> >>>>> HHH is only required to report on the behavior of its >>>>> own correct simulation (meaning the according to the >>>>> semantics of the C programming language) and would be >>>>> incorrect to report on any other behavior. >>>> >>>> Which means HHH has conflicting requirements, >>> >>> No, it just means that the ones that you have >>> been saying are f-cked up and no-one noticed this before. >>> >>>  > because to perform a >>>  > correct simulation of its input it cannot halt itself, and therefore >>>  > can't report that. >>> In other words you simply "don't believe in" the variant >>> form of mathematical induction that HHH uses. >>> >>> A proof by induction consists of two cases. The first, the base case, >>> proves the statement for 𝑛=0 without assuming any knowledge of other >>> cases. The second case, the induction step, proves that if the >>> statement holds for any given case 𝑛=k, then it must also hold for >>> the next case 𝑛=k+1. These two steps establish that the statement >>> holds for every natural number 𝑛. The base case does not necessarily >>> begin with 𝑛=0, but often with 𝑛=1, and possibly with any fixed >>> natural number 𝑛=𝒩, establishing the truth of the statement for all >>> natural numbers 𝑛 ≥ 𝒩.   https://en.wikipedia.org/wiki/ >>> Mathematical_induction >>> >> So the proof by induction shows that for any n HHH fails to complete >> the simulation. So, it has been proven that no HHH exists that is able >> to simulate correctly. It always aborts before it sees that the >> simulated HHH aborts as well. > > Yet again over-your-head. > Unless the first HHH aborts Changing the input is not allowed.