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 <mikko.levanto@iki.fi>
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: <vvv016$1n6bd$1@dont-email.me>
References: <BPOTP.66191$v0S.4884@fx14.ams4> <3bc01824e1d95a30b9784942a8b7ef3bc9ec8ff8@i2pn2.org> <UIRTP.228282$_Npd.219273@fx01.ams4> <vvosru$3ql7h$1@dont-email.me> <bc5cc7788c2f522f313339d699520118aba2b18c@i2pn2.org> <YVSTP.290844$6Qab.237944@fx07.ams4> <445621fd6d6864f68b1c6e2040cff818c336600f@i2pn2.org> <EgUTP.680779$4AM6.183617@fx17.ams4> <vvp3sa$3voh3$1@dont-email.me> <PzUTP.89850$o31.7288@fx04.ams4> <vvs7d7$vk6t$1@dont-email.me> <vvt0ou$14pca$1@dont-email.me>
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 <IS> 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