Path: news.eternal-september.org!eternal-september.org!.POSTED!not-for-mail From: Mikko Newsgroups: comp.theory Subject: Re: DDD simulated by HHH cannot possibly halt (Halting Problem) Date: Mon, 14 Apr 2025 11:28:18 +0300 Organization: - Lines: 121 Message-ID: References: MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8; format=flowed Content-Transfer-Encoding: 8bit Injection-Date: Mon, 14 Apr 2025 10:28:19 +0200 (CEST) Injection-Info: dont-email.me; posting-host="392555565981b926339f9f53b30a6ad2"; logging-data="925674"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX19jf1MIrC7s+XGscUDctVMK" User-Agent: Unison/2.2 Cancel-Lock: sha1:1UPMK4tGAHLwf/F9IyKsMBg+3aA= On 2025-04-13 19:34:49 +0000, olcott said: > On 4/10/2025 6:27 PM, dbush wrote: >> 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. > > int DD() > { > int Halt_Status = HHH(DD); > if (Halt_Status) > HERE: goto HERE; > return Halt_Status; > } > > int main() > { > HHH(DD); > } That is changing the input. The subject line specifies DDD. -- Mikko