Path: 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: Mon, 12 May 2025 10:19:03 +0300
Organization: -
Lines: 111
Message-ID: <vvs7d7$vk6t$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>
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Mon, 12 May 2025 09:19:04 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="d66022cf12555db523e1c5ad57a06eab";
	logging-data="1036509"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1/XYcVhyZFbWROokMv/4TV6"
User-Agent: Unison/2.2
Cancel-Lock: sha1:MrLk8rkzpnuT2eF4OrKbr90izSc=

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.

-- 
Mikko