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: Mikko Newsgroups: comp.theory Subject: Re: Halting Problem: How my refutation differs to Peter Olcott's Date: Tue, 13 May 2025 11:31:34 +0300 Organization: - Lines: 128 Message-ID: References: <3bc01824e1d95a30b9784942a8b7ef3bc9ec8ff8@i2pn2.org>

<445621fd6d6864f68b1c6e2040cff818c336600f@i2pn2.org>

MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8; format=flowed Content-Transfer-Encoding: 8bit Injection-Date: Tue, 13 May 2025 10:31:34 +0200 (CEST) Injection-Info: dont-email.me; posting-host="70f604bba1da44c1dffb957c0b3101a2"; logging-data="1808749"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1+KskSapKOJoWluwOSnbUeU" User-Agent: Unison/2.2 Cancel-Lock: sha1:qCCtiEmEf0Dl92I7dP3OdtP+Ry4= Bytes: 6377 On 2025-05-12 14:31:58 +0000, olcott said: > On 5/12/2025 2:19 AM, Mikko wrote: >> On 2025-05-11 03:11:43 +0000, Mr Flibble said: >> >>> On Sat, 10 May 2025 22:00:26 -0500, olcott wrote: >>> >>>> On 5/10/2025 9:51 PM, Mr Flibble wrote: >>>>> On Sat, 10 May 2025 21:49:41 -0400, Richard Damon wrote: >>>>> >>>>>> On 5/10/25 9:18 PM, Mr Flibble wrote: >>>>>>> On Sat, 10 May 2025 21:07:34 -0400, Richard Damon wrote: >>>>>>> >>>>>>>> On 5/10/25 9:00 PM, olcott wrote: >>>>>>>>> On 5/10/2025 6:56 PM, Mr Flibble wrote: >>>>>>>>>> On Sat, 10 May 2025 18:40:53 -0400, Richard Damon wrote: >>>>>>>>>> >>>>>>>>>>> On 5/10/25 4:38 PM, Mr Flibble wrote: >>>>>>>>>>>> How my refutation differs to Peter's: >>>>>>>>>>>> >>>>>>>>>>>> * Peter refutes the halting problem based on pathological input >>>>>>>>>>>> manifesting in a simulating halt decider as infinite recursion, >>>>>>>>>>>> this being treated as non-halting. >>>>>>>>>>>> * Flibble refutes the halting problem based on patholgical input >>>>>>>>>>>> manifesting as decider/input self-referencial conflation, >>>>>>>>>>>> resulting in the contradiction at the heart of the halting >>>>>>>>>>>> problem being a category (type) error, i.e. ill-formed. >>>>>>>>>>>> >>>>>>>>>>>> These two refutations are related but not exactly the same. >>>>>>>>>>>> >>>>>>>>>>>> /Flibble >>>>>>>>>>> >>>>>>>>>>> And the problem is that you use incorrect categories. >>>>>>>>>>> >>>>>>>>>>> The decider needs to be of the category "Program". >>>>>>>>>>> >>>>>>>>>>> The input also needs to be of the category "Program", but >>>>>>>>>>> provided via a representation. The act of representation lets us >>>>>>>>>>> convert items of category Program to the category of Finite >>>>>>>>>>> String which can be an input. >>>>>>>>>> >>>>>>>>>> Those two categories you have identified are different hence the >>>>>>>>>> category error. >>>>>>>>>> >>>>>>>>>> >>>>>>>>> That is correct. A running program and an input finite string ARE >>>>>>>>> NOT THE SAME. >>>>>>>> >>>>>>>> But there is a direct relationship between the two. >>>>>>>> >>>>>>>> >>>>>>>> >>>>>>>>>>> The "Pathological Input" *IS* a Program, built by the simple >>>>>>>>>>> rules of composition that are allowed in the system. >>>>>>>>>> >>>>>>>>>> Such composition is invalid. >>>>>>>>>> >>>>>>>>>> >>>>>>>>> Richard is trying to get away with saying that a finite string THAT >>>>>>>>> IS NOT A RUNNING PROGRAM A RUNNING PROGRAM >>>>>>>>> >>>>>>>>> >>>>>>>> But they are related to each other, >>>>>>> >>>>>>> Even if there is some perceived relationship between the two >>>>>>> different categories it doesn't mean there still isn't a category >>>>>>> error. >>>>>> >>>>>> So, what is the error, since the input *IS* the finite string that was >>>>>> built by the program representation operation, and thus *IS* what an >>>>>> input needs to be. >>>>>> >>>>>> >>>>>>> Why relationship doesn’t rescue the mistake: >>>>>>> >>>>>>> * Shared context ≠ shared type. >>>>>>> – A pupil and a teacher are clearly related (one teaches, one >>>>>>> learns), but the question “Who is taller, the lesson?” commits a >>>>>>> category error because a lesson isn’t the kind of thing that has >>>>>>> height, regardless of its pedagogical ties to people. >>>>>> >>>>>> Which doesn't apply here, and you are just indicationg you don't >>>>>> understand what a representation is. >>>>>> >>>>>> The input is a finite string that represents a program. >>>>> >>>>> A program and a finite string representing a program are different >>>>> categories ergo we have a category error. >>>>> >>>>> /Flibble >>>> >>>> This made no difference difference until my simulating termination >>>> analyzer discovered they they don't always have the same behavior as was >>>> merely presumed for 90 years. >>>> >>>> A halt decider was "defined" to report on the behavior of the direct >>>> execution of the input ONLY because no one knew that it could possibly >>>> be different behavior than what the input finite string specifies. >>>> >>>> Everyone here takes this false assumption as the infallible word of God. >>>> A textbook says it therefore it must be infallible. >>> >>> Yes, the reason why these two different categories cause a category error >>> is because of the self-referential dependency between them, which >>> manifests as infinite recursion in your simulating halt decider case. >> >> That is contradicto in adiecto: a refertial dependncy between two entities >> of different categories cannot be self-referential. An entity can have a >> self-referential dependncy only to itself and it is always of the same >> category as it is itself. > > Referential dependency. > > void bar() > { > foo(); > } > > void foo() > { > bar(); > } That example specifies a non-halting computation. No category error. -- Mikko