Path: ...!news.misty.com!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: =?utf-8?Q?Re:_Refutation_of_Turing=E2=80=99s_1936_Halting_Problem_Proof_Based_on_Self-Referential_Conflation_as_a_Category_(Type)_Error?=
Date: Tue, 22 Apr 2025 12:45:40 +0300
Organization: -
Lines: 56
Message-ID: <vu7og4$b3gh$1@dont-email.me>
References: <TuuNP.2706011$nb1.2053729@fx01.ams4>
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Tue, 22 Apr 2025 11:45:41 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="77e99febd2ea8fbd06e9bc59456aaf8d";
	logging-data="364049"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1+iEPqCTptYkyMjXSydJfKG"
User-Agent: Unison/2.2
Cancel-Lock: sha1:C7yPvQNsD0zgrZsRzfRwFspC6hM=
Bytes: 3560

On 2025-04-21 16:37:07 +0000, Mr Flibble said:

> This document refutes Alan Turing’s 1936 proof of the undecidability of
> the halting problem, as presented in “On Computable Numbers, with an
> Application to the Entscheidungsproblem” (Proceedings of the London
> Mathematical Society, 1936), by leveraging the assumption that self-
> referential conflation of a halt decider and its input constitutes a
> category (type) error. The refutation argues that Turing’s proof, which
> relies on a self-referential construction, is invalid in a typed system
> where such conflation is prohibited.
> 
> ---
> 
> 1. Turing’s 1936 Halting Problem Proof
> Turing’s proof demonstrates that no general algorithm (Turing machine) can
> decide whether an arbitrary Turing machine halts on a given input. The
> proof proceeds as follows:
> 
> - Assume a universal Turing machine U that can simulate any Turing machine
> M on input w.

Why do you mention this assumption here but do not use it below?

> - Assume a halt decider H, a Turing machine that takes as input the
> description of a Turing machine M (denoted <M>) and an input w, and
> outputs:
>   - 1 if M halts on w.
>   - 0 if M does not halt on w.
>   Thus, H(<M>, w) determines whether M halts on w.
> - Construct a Turing machine D (the “diagonal” machine) defined as:
>   - D takes as input the description of a Turing machine <M>.
>   - D runs H(<M>, <M>), i.e., it checks whether M halts when given its own
> description as input.
>   - If H(<M>, <M>) = 1 (M halts on <M>), D enters an infinite loop (does
> not halt).
>   - If H(<M>, <M>) = 0 (M does not halt on <M>), D halts.
> - Apply D to its own description, i.e., evaluate D(<D>):
>   - If H(<D>, <D>) = 1 (D halts on <D>), D loops infinitely (does not
> halt).
>   - If H(<D>, <D>) = 0 (D does not halt on <D>), D halts.
> - This creates a contradiction: H’s output about D’s halting behavior
> leads to the opposite behavior, implying that H cannot exist for all
> Turing machines and inputs.
> - Therefore, the halting problem is undecidable, as no such H can
> consistently determine halting for all cases.
> 
> Turing’s proof relies on self-reference, where D is defined in terms of
> H’s evaluation of D’s own description, leading to the diagonalization
> contradiction.

No, that is not true. The definition of D does not depend on H's evaluation
of anything. D is constructed from H itself.

-- 
Mikko