Path: ...!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!eternal-september.org!.POSTED!not-for-mail From: Keith Thompson Newsgroups: comp.theory Subject: Re: Unpartial Halt Deciders Date: Fri, 18 Apr 2025 15:42:18 -0700 Organization: None to speak of Lines: 77 Message-ID: <87o6wtnlbp.fsf@nosuchdomain.example.com> References: <87zfgdnufj.fsf@nosuchdomain.example.com> <0JxMP.1398486$cgs7.284882@fx14.ams4> <87sem5nu3q.fsf@nosuchdomain.example.com> MIME-Version: 1.0 Content-Type: text/plain Injection-Date: Sat, 19 Apr 2025 00:42:20 +0200 (CEST) Injection-Info: dont-email.me; posting-host="b62a019a496a9456e80ffe1b61d2a7b5"; logging-data="4175327"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1+26xsUWHx+K5B9qBGwe+JP" User-Agent: Gnus/5.13 (Gnus v5.13) Cancel-Lock: sha1:CDXWjr0bGKM005CrHMb+Yr41qzM= sha1:5GvlbDUKje44Ngf8D5PJXJnJg68= Bytes: 4498 Mr Flibble writes: > On Fri, 18 Apr 2025 12:32:41 -0700, Keith Thompson wrote: >> Mr Flibble writes: >>> On Fri, 18 Apr 2025 12:25:36 -0700, Keith Thompson wrote: >>>> Mr Flibble writes: >>>>> I, aka Mr Flibble, have created a new computer science term, the >>>>> "Unpartial Halt Decider". It is a Halt Decider over the domain of >>>>> all program-input pairs excluding pathological input (a manifestation >>>>> of the self referencial category error). >>>> [...] >>>> >>>> Do you have a rigorous definition of "pathological input"? >>>> >>>> Is there an algorithm to determine whether a given input is >>>> "pathological" or not? >>>> >>>> I could define an is_prime() function like this: >>>> >>>> bool is_prime(int n) { >>>> return n >= 3 && n % 2 == 1; >>>> // returns true for odd numbers >= 3, false for all others >>>> } >>>> >>>> I'll just say that odd numbers that are not prime are pathological >>>> input, so I don't have to deal with them. >>> >>> Pathological input: >>> >>> Self-referencial to the decider. >> >> OK. >> >> Do you have a *rigorous* definition of "pathological input"? >> >> Is there an algorithm to determine whether a given input is >> "pathological" or not? > > In the general case pathological input is not computable as it is a > category/type error (ergo not logically sound) so there is no algorithm > that can detect it. Specific forms of it can however be detected by a > Simulating Halt Decider given certain constraints - see Mr Olcott for > details. So your "new computer science term" is based on a concept that is not logically sound. Got it. Another point: The well known proof that the Halting Problem is not solvable works by assuming that a halt decider exists and then creating *one* input, based on the code of the decider, on which the decider cannot give a correct answer. You can call that input "self-referential to the decider". Producing just one input on which any halt decider must fail is all that was required to prove that the Halting Problem is in general not solvable. But it doesn't imply that there aren't plenty of other inputs on which any purported halt decider must fail. Let's say you have a halt decider that works reliably for non-pathological inputs. And let's say you write a program (or Turing machine) that halts if and only if it finds an even natural number greater than 2 that is not the sum of two primes. This program evetually halts if Goldbach's Conjecture is false, and never halts if Goldbach's Conjecture is true. Assume the program was written without any knowledge of any halt decider to which it might be fed. (Of course it must work with arbitrary precision integers, something that's entirely possible for a Turing machine, which has unlimited storage on its tape.) Now let's feed this program to your halt decider. *Either* your halt decider can resolve whether Goldbach's Conjecture is true or false (something that mathematicians have been unable to do for centuries) *or* that particular input is "pathological", even though it is not in any way "self-referential to the decider". -- Keith Thompson (The_Other_Keith) Keith.S.Thompson+u@gmail.com void Void(void) { Void(); } /* The recursive call of the void */