Re: Refutation of Linz's Halting Problem Proof

On 2025-04-20 22:15:36 +0000, Mr Flibble said:

================================================================================                  Refutation of Linz's Halting Problem Proof
                  Based on Type Error Assumption
================================================================================  Date: April 20, 2025
 This document refutes Peter Linz's proof of the undecidability of the
halting
problem, as presented in "An Introduction to Formal Languages and
Automata," under
the assumption that self-referential input conflating deciders with
programs
constitutes a category (type) error. By enforcing a type system that
separates
deciders from programs, the diagonalization argument central to Linz's
proof is
invalidated, challenging the claim of universal undecidability.
 --------------------------------------------------------------------------------  1. Background: Linz's Proof
--------------------------------------------------------------------------------  Linz demonstrates the halting problem's undecidability using a
diagonalization
argument. He assumes a hypothetical halting oracle H(P, I),

...
Linz does not assume a halting oracle. The claim to b proven is that
no Turing machine is a halting decder. H is a Truing machine and Linz
proves that it is not a Turing machine.
Linz also proves the claim with antother proof that does not use
diagonalization.
--
Mikko