Path: ...!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: DD simulated by HHH cannot possibly halt (Halting Problem) Date: Mon, 14 Apr 2025 07:53:55 -0400 Organization: A noiseless patient Spider Lines: 134 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 13:53:55 +0200 (CEST) Injection-Info: dont-email.me; posting-host="e9923b1bf4e091a8793967377f2f9306"; logging-data="1267203"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX19XeV5r5F3uRrDD3eqUUGeh" User-Agent: Mozilla Thunderbird Cancel-Lock: sha1:ncjeNS2sZiQns/HS7HObcLs9z8U= In-Reply-To: Content-Language: en-US Bytes: 6890 On 4/14/2025 7:48 AM, olcott wrote: > On 4/14/2025 3:28 AM, Mikko wrote: >> 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. >> > > Changing the subject line is allowed. > Then maybe we should do as you do in such situations: On 8/10/2024 2:11 PM, olcott wrote: > Changing the title indicates a reply that I can ignore.