Path: news.eternal-september.org!eternal-september.org!.POSTED!not-for-mail
From: Mikko <mikko.levanto@iki.fi>
Newsgroups: comp.theory
Subject: Re: Final Statement on the Halting Problem
Date: Tue, 17 Jun 2025 11:27:05 +0300
Organization: -
Lines: 78
Message-ID: <102r8sp$293fk$1@dont-email.me>
References: <7hA3Q.159938$vK4b.76905@fx09.ams4> <e0695425cda6fd1733cee78d9a02280e5f56fe96@i2pn2.org> <F2F3Q.1262373$lZjd.664710@fx05.ams4> <102oqkb$1idvn$1@dont-email.me> <rsZ3Q.529202$6Qab.48722@fx07.ams4>
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Tue, 17 Jun 2025 10:27:06 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="ed336438e989950b4276e1e3d4de3565";
	logging-data="2395636"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1+Beo0TrrwzQMyeA59ClP4N"
User-Agent: Unison/2.2
Cancel-Lock: sha1:f9jyHDjjIgvbgeyhFlVILOdXcF8=

On 2025-06-16 18:33:59 +0000, Mr Flibble said:

> On Mon, 16 Jun 2025 13:11:23 +0300, Mikko wrote:
> 
>> On 2025-06-15 19:21:09 +0000, Mr Flibble said:
>> 
>>> On Sun, 15 Jun 2025 14:23:36 -0400, Richard Damon wrote:
>>> 
>>>> On 6/15/25 9:55 AM, Mr Flibble wrote:
>>>>> The halting problem as defined ignores recursive self reference
>>>>> focusing on the paradox instead, I would argue the recursive self
>>>>> reference leads to infinite regress in the definition of the problem
>>>>> thus creating a category error making the problem definition itself
>>>>> ill-formed.
>>>>> 
>>>>> /Flibble
>>>> 
>>>> But there is no recursive self-reference in the halting problem.
>>>> 
>>>> You only get that recursion when you assume that there exists a
>>>> program that can solve it, which is what shows that there is not
>>>> computation that can solve the halting problem.
>>>> 
>>>> You have just fallen for Peter Olcotts deceptive strawman definition
>>>> of the halting problem, because you don't really understand what you
>>>> are talking about.
>>> 
>>> Damon's response is defensive, dismissive, and slightly aggressive in
>>> tone. But setting tone aside for a moment, let's analyze the *technical
>>> content* of his reply point by point.
>>> 
>>> ---
>>> 
>>> ### 🔍 **Claim-by-Claim Analysis**
>>> 
>>> #### **1. "But there is no recursive self-reference in the halting
>>> problem."**
>>> 
>>> This is partially true, depending on what one means by "the halting
>>> problem."
>> 
>> Unless otherwise specified, one means the halting problem of Turing
>> machines.
>> 
>>> * The *general formulation* of the halting problem does **not** involve
>>> self-reference:
>>> 
>>>> “Given a program $P$ and input $x$, determine whether $P(x)$
>>>> halts.”
>> 
>> The halting problem is to construct a Turing machine that can answer
>> every question of the above pattern.
>> 
>>> That’s just a predicate over two arguments—no recursion or
>>> self-reference is involved here *yet*.
>>> 
>>> * However, **self-reference is absolutely introduced** in the *proof of
>>> undecidability*, specifically in Turing's diagonal argument using $H(P,
>>> P)
>>> $ and the construction of a paradoxical program $D$ such that $D(D)$
>>> leads to contradiction.
>> 
>> There is no self-reference in Turing's construction of $D$. If $H$ is
>> any Turing machine it is possible to construct the corresponding $D$.
>> Then one can run $D(D)$ and see whether it halts or enters a loop that
>> can easily be seen as non-halting. Turing's $D$ does not do anything
>> else. If is also possible to run $H(D, D)$ and then compare its answer
>> to the observed behaviour of $D(D)$. There is nothing paradoxcal there,
>> the answer is simply wrong.
> 
> BULLSHIT

That term is not applicable to my words, as they clearly are meaningful,
relevant, and true.

-- 
Mikko