Path: ...!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!eternal-september.org!.POSTED!not-for-mail From: olcott Newsgroups: comp.theory Subject: Re: Halting Problem: What Constitutes Pathological Input Date: Mon, 5 May 2025 13:08:20 -0500 Organization: A noiseless patient Spider Lines: 89 Message-ID: References:

MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit Injection-Date: Mon, 05 May 2025 20:08:20 +0200 (CEST) Injection-Info: dont-email.me; posting-host="0a6320ec149f030cd98ca15e4d2d5e5f"; logging-data="1046110"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX199MgRvaGplOOOqu20dBdwN" User-Agent: Mozilla Thunderbird Cancel-Lock: sha1:SW1WBaD6XKXCt2p7PILFjlI7PhU= X-Antivirus-Status: Clean X-Antivirus: Norton (VPS 250505-4, 5/5/2025), Outbound message In-Reply-To: Content-Language: en-US Bytes: 4541 On 5/5/2025 1:06 PM, Mr Flibble wrote: > On Mon, 05 May 2025 13:45:07 -0400, dbush wrote: > >> On 5/5/2025 1:37 PM, olcott wrote: >>> On 5/5/2025 11:13 AM, Mr Flibble wrote: >>>> On Mon, 05 May 2025 11:58:50 -0400, dbush wrote: >>>> >>>>> On 5/5/2025 11:51 AM, olcott wrote: >>>>>> On 5/5/2025 10:17 AM, Mr Flibble wrote: >>>>>>> What constitutes halting problem pathological input: >>>>>>> >>>>>>> Input that would cause infinite recursion when using a decider of >>>>>>> the simulating kind. >>>>>>> >>>>>>> Such input forms a category error which results in the halting >>>>>>> problem being ill-formed as currently defined. >>>>>>> >>>>>>> /Flibble >>>>>> >>>>>> I prefer to look at it as a counter-example that refutes all of the >>>>>> halting problem proofs. >>>>> >>>>> Which start with the assumption that the following mapping is >>>>> computable and that (in this case) HHH computes it: >>>>> >>>>> >>>>> Given any algorithm (i.e. a fixed immutable sequence of instructions) >>>>> X described as with input Y: >>>>> >>>>> A solution to the halting problem is an algorithm H that computes the >>>>> following mapping: >>>>> >>>>> (,Y) maps to 1 if and only if X(Y) halts when executed directly >>>>> (,Y) maps to 0 if and only if X(Y) does not halt when executed >>>>> directly >>>>> >>>>> >>>>> >>>>>> int DD() >>>>>> { >>>>>> int Halt_Status = HHH(DD); >>>>>> if (Halt_Status) >>>>>> HERE: goto HERE; >>>>>> return Halt_Status; >>>>>> } >>>>>> >>>>>> https://github.com/plolcott/x86utm >>>>>> >>>>>> The x86utm operating system includes fully operational HHH and DD. >>>>>> https://github.com/plolcott/x86utm/blob/master/Halt7.c >>>>>> >>>>>> When HHH computes the mapping from *its input* to the behavior of DD >>>>>> emulated by HHH this includes HHH emulating itself emulating DD. >>>>>> This matches the infinite recursion behavior pattern. >>>>>> >>>>>> Thus the Halting Problem's "impossible" input is correctly >>>>>> determined to be non-halting. >>>>>> >>>>>> >>>>>> >>>>> Which is a contradiction. Therefore the assumption that the above >>>>> mapping is computable is proven false, as Linz and others have proved >>>>> and as you have *explicitly* agreed is correct. >>>> >>>> The category (type) error manifests in all extant halting problem >>>> proofs including Linz. It is impossible to prove something which is >>>> ill-formed in the first place. >>>> >>>> /Flibble >>> >>> The above example is category error because it asks HHH(DD) to report >>> on the direct execution of DD() and the input to HHH specifies a >>> different sequence of steps. >>> >>> >> In other words, you're demonstrating that you don't understand proof by >> contradiction, a concept taught to and understood by high school >> students more than 50 years your junior. > > For proof by contradiction to be valid the contradition has to be well- > formed which in the case of the Halting Problem it is not. > > /Flibble Yes. Self-contradiction is always ill-formed. -- Copyright 2024 Olcott "Talent hits a target no one else can hit; Genius hits a target no one else can see." Arthur Schopenhauer