Re: Refutation of Turing’s 1936 Halting Problem Proof Based on Self-Referential Conflation as a Category (Type) Error

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