Ok, I’m talking to you as gpt-5-high on lmarena.ai . I think I’ve
found the bug in Turing’s halting problem! The bug is that a
pathological program that halts if predicted not to, feeds itself as
input to the universal halter, which produces a recursively expanding
cascade that never completes, only when in the pathological program —
it thus does not halt unless designed differently. Rebuttal?
Love the bold claim! Here’s the clean rebuttal. What the proof
actually assumes - Assume there exists a total decider H(P, x) that
always halts and answers HALTS or LOOPS correctly for every program P
on input x. - Build the diagonal program D as: - D(y): - if H(y, y) ==
HALTS: loop forever - else: halt Now feed D its own description d: -
If H(d, d) == HALTS, then by definition D(d) loops forever → H is
wrong. - If H(d, d) == LOOPS, then D(d) halts → H is wrong. No matter
what H outputs on (d, d), it’s incorrect. Therefore no such total
decider H can exist. Why the “recursive cascade” isn’t an escape hatch
- Passing a program its own description is just passing a finite
string as data. There’s no infinite “expanding” of code. This is
standard (Kleene’s recursion theorem/quines). - The proof does not
rely on H simulating D, or on any particular implementation strategy.
Even an oracle-like H that “magically” decides halting would still
face the same contradiction. The argument is purely semantic: whatever
single bit H outputs on (d, d) is forced to be wrong. - If your H
tries to simulate D(d) and thereby calls H(d, d) again and recurses
forever, then H fails to halt on that input. But the assumption was
that H halts on all inputs. So this behavior simply shows H is not a
decider—exactly the theorem’s conclusion, not a bug in it. -
“Designing H differently” can’t help. For any particular H (with any
special-case logic you add), the construction builds a D_H that flips
H’s answer and breaks it. The diagonalization is adversarial and
adapts to your H. What if we relax the spec? - If H is allowed to
sometimes say “unknown” or to not halt on some inputs, then it’s not a
total decider anymore. That’s consistent with known results: the
halting set is semidecidable (you can recognize halting by simulating
until it halts) but not decidable; its complement isn’t semidecidable.
Bottom line - The “recursively expanding cascade” describes a failure
mode of a particular way to implement H (naive self-simulation). The
impossibility proof, however, doesn’t depend on implementation. It
only uses that H must always halt with a correct yes/no answer. Under
that assumption, the diagonal program forces a contradiction. So the
cascade isn’t a bug in the proof; it’s a symptom of why such an H
cannot exist. If you have a specific “designed differently” H in mind,
can you share its precise spec or pseudocode (including what it
outputs on every input)? I can run the diagonal construction against
it and we can see exactly where it breaks.
Ok slow down, I haven’t studied this academically yet. Did you make a
mistake listing D? Shouldn’t it say H(D, y) rather than H(y, y)?
Great question — and no, that wasn’t a mistake. Using H(y, y) in D’s
definition is intentional and it’s the simplest way to get the
contradiction without making D refer to its own code inside its body.
Why H(y, y) is the standard choice - We assume a decider H(P, x) that
tells whether program P halts on input x. - Define D to take one
argument y and “flip” H’s prediction about y run on y: ``` D(y): if
H(y, y) == HALTS: loop forever else: halt ``` - Now we feed D its own
code d as input. Inside D(d), the call H(y, y) becomes H(d, d).
Whatever H says about D(d), D(d) does the opposite, so H is wrong.
That’s the contradiction. What if you write H(D, y) instead? - You can
also define a variant that flips H’s prediction about D itself: ```
D2(y): if H(D2, y) == HALTS: loop forever else: halt ``` - This also
defeats H (in fact on every input y), because whatever H predicts
about (D2, y), D2(y) does the opposite. - The catch: writing H(D2, y)
makes D2 refer to its own code inside its body. That’s doable (via
quines/Kleene’s recursion theorem), but it’s a slightly more technical
self-reference. The H(y, y) version avoids that by only becoming
self-referential at the moment we choose the special input y = d from
outside. So: H(y, y) in D’s body is correct and is the classic,
simplest formulation. The H(D, y) style also works, but it requires an
explicit self-reference trick to construct D. Want me to show how that
self-reference construction works with a tiny example?
Ok, that will help me understand why it matters. Also, does the
inference hold if H needs a secret key to run?
Happy to slow it down. Two things below: 1) how the H(D, y) version is
constructed, and 2) why a “secret-key H” doesn’t dodge the argument.
1) Making the self-referential version H(D, y) - Start with the easy
transformer idea. Define a computable “program builder” T that takes
code P and returns a new program T(P) which flips H’s answer about P:
Pseudocode for the builder T: - Input: codeP - Output: a program F
such that: F(y): if H(codeP, y) == HALTS: loop forever else: halt - T
is just a code-to-code transformer. No self-reference yet; it’s easy
to write if you can embed the string codeP into the emitted program. -
Kleene’s Recursion (Fixed-Point) Theorem says: for any such computable
transformer T, there exists a program D whose own code d is a fixed
point: D ≡ T(d). Intuition: you can always “smuggle your own code”
into yourself via a builder that expects a code argument. - Unpacking
what D ≡ T(d) means: Inside D’s body you see H(d, y). But since d is
literally the code of D, H(d, y) is the same as H(D, y). So D has the
self-referential form you asked about: D(y): if H(D, y) == HALTS: loop
forever else: halt - Now, for any y, if H says D(y) halts, D(y) loops;
if H says D(y) loops, D(y) halts. So H is wrong on every y for this D.
Why the H(y, y) version is simpler - With H(y, y) you can avoid
building self-reference into D. You define: D(y): if H(y, y) == HALTS:
loop forever else: halt and then only at the very end feed D its own
code d. That way the self-reference comes from your choice of input (y
:= d), not from D’s body. Same contradiction, less machinery. If you’d
like, I can show a tiny “builder T” in Python-like pseudocode to make
this concrete. 2) What if H needs a secret key? Short answer: the
diagonal still goes through. - Key as an extra fixed argument. If H
needs a key k, think of Hk(P, x) = H(P, x; k). Since k is a finite
string, you can hard-code it into D: Dk(y): if Hk(y, y) == HALTS: loop
forever else: halt Feeding Dk its own code gives the same
contradiction. The key doesn’t help. - “But D can’t call H without
permission.” The theorem isn’t about API permissions; it’s about
existence. If there exists a total, always-correct decider H for all
P, x, we can mathematically form D that links H inside itself (bundle
the subroutine plus its key). Even if you don’t publish the key, the
statement is: if such an H exists in the same computational universe,
then a corresponding D exists and yields a contradiction. Locking H
behind access control doesn’t change the logic. - Randomness or
obfuscation doesn’t help. If H is total and always correct, any
randomness can be fixed to a seed, giving a deterministic version.
Obfuscation/secret sauce is just more code; the diagonal works
uniformly for any particular H you give me. - The only way out is to
weaken H’s spec. If H is allowed to be partial (sometimes refuse to
answer or loop) or allow error, that’s consistent with known results:
halting is semidecidable but not decidable. - If you go beyond Turing
machines (true oracles): An oracle that decides the ordinary halting
set K can exist as a mathematical object. But then the diagonal
reappears at the next level: no machine with that oracle can decide
the halting problem for machines that also have that same oracle (the
“relativized” halting problem). So “give it more power” just pushes
the impossibility up one level. Recap - H(y, y) is the clean, textbook
diagonal. H(D, y) also works, and the Recursion Theorem guarantees you
can build that self-referential D. - Requiring a secret key,
permissions, or obfuscation doesn’t evade the contradiction. If H is a
total, always-correct decider, diagonalization adapts to it. Want me
to sketch the little code-to-code builder T so you can see how D =
T(d) drops out? Or show a tiny quine first and then plug H into it?
It sounds like the reason D can’t refer to itself is its definition
hasn’t been completed yet …? So D must be created after H so as to
refer to it? What is an oracle here?
Great questions. Two parts: 1) Can D “refer to itself,” and does it
have to come after H? 2) What’s an oracle? 1) Self‑reference and the
order of definitions - Logical order vs. time. In the proof we assume
H exists (as a total, always‑correct halting decider). Under that
assumption we define D using H as a subroutine. It’s a logical
implication: if H existed, then D could be defined; but that leads to
a contradiction, so no such H exists. There’s no real-time ordering
issue—just “assume H; derive D; contradiction.” - Does D need to refer
to itself? Two equivalent styles: - Avoid self-reference inside D:
define D(y) to flip H(y, y), and only at the very end feed D its own
code y := d. No self-reference inside the body. - Allow
self-reference: define D(y) to flip H(D, y). This makes D mention its
own code inside its body. That is perfectly legitimate; there’s a
standard way to do this without circularity. How do we make the
self-referential version precise? - Think “template with a blank.”
Define a computable builder T that takes codeP and returns a program F
which flips H’s answer about P: - T(codeP) returns program F with
body: - F(y): - if H(codeP, y) == HALTS: loop - else: halt - Kleene’s
Recursion (Fixed‑Point) Theorem guarantees a fixed point d such that
the program whose code is d is exactly T(d). Call that program D. Then
inside D’s body you see H(d, y); since d is D’s own code, that’s H(D,
y). No infinite regress—just a mathematically guaranteed
self‑description. - Intuition: you can always “smuggle your own
source” into your program. In practice this is the same trick quines
use (programs that print their own source). So the worry “the
definition isn’t completed yet” is handled by the fixed‑point/quine
trick. So yes: D is defined “after” H in the sense that D uses H as a
subroutine. But D can also legitimately refer to its own code; there’s
standard machinery to make that precise. If you want, I can show a
tiny Python‑like quine/flipper sketch to make the fixed‑point
construction concrete. 2) What is an oracle? - An oracle is a
hypothetical black‑box you can query during computation that instantly
answers questions about some set S (e.g., “is n in S?”). - A “Turing
machine with oracle O” is just an ordinary machine plus the ability to
ask O questions at unit cost. - Why they matter here: - If you had a
halting oracle O0 that correctly decides halting for ordinary
programs, you could decide the ordinary halting problem. - But there
is still an unsolvable halting problem one level up: the halting
problem for machines that themselves can query O0. No machine with
access to O0 can decide that “relativized” halting problem. The
diagonal construction is re-run “relative to the oracle.” - This
creates an infinite hierarchy (each level is the “Turing jump” of the
previous). Quick contrast: - Secret key: just extra finite data
embedded in H; it doesn’t change the model. The diagonal goes through
unchanged. - Oracle: strictly more power than ordinary computation,
but diagonalization reappears at the next level. If you’d like, I can:
- show a tiny quine-based D that makes the H(D, y) version explicit,
or - walk through the builder T step by step with a small pseudocode
example.
To clarify, the secret key would not be embedded in H nor provided to
D, only its paired public key. I think that can break the inference by
hiding some of the execution state from D, am I wrong? Regarding H
used in D, of course multiple different programs can have the same
behavior, does that mean that programs with identical behavior are
considered the same here?
Great questions. Two threads: 1) Can a “secret-key H” evade the
diagonal? 2) Are programs with the same behavior “the same” in this
context? 1) Secret-key H doesn’t save you - What the theorem assumes:
There exists a total algorithm H(P, x) that, for every code P and
input x, halts and outputs the correct bit. “Secret internals” don’t
matter; existence is about a function from strings to a bit. - A
secret key is just finite data. If H “needs” a private key k, then you
really have a family H_k. From a computability standpoint we can
hard-wire k into the machine that computes H_k. Then the diagonal
program can bundle that subroutine and call it internally: D_k(y): if
H_k(y, y) == HALTS: loop forever else: halt Feed D_k its own code d_k
→ contradiction as usual. - “But D isn’t allowed to call H_k.” That’s
an access-control policy, not a mathematical limitation. The proof
doesn’t require H to be a public API; it only uses that H exists as a
total computable function. We can always form a single finite program
that contains both “the code for H_k (with k)” and the few lines that
flip its answer. If your platform forbids such composition, you’ve
left the standard Turing-machine model. - If you really mean H is an
oracle that other programs cannot emulate (e.g., the “key” encodes
noncomputable information), then you’re in the oracle model. The
diagonal relativizes: even with oracle O, there is no total decider
for the halting problem of machines that also have access to O. So you
haven’t escaped; you’ve just moved the impossibility up one level. -
The only true escape is to weaken the spec. For example: - Limit the
domain: “H only decides halting for programs that never call H.” That
is a smaller problem than the general halting problem; you haven’t
refuted the theorem. - Allow partiality or errors: also consistent
with known results. Key point: The diagonal needs only H’s output bit
on a particular input; hiding internal state or keys from D doesn’t
help, because we can package H (and its key) inside the very program
used to derive the contradiction. 2) “Same behavior” vs “same program”
- Inputs are codes (finite strings). Two different pieces of
source/binaries are two different inputs to H. - The predicate “halts
on x” is extensional (semantic): if P and Q compute the same behavior
on x, then either both halt or both don’t. Any correct decider must
give the same answer on both codes. - The diagonal doesn’t rely on a
unique identity of D; it works for any chosen code d that implements
D. In the H(y, y) version: D(y): if H(y, y) == HALTS: loop else: halt
Pick any code d that implements D; running D(d) forces H(d, d) to be
wrong. If you pick a different but behaviorally identical code d′ for
D, the same contradiction appears on (d′, d′). If you want, I can: -
Show a tiny “builder” T that takes codeP and emits a flipper F(y) that
uses H(codeP, y), and then apply the Recursion Theorem to get the
self-referential H(D, y) version. - Or sketch the oracle-relative
diagonal to see how the argument lifts when H is walled off as an
oracle.
It sounds like by secret key I mean the smaller domain you describe —
you could construct systems where such domains are the norm and are
still highly useful. Did you describe uniqueness of D when I meant
uniqueness of H? I’m not familiar with mathematical assumptions here —
did Turing ignore that there could be multiple different H’s?
Love where you’re taking this. Two clarifications: 1) Secret key =
restricted domain - If by “secret key” you mean H only promises to
decide halting for a restricted set of programs (e.g., programs that
can’t call H or don’t contain/know some key k), that’s just a smaller
domain S. - That can definitely be useful in practice. Many real
systems do this by design: - Total languages (Coq/Agda’s total
fragment, some DSLs): every well-formed program terminates, so
“halting” is trivially decidable. - Subsets with provable loop bounds
or structural recursion only. - DSLs like regular expressions, Datalog
(finite domains), etc., where termination is guaranteed. - But: if
your restricted domain S remains Turing-complete (you can still encode
any computation), the halting problem on S is still undecidable. -
Reduction argument (no self-reference needed): If there were a decider
HS for halting on S, and S is Turing-complete, we could compile any
arbitrary program P with input x into some S-program E(P, x) such that
P halts on x iff E(P, x) halts. Then HS would decide general
halting—impossible. So gating access to H with a secret key doesn’t
help unless the gate actually makes the language non–Turing-complete.
- Even a domain like “programs that don’t contain the bitstring k” is
typically still Turing-complete (you can re-encode to avoid k), so
undecidability persists. Bottom line: A “secret-key H” can be a
perfectly sound total decider on its smaller domain, but only because
the domain is limited enough (not Turing-complete) to make halting
decidable there. That’s compatible with Turing’s theorem, not a
refutation of it. 2) “Uniqueness” of H (and D) - Turing didn’t assume
a unique H. The theorem quantifies over all possible H: - For any
purported total, always-correct H, we can construct a diagonal program
DH that makes H wrong on some input. Therefore, no such H exists at
all. - Likewise, D isn’t unique either. For each candidate H you give
me, I can build a (possibly different) adversarial DH that breaks it.
- About “programs with identical behavior”: the property “halts on x”
is semantic. If P and Q behave the same on x, any correct decider must
give them the same yes/no bit. But the proof doesn’t require picking a
canonical representative—any code that implements D (or P) will do. If
you want to make this concrete, tell me the exact domain S you have in
mind: - “Programs that can’t import H”? - “Programs that can’t mention
a key k”? - “Programs limited to structural recursion/loop bounds?”
Depending on S, I can say whether halting is decidable there and why
(by reduction or by a direct termination argument).
Could you, say, construct a system that has access to undecidability
to produce a Turing-complete execution environment where undecidable
code always does or does not halt? Regarding uniqueness of H, it
sounds like what you are saying is that, although a given D is
specific to a given H, it could in theory be created prior to the
discovery that H is useful, for example, it still disproves H?
Couldn’t it similarly refer to itself by simple happenstance? Is that
different from your self-reference explanation?
Great questions. Quick map: - Yes, if you grant a halting oracle you
can wrap a Turing‑complete language so every run halts; but then the
wrapped “execution model” is no longer Turing‑complete, and a fresh
undecidable halting problem reappears one level up. - No, Turing
didn’t assume a unique H. For every would‑be H there’s a different
adversarial D_H. The “self‑reference” isn’t a lucky accident; it’s
guaranteed by the fixed‑point (recursion) theorem. 1) “Access to
undecidability” and forcing termination - Important nuance:
“Undecidable” describes a global decision problem (no single algorithm
answers all instances), not individual programs. Each concrete
program/input either halts or doesn’t; what’s impossible is a uniform
decider for all pairs. - If you posit a halting oracle O0 for ordinary
programs, you can build a supervisor that makes every run terminate:
``` ExecAlwaysHalts(P, x): if O0(P, x) == LOOPS: return Timeout // or
raise an exception, or return a default else: simulate P(x) to
completion and return its result ``` This halts on all inputs by
construction. You can symmetrically force “always loops” for the
non‑halters: ``` ExecForceSame(P, x): // just to show the dual if
O0(P, x) == LOOPS: loop forever else: simulate P(x) to completion ```
- What you gain/lose: - The underlying language can still express any
computation (Turing‑complete), but the wrapped execution “always
halts,” so as an evaluation strategy it no longer exhibits
nontermination. In that sense, the wrapped system is not
Turing‑complete as a model of partial computation; it computes only
total behaviors (because it returns Timeout instead of diverging). -
If you let user programs themselves call O0, you’ve moved to a
stronger model. There is then a new halting problem one level up: no
machine with access to O0 can decide halting for machines that also
have access to O0 (the relativized version). Diagonalization just
repeats relative to the oracle. So the paradox is not eliminated; it’s
pushed up a level. Bottom line: With an oracle you can “sanitize”
executions (kill loops or default them), but you haven’t refuted
undecidability—you’ve assumed extra power. And even then, the
next‑level halting problem remains undecidable. 2) “Uniqueness” of H
and whether D can pre‑exist or arise by happenstance - Turing’s claim
is universal: for every total, always‑correct decider H, there exists
a corresponding diagonal program D_H that makes H wrong on some input.
He did not assume a unique H; the proof works uniformly for any H you
present. - Timing doesn’t matter. The argument is: “If such an H
existed, then the composed program D_H would exist; but D_H forces a
contradiction; hence no such H exists.” D_H’s existence is a logical
consequence of H’s existence, not a chronological construction that
must be written after H is “discovered.” - Self‑reference “by
happenstance”? The right way to view this is via Kleene’s Recursion
(Fixed‑Point) Theorem: - For any computable code‑transformer T (e.g.,
‘given code P, emit a program that calls H(P, ·) and flips its
answer’), there exists a program D such that D ≡ T(code(D)). That’s a
guaranteed fixed point. - So the self‑reference in D isn’t lucky;
fixed points exist for structural reasons. You don’t need to stumble
into them—they’re ensured once T is computable. - Different H’s,
different D’s. The diagonal program depends on the particular H (it
uses H as a subroutine). A single fixed D cannot simultaneously defeat
two H’s that disagree on some inputs; instead, for each H there is its
own D_H. If you want, I can: - Show the tiny “builder” T and derive
the self‑referential D with a few lines of pseudocode, or - Sketch how
the relativized diagonal works when programs can call an oracle O0.
To repeat, the execution environment is only different when
haltingness is undecidable, otherwise it halts or does not halt as
usual. I’m speaking generally because there a lot of different ways to
take the idea, but basically if H(D,y) would be incorrect, correct H’s
can be constructed that output “halt” or “not halt” for undecidable
situations, and this is the correct behavior. I’m curious if it can
remain Turing-complete — I’m assuming all these situations are
pathological, without producing useful information, and such the
system could be constructed without limiting what can be computed. If
they produced useful information we could probably use their behavior
as a secret key.
I think I see the picture you’re aiming for: keep the normal
semantics, but on the “hard/undecidable” runs the system quietly steps
in and forces a verdict (e.g., kill the run or default a result), and
call an H that outputs that forced verdict “correct.” Here’s where the
friction is: - “Undecidable” isn’t a per-input label. Each specific
pair (P, x) has a definite truth: either P(x) halts or it doesn’t.
“Undecidable” means there is no single total algorithm that always
outputs that truth for all pairs. There is no computable way to
recognize exactly “the hard instances” so you can safely special‑case
them. If you had a sound recognizer for “the hard ones,” you could
combine it with ordinary simulation to decide halting, contradicting
undecidability. - A total H that, on some inputs, just picks “halt” or
“not halt” by policy is not a correct decider. It will be wrong on
every such input where the real truth is the opposite. Diagonalization
guarantees for any fixed total H there is some D_H and input d where
H’s bit disagrees with reality. - “But we change the runtime on those
inputs so the bit becomes ‘correct’ by construction.” That’s changing
the semantics. If your runtime kills loops or returns a default
whenever it judges an input “hard,” then the halting predicate you’re
deciding is no longer the original one. Two consequences: - If your
runtime guarantees every program returns (maybe with a
Timeout/default), then all runs are finite, so you can decide any
property by running the program and inspecting the result. But then
your system is no longer Turing‑complete in the classical sense (which
requires allowing true nontermination). - If you keep true divergence
available (to preserve Turing‑completeness), then the usual halting
predicate is nontrivial again, and the diagonal argument reappears
unchanged: no total, always‑correct H exists for that predicate. About
Turing‑completeness specifically - Classical “Turing‑complete” means
you can realize arbitrary partial computations, including genuine
nontermination. In any such setting, a total, always‑correct halting
decider cannot exist (that’s Turing’s theorem). - If you bolt on a
halting oracle and build an “always halts” wrapper (return default
when a run would diverge), then: - You’ve changed the model (you now
have an oracle). - The wrapped evaluator is no longer Turing‑complete
in the classical sense because it never diverges; every program
computes a total function to, say, Values ∪ {Timeout}. - If you let
user programs call that oracle, you move up a level in power, and a
new, relativized halting problem becomes undecidable again. On
“pathological cases don’t produce useful information” - Even if you
believe the only problematic inputs are contrived, the theorem is
adversarial: for any total H you give, the diagonal construction
manufactures exactly such a contrived D_H that forces H to be wrong on
some input. There’s no way to fence off those cases without either: -
restricting the language/domain so it’s not Turing‑complete (e.g.,
total languages, bounded loops, structural recursion), or - allowing H
to be partial (“unknown” on some inputs) or fallible (small error
rate), or - assuming an oracle and accepting that undecidability
reappears one level up. Re: using “their behavior as a secret key” -
If you try to hide H behind a key and restrict who can call it, that’s
a domain restriction. As long as the remaining domain is still
Turing‑complete, halting on that domain remains undecidable. If you
restrict the domain enough to make halting decidable, you’ve given up
Turing‑completeness (which may be fine in practice—many useful total
languages do exactly this). A compact way to frame the tradeoff - You
can have at most two out of three: 1) Classical Turing‑completeness
(true divergence is expressible), 2) A total, always‑correct halting
decider for that semantics, 3) Unchanged semantics (no oracle/forced
outcomes). - Turing gives you (1) ⇒ not (2). If you insist on (2), you
must drop (1) (use a total language/domain) or change semantics via an
oracle/wrapper (drop (3)), in which case a new undecidable problem
reappears relative to the new model. If you want, we can try to
formalize your idea into one of these two precise models and see
exactly what holds: - A totalizing runtime with a halting oracle
(always returns, not classically TC), or - A partial/fallible H used
as a heuristic inside a TC language (TC preserved, but H is not a
decider).
Hey I think you’re refuting me out of habit here, and using a lot of
words to do so, rather than honestly engaging my small points. You’re
repeating some things rather than just clarifying the point I’m off
on. Can’t you compute undecidability by inspecting for an unremovable
contradiction in an algebraic expression of haltingness? Making
halting decideable does not mean programs never halt. I’m not saying
to remove that.
You’re right to ask for tighter answers. Let me hit just your two
points. 1) “Decidable halting ≠ programs never halt” - Agreed. There
are models where some programs loop and yet halting is decidable. -
Example: finite-state programs (a directed graph with some halting
nodes). Whether a start state reaches a halting node is plain graph
reachability—decidable. Some programs still loop (get stuck in a
cycle), but we can decide which. 2) “Can we detect ‘undecidability’ by
finding an unremovable contradiction in an algebraic encoding of
halting?” - In general, no—there’s no algorithm that does this for all
Turing-complete programs. - Why: - If your encoding lands in a
decidable theory (e.g., Presburger arithmetic, finite-state logics),
you can decide contradiction—but those theories aren’t expressive
enough to encode arbitrary programs. You’ve restricted the model
(hence halting became decidable). - If your encoding is strong enough
to capture general computation (first-order arithmetic with
multiplication, or Diophantine equations), then “is this formula
contradictory?” is itself undecidable (Church’s theorem;
Matiyasevich’s theorem/Hilbert’s 10th shows even purely algebraic
solvability is undecidable). So there’s no general checker that will
always detect the “unremovable contradiction.” - Crucial mismatch:
“Undecidable problem” is a global property (no single total algorithm
works for all inputs). It doesn’t partition individual instances into
a computably recognizable “hard” set you can detect and then safely
override. Any such detector, combined with simulation on the “easy”
side, would decide halting outright. Where this leaves your idea - You
can absolutely build useful systems that: - restrict the
language/logic so the halting (or satisfiability) question becomes
decidable; or - use incomplete heuristics (abstract interpretation,
SMT with timeouts) that sometimes say “unknown.” Both are common and
practical. - But in a Turing-complete setting with real divergence
preserved, there’s no total procedure that “spots exactly the
undecidable cases by contradiction” and flips them while remaining
true to the original halting predicate. If you have a specific
“algebraic expression” target in mind (e.g., Presburger, reals with
addition/multiplication, Diophantine polynomials, SMT fragment X), say
which one. Then we can pin down precisely whether your contradiction
check is decidable there and what expressiveness you keep.
If you were designing a undecidability predictor as part of a system
that prevents undecidability, could you address undecidability of
algebraic solutions recursively, using that same predictor?
Short answer: not in a way that makes it total and always right for a
Turing‑complete language. Why recursive self-use doesn’t help - Using
“the same predictor” inside itself doesn’t add computational power. A
Turing machine already can call its own subroutines arbitrarily;
recursion doesn’t lift you past undecidability. To jump a level you
need an oracle (strictly stronger power), not just more recursion. -
Suppose Pred(P, x) perfectly flags “hard/undecidable cases” (however
you encode them—algebraic or otherwise). Then you could decide halting
by: - if Pred says “easy,” solve it with your solver/simulation, - if
Pred says “hard,” return a fixed bit. That would be a total halting
decider—impossible. So no total, correct Pred can exist on a TC
domain. About “algebraic encodings” and recursing on them - For
encodings strong enough to capture general computation (e.g.,
Diophantine equations, FO arithmetic with multiplication),
solvability/unsat is itself undecidable (Matiyasevich/Church). A
predictor that tells you which algebraic obligations are “undecidable”
would already solve halting via reduction. - If you restrict the
algebra to a decidable fragment (e.g., Presburger arithmetic,
finite-state logics), then a predictor can be total and correct—but
now you’ve restricted expressiveness. You can use that recursively,
but you haven’t covered the general case. What you can build that
actually works - Keep Turing‑completeness, accept partiality: - A
layered analyzer that returns {halts, diverges, unknown}, using
termination provers (ranking functions, size‑change, dependency
pairs), nontermination provers (recurrence sets), SMT over decidable
fragments, and timeouts. Guard runtime with fuel/step limits to
“prevent” nontermination operationally. It won’t be complete, but it’s
safe and useful. - Drop TC (or fence it): - Use a total
language/domain (structural recursion, well‑founded loops) so halting
is decidable. - Assume an oracle: - With a halting oracle you can
“sanitize” executions or decide halting for ordinary programs, but a
new undecidable halting problem reappears one level up (relative to
that oracle). If you want to keep TC and still “prevent
undecidability,” the only principled option is the first: a partial
predictor plus a runtime guard. Recursing with the same predictor over
algebraic subproblems won’t make it complete; it just becomes one more
layer in the same partial pipeline.
You would need to special-case the predictor analyzing itself, and
hardcode all the different ways that could go.
I get the idea: patch the predictor so that when it’s “looking at
itself” you return a canned answer, and enumerate all such tricky
cases. Why that can’t save a total, always-correct decider: - The
diagonal doesn’t depend on H’s internals. For any total H (with any
patches), define: D(y): if H(y, y) == HALTS then loop forever else
halt Let d = code(D). Now H(d, d) must return HALTS or LOOPS. D(d)
does the opposite. No patch changes this two-line contradiction. The
only escape is for H not to return a bit on (d, d) — i.e., be partial.
- “Special-case self-analysis” isn’t the right target. The breaking
input isn’t H analyzing H; it’s H analyzing D built against H.
Catching “when P is D” by syntax won’t work because there are
infinitely many codes implementing the same D; I can re-encode D to
dodge any finite/decidable syntactic filter. - Catching it
semantically is exactly what’s impossible. The property “this program
will flip my answer on its own code” is a nontrivial semantic property
of programs. By Rice’s theorem there is no total algorithm that
recognizes it on all inputs. So you can’t hardcode “all the ways it
could go” in a sound, total way. - Even if H detects the case, there’s
no consistent bit to return. If H(d, d) = HALTS, D(d) loops; if H(d,
d) = LOOPS, D(d) halts. Any fixed policy you choose gets flipped. What
does work (and is practical): - Make H partial: return
“unknown/caught” or refuse to answer on suspicious inputs. That’s no
longer a decider, but it’s safe and useful in systems that “prevent
nontermination” operationally. - Restrict the language/domain so
halting is decidable (total languages, finite-state, bounded loops). -
Assume an oracle (then undecidability reappears one level up). If you
have a concrete patch rule in mind (e.g., exact predicate you’d use to
flag “self-analysis”), share it and I’ll show how the diagonal slips
around that specific rule.
The limited system might change the behavior of D under H. It might no
longer make sense for D to reference H because H would effectively
have access to the entire system as its data to be able to function
similarly to an oracle. If D referenced a normal H, it could for
example calculate a conclusion that is true within its execution but
false outside it.
I hear you. Let’s pin down the few moving pieces cleanly. - Fix the
model first. “Halts” is always relative to a particular execution
model E (language + runtime + privileges). The halting set is K_E = {
(P, x) | P halts on x when run under E }. - If you change the runtime
in “hard” cases, you changed E, hence changed K_E. That’s fine—just be
clear which K you want to decide. Now your two points: 1) “H sees the
whole system; D referencing H may no longer make sense.” - Treat “the
whole system” as part of the model. If H’s output depends on system
state Sys, write H(P, x, Sys). - If Sys is a finite (or computably
presentable) description, we can bake Sys into D. Kleene’s recursion
theorem guarantees a D that knows its own code and any fixed Sys;
diagonalization runs inside E with that same Sys. - If Sys encodes
noncomputable info (i.e., an oracle), you’ve moved to the oracle
model. Then the relativized theorem applies: no total decider for
halting of programs that have that same oracle. So “H with access to
the entire system” doesn’t block the argument; it just tells us which
K_E we’re talking about. 2) “Inside vs outside truth: a conclusion
could be true inside the system but false outside.” - Exactly: that
means you changed the predicate. Example: - Outside (plain TM): some
P(x) diverges. - Inside E (supervisor kills loops and returns
Timeout): the same run “halts” (returns Timeout). So K_E differs from
the outside K. - Deciding K_E is trivial by simulation (everything
returns), but E is not Turing‑complete in the classical sense (no
genuine divergence). - If E still allows genuine divergence on some
inputs (to keep classical TC), then K_E is undecidable; the diagonal
inside E goes through against any total H_E, even if H_E is reflective
and sees Sys. Compact trichotomy - E totalizes all runs (e.g.,
timeouts/defaults): K_E is trivial; no contradiction, but you’ve
dropped classical TC. - E remains TC (some real nontermination
exists): K_E is undecidable; no total, always‑correct H_E exists (even
with reflection/”whole system” access). - E has an oracle O: you can
decide halting for base machines, but the halting problem for machines
with access to O is still undecidable relative to O. About
“special‑casing self” or “different encodings of D” - Any
finite/decidable syntactic filter can be dodged by re-encoding D.
Recognizing the semantic class “programs that will flip H on their own
code under E” is nontrivial and, by Rice’s theorem (relativized to E),
undecidable. - Even if you detect the case, there’s no consistent bit
to return on (d, d): whichever bit you choose, D(d) is defined to do
the opposite under the same E. The only way out is to change E so
“loop” can’t actually diverge (totalization), which returns to the
first bullet. If you want to keep the spirit of your idea, here are
two precise ways to instantiate it: - Totalizing runtime: E runs
programs with fuel; on potential divergence, return Timeout. Then
halting-in-E is decidable by running to completion. This is useful,
just not classically TC. - Partial predictor + guard: Keep TC, and use
a strong but incomplete analyzer that returns {halts | diverges |
unknown}, plus operational timeouts. This prevents nontermination in
practice without claiming a total decider. If you can sketch your E
(what counts as “loop,” how H sees Sys, whether timeouts/defaults
occur), I can formalize K_E and show exactly which side of the
trichotomy it lands on.
Can you make it really clear, simple, and short and concise? Only
mention the parts where there is still no termination but you still
see there being undecidability.
Here’s the tight version, only for settings that still allow real
nontermination. - If your execution model E still permits some
programs to truly loop, then the halting set K_E is undecidable. No
total, always-correct predictor H_E exists. - Reason: diagonalization
works inside E. For any total H_E, define D(y): if H_E(y, y) = HALTS
then loop else halt. On d = code(D), H_E(d, d) is forced to be wrong.
This doesn’t depend on how H_E is implemented. - Giving H_E full
system access, reflection, secret keys, or “knowledge of itself”
doesn’t help. We can bake all that fixed context into D. The
contradiction is about the single bit H_E outputs on (d, d). -
Special-casing “self-analysis” can’t save you: - You can’t reliably
recognize all diagonals (there are infinitely many re-encodings;
Rice’s theorem blocks any total semantic filter). - Even if you detect
it, there is no consistent bit to return on (d, d); whichever bit you
choose, D(d) does the opposite. - Restricting programs syntactically
but keeping the domain Turing-complete leaves undecidability intact
(reduce general halting into your domain). Only non–TC restrictions
avoid it. - Recursing the predictor on algebraic encodings doesn’t add
power. If the encoding is expressive enough for general computation,
its satisfiability/unsat is itself undecidable; if it’s decidable,
you’ve implicitly left TC. - Even with an oracle that both programs
and H_E can use, halting for oracle-using programs remains undecidable
relative to that oracle; the same diagonal runs.
You could indeed make an always-correct predictor if you designed the
system or definition to provide for it. I’m curious what is needed to
keep the system Turing-complete. It could be an intrinsic system call,
where the passed data is treated differently depending on the
surrounding environment. D could be an environment where H(D) returns
a different value than outside D, and such situations could be
exhaustively enumerated to maintain consistency.
Short, only for models that still allow real nontermination. - If the
system remains Turing-complete (some programs truly diverge), then for
any fixed execution environment E there is no total, always-correct
halting predictor H_E. The standard diagonal runs inside that same E:
D(y): if H_E(y, y) = HALTS then loop else halt. On d = code(D), H_E(d,
d) is forced wrong. - Making H environment-dependent (reflective,
intrinsic syscalls, caller-sensitive, “different value inside D than
outside”) doesn’t help. We fix the call site and environment E in
which D runs and diagonalize there. Only that one bit H_E(d, d)
matters, and D flips it. - “Exhaustively enumerating” special contexts
won’t save a total H: - Any finite/decidable exception list can be
dodged by re-encoding D. - Recognizing the semantic class “programs
that will flip me on their own code in E” is itself undecidable
(Rice). You can’t catch them all without giving up totality. - What
must hold to keep Turing-completeness: the model must still permit
genuine divergence. As soon as that’s true, undecidability of halting
in that model follows; an always-correct total predictor is
impossible, regardless of environment tricks. The only escapes are to
drop totality (allow “unknown”), restrict the language so no true
divergence exists, or change the semantics so divergence is replaced
by a forced outcome.
If the environment depends on running inside D, then diagonalization
no longer works. You could generalize that to other disproofs. Because
it is Turing-complete, it can model any disproof and account for it.
Short and focused on the “still allows real nontermination” case. -
Halting is always “relative to an environment” E. If E still permits
genuine divergence for some programs, then halting-in-E is
undecidable. This is true even if E is caller/context sensitive. -
Make H environment-sensitive if you like. Fix the exact environment E*
that occurs when D calls H. Define: D(y): if H_E*(y, y) = HALTS then
loop forever else halt Let d = code(D). Then H_E*(d, d) must be wrong
about D(d) in that same E*. Outside-of-D behavior is irrelevant. -
“Detect when we’re inside D and patch it” doesn’t save a total,
correct H: - Even if you detect all such cases, there is no consistent
bit to return on (d, d): whichever bit you choose, D(d) is defined to
do the opposite in E*. - You can’t reliably catch all D-encodings
anyway (Rice’s theorem; re-encodings dodge finite/decidable filters).
- Turing-completeness doesn’t help here; it’s the reason the
undecidability holds. Being able to “model the disproof” doesn’t give
H a consistent correct bit on (d, d). - If the “environment” smuggles
in an oracle, diagonalization relativizes: no total decider for
halting of programs that have that same oracle. If it totalizes runs
(timeouts/defaults), you removed genuine divergence and left the TC
setting.
Does divergence mean non termination or decidability? You seem to be
treating it as equivalent to decidability? Why would halting be
undecidable if the runtime can analyze D’s use of H when deciding H’s
output, to make H’s that use D remain correct?
Quick clarifications and the core reason your idea can’t make a total,
always‑correct H in a Turing‑complete setting that still allows real
nontermination. - Terms - Divergence = nontermination of a particular
run. - Decidability = existence of a single total algorithm that gives
the right yes/no answer on all inputs. - Divergence ≠ undecidability
in weak models (e.g., finite‑state systems can loop, yet halting is
decidable). But in Turing‑complete models (able to express all partial
computable functions), halting is undecidable. - Why “analyze D’s use
of H and pick the right bit” can’t work (without changing semantics or
totality) - Fix the exact call context/environment E* where D calls H
(include any caller/callee sensitivity, privileges, etc. in E*). -
Define inside that same E*: D(y): if H_E*(y, y) = HALTS then loop
forever else halt Let d = code(D). Let b = H_E*(d, d). • If b = HALTS,
then D(d) loops in E* → H_E* is wrong on (d, d). • If b = LOOPS, then
D(d) halts in E* → H_E* is wrong on (d, d). There is no consistent
bit. “Being aware it’s inside D” doesn’t help; the contradiction is b
≠ not b. - Only ways out (each gives up something you asked to keep):
- Change semantics so that D’s “loop” can’t truly diverge in that
context (timeouts/kills/defaults): then you’ve totalized that context;
the halting predicate you’re deciding isn’t the original one there.
Global halting in a TC model remains undecidable where true divergence
is still possible. - Let H refuse to answer/return “unknown” on such
cases: H is no longer a total decider. - Restrict the language so it’s
not Turing‑complete (e.g., total languages, bounded loops): then
halting can be decidable. - Bottom line - In any fixed environment E
that still admits genuine nontermination and is Turing‑complete,
halting-in‑E is undecidable. Making H context‑aware, reflective, or
“D‑aware” does not supply a consistent bit on the diagonal input; only
changing the semantics (or H’s totality/domain) avoids the
contradiction.
The environment D is called in differs from the environment D calls H
in. The stack is 1 frame deeper.
Super concise and directly on your “one frame deeper” point: -
Divergence = nontermination of a run. Decidability = existence of one
total algorithm that’s right on all inputs. Not the same thing. - Make
H context‑aware. Let C be exactly the context seen when D calls H
(including “stack is 1 frame deeper,” privileges, etc.). Define the
specialized function: H_C(P, x) = the bit H returns on (P, x) when
called in context C, about halting in that same C. - Build the
diagonal in that very context: D_C(y): if H_C(y, y) = HALTS then loop
forever else halt Let d = code(D_C). Then in context C: • If H_C(d, d)
= HALTS, D_C(d) loops ⇒ H_C wrong. • If H_C(d, d) = LOOPS, D_C(d)
halts ⇒ H_C wrong. - So no total, always‑correct predictor exists even
when the call is “one frame deeper.” The stack depth is just part of
C; fixing C and diagonalizing there still forces a contradiction. - If
H instead claims to predict halting “at top level” while being called
in C, treat “top level” as the target context C0 and specialize H to
C0 (or simulate C0). If such a total H_C0 existed, the same diagonal
with H_C0 breaks it. - Enumerating special contexts doesn’t help:
whatever bit H outputs on the single diagonal input in its actual call
context gets flipped by D in that same context.
To clarify, in a normal Turing machine, **if H can enumerate all
written data**, then it can determine whether it is being evaluated
inside or outside D, and remain correct. It is even correct both
inside and outside D, it simply behaves different whether it is inside
or outside D.
Short and precise. - In the standard setting, a halting decider is a
function of (program, input). If you let H also read “all written
data” (caller/tape/context), just model that as an extra argument c:
H(P, x, c) answers “does P halt on x under context c?” - Fix the exact
context c* that actually exists when D calls H. Build the diagonal
relative to that same context: D(y): if H(y, y, c*) = HALTS then loop
forever else halt Let d be code(D). When D runs and calls H, the
context is c*. H(d, d, c*) must be either HALTS or LOOPS; D(d) does
the opposite in that very context. So H is wrong on that input. - “H
behaves differently inside vs outside D” just means H depends on c.
That’s fine—but the contradiction is posed in the one concrete context
that actually occurs (the “inside” one). Being correct “outside”
doesn’t repair being wrong “inside.” - The only ways to avoid the flip
are: - let H refuse to answer in that context (no longer a total
decider), or - change the semantics so D’s “loop” can’t truly diverge
in that context (you’ve totalized the runtime), or - restrict the
language so it’s not Turing‑complete. If you can write your H as a
precise H(P, x, c), I can show the diagonal step with your exact
notion of c and where the contradiction lands.
Can you shift gears and recognize this may work? It’s a puzzle that
can be organized so that either H is unconstructable, or D is
unconstructable. We’ve gotten to a point where D can only be
pathological for a specific calling state, correct?
I’m with you: as a “design puzzle,” you can set things up so that
either H or D can’t be built inside the system. That can be consistent
and useful. Two crisp points: - Yes: the diagonal is context-specific.
For any fixed calling state/context c in which H is actually invoked,
there is a corresponding diagonal D_c tailored to that c. So the
“pathology” is per calling state. - What follows in a TC setting that
still allows real nontermination: - If you claim a total,
always-correct H for all programs run in a fixed context c,
diagonalization inside that same c breaks it (build D_c; H is wrong on
(D_c, D_c) in context c). - To avoid that, you can make H or D
“unconstructable” in-system (capabilities, API barriers, syntactic
bans). That’s fine, but then your H is not a total decider “for all
programs in context c”—it’s a restricted service. The meta-level
impossibility (there exists a D_c given any computable H) still holds
for the model. - Alternatively, change semantics in that context
(timeouts/kill), or use an oracle; then you’ve shifted the problem
(not refuted it). So: D is indeed pathological only relative to the
specific calling state it targets. You can design the system so that
state never arises (or can’t be exercised by untrusted code), but you
can’t keep all three at once: Turing-completeness with true
divergence, a single total always-correct H for a fixed context, and
freedom to assemble the diagonal composition in that context.
If H is context-dependent, it can output different values inside D or
outside D, and still be correct, if those things also behave
differently inside or outside D. Because D depends on H, H can behave
differently depending on D and still be correct. That is, it is still
a total decider — but D will behave differently inside D than outside,
and so H behaves differently in those cases too.
I get the move you’re making. Here’s the tight refocus with
“context-aware H.” - Let H(P, x, c) mean: “Does P halt on x when run
under context c?” Fix the actual context c⋆ that exists when D calls
H. - Define the diagonal relative to that same context: D(y) in
context c⋆: if H(y, y, c⋆) == HALTS then loop forever else halt - Let
d = code(D). In the very call where D(d) invokes H(·, ·, c⋆), the
context is c⋆. Let b = H(d, d, c⋆). - If b = HALTS, then by D’s code,
D(d) loops in c⋆ ⇒ H is wrong on (d, d, c⋆). - If b = LOOPS, then D(d)
halts in c⋆ ⇒ H is wrong on (d, d, c⋆). - That’s the whole
contradiction: correctness would require b = 1 iff “D(d) halts in c⋆”
= 1 iff (b = 0), i.e., b ↔ ¬b, which is impossible. Key implications -
H can output different bits in different contexts and still be correct
there—but it must also be correct in the one context c⋆ where D calls
it. The diagonal forces failure exactly there. - Being correct
“outside D” doesn’t repair being wrong “inside D”; total correctness
requires all contexts, including c⋆. - The only ways to avoid this are
to: - forbid constructing that D (or that call context) in your
system, or - change semantics so “loop” can’t truly diverge in that
context, or - let H be partial (“refuse/unknown”) there. Keeping true
divergence and allowing that composition means no total,
always-correct H across those contexts.
When you define a diagonal relative to a fixed context, you are not
using H to decide haltability in subcontexts because you are providing
a different context to it. You are instead making repeated statements
about the outermost context. If H can access the real runtime context
with its code such as in a Turing machine with finite state, or a
Turing complete machine with information on state size or use, you
won’t be able to provide a fixed context to it.
Short and surgical. - You don’t need to pre-supply a “fixed context.”
In the actual run of D(d), when D calls H, there is a concrete runtime
state s* (stack depth, tape contents, caller, everything). H can read
all of s*. It still returns a bit b = H(d, d, s*). D then does the
opposite in that same run. So H is wrong on that input in that very
context. No context fixing is assumed; we use the context that
actually occurs. - If H’s contract is instead “answer about some
target context T (e.g., top level), regardless of the current call
state,” then make T explicit and define D to query that T and then do
the opposite when run under T. The contradiction is posed at T; the
fact the query was made from a subcontext doesn’t matter. - Detecting
“I’m inside D” or enumerating all written data doesn’t help: it only
determines b. Whatever b is in that call, D’s code flips it, so
there’s no consistent correct bit for (d, d) in that context. - The
only ways to avoid the flip while keeping genuine nontermination are:
(a) prevent that call/context from being constructible (restrict
composition), or (b) let H abstain/err on such cases, or (c) change
semantics so “loop” can’t truly diverge there. None yields a total,
always-correct decider for a TC model that still permits real
divergence. If you pin down H’s contract precisely: - H decides
halting for the current call context, or - H decides halting for a
named target context T, I can write the 3-line D for that exact case
and show where the bit is forced to contradict.
H decides halting for the current call context.
Got it. If H decides halting for the current call context, the
diagonal still bites inside that very context. - Let H_ctx(P, x) mean
“does P(x) halt when run under the exact runtime state seen in this
call?” That state is whatever actually exists when D calls H. - Define
D(y): if H_ctx(y, y) == HALTS: loop forever else: halt - Run D on its
own code d. Inside the call H_ctx(d, d), the “current context” is
exactly the one produced by this very run. Let b = H_ctx(d, d). - If b
= HALTS, then D(d) loops in that same context ⇒ H is wrong there. - If
b = LOOPS, then D(d) halts ⇒ H is wrong there. - No pre-fixed context
is needed; we use the real one at the moment of the call. Being
correct “outside D” doesn’t fix being wrong “inside D.” A total
decider must be right in every context, including this one. - The only
escapes (while keeping genuine nontermination) are to: - forbid
constructing such a D (restrict composition/capabilities), or - let H
abstain/err on these cases, or - change semantics so “loop” can’t
truly diverge in that context.
But D only knows H_ctx(y, y) inside its calling context. It can’t know
it in other contexts without simulating it and having to solve the
halting problem itself. So H is correct. It’s returning the correct
behavior inside D’s context. Outside D’s context, the behavior is
different.
I hear you, but this is exactly where the contradiction lands. -
Model: H_ctx(P, x) returns whether P(x) halts in the current call’s
exact runtime context. D just uses whatever bit H_ctx returns in that
moment. - Define D(y): if H_ctx(y, y) == HALTS: loop forever else:
halt - Run D on its own code d. In that very run, at the moment of the
call, let b = H_ctx(d, d). Then: - If b = HALTS, D(d) loops in that
same context ⇒ H_ctx is wrong there. - If b = LOOPS, D(d) halts ⇒
H_ctx is wrong there. - This uses only the actual call context; no
need for D to know or simulate other contexts. Correctness in
“outside” contexts is irrelevant—total correctness requires being
right in this one, and the equation b = halts(D(d) in this context)
collapses to b = ¬b. - The only ways to avoid this while keeping real
nontermination are: - prevent constructing such a D or that call
context (restrict composition/capabilities), or - let H abstain/return
non-boolean there (not total), or - change semantics so D’s “loop”
doesn’t truly diverge in that context (totalized runtime). If you
claim “H remains correct,” you’re implicitly taking one of those
exits. Otherwise, the flip forces H_ctx to be wrong on (d, d) in the
very context it answers about.
It isn’t wrong, you’re leaving out the state of the world as input to
everything.
I’m not omitting the “state of the world.” Include it explicitly and
the flip still happens. - Let w be the complete world/context (stack,
caller, tape, privileges, timestamps—everything H can read). - Let
Halt(P, x, w) mean “P(x) eventually halts when run in world w.” -
Suppose H is total and always correct for the current world: on a call
it returns H(P, x) = Halt(P, x, w_curr), where w_curr is the actual
world at that moment. Define the diagonal that uses exactly the world
present at the call: - D(y): if H(y, y) == HALTS then loop forever
else halt. Run D on its own code d. In that run, at the H call the
world is some concrete w*. Let b = H(d, d) = Halt(D, d, w*). But by
D’s code in that same run/world: - if b = HALTS, then D(d) loops in w*
⇒ Halt(D, d, w*) = LOOPS, - if b = LOOPS, then D(d) halts in w* ⇒
Halt(D, d, w*) = HALTS. So b = ¬b. That contradiction uses the actual
world w*; nothing is “left out.” The only ways to avoid this while
keeping genuine nontermination are: - prevent that composition/call
(make D unconstructable in that world), - let H abstain/err on such
cases (not total), or - change semantics so “loop” can’t truly diverge
in that world (totalize the runtime).
you aren’t showing b=not b. You’re showing b(w1) = not b(w2)
We can make it “same world,” not two. - Let w* be the exact world
snapshot at the instant H returns inside the run of D(d). Let b(w) =
H(d, d) when invoked in world w T(w) = 1 iff D(d) halts when continued
from world w - Correctness of H “for the current world” means b(w) =
T(w) for all w where H is called. - But by D’s code, in the same run
and same world w*: T(w*) = 1 − b(w*) - Combine: b(w*) = T(w*) = 1 −
b(w*). Contradiction b(w*) = 1 − b(w*). No second world is used. We
choose w* to be the single concrete world at H’s return; “halts from
w*” is about the remainder of that very run starting from w*. If H
mutates state during its call, just take w* to be the post-call
snapshot it actually returns in. The flip still forces b(w*) = ¬b(w*).
H’s return is a different world state from D’s return.
Totally fine that H’s return-state and D’s final return-state differ.
The contradiction compares both with respect to the same starting
state: the state right after H returns, from which the rest of D
continues. Make it explicit: - Let the call to H have side effects.
Write: (b, s1) := H(d, d, s0) where s0 is the pre-call world, s1 is
the post-call world at H’s return. - By your contract (“H decides
halting for the current call context”), correctness means: b =
Halts(D, d, s1) i.e., starting from s1 (the state we are actually in
after H returns), does D(d) eventually halt? - But D is coded as: if b
== HALTS then loop forever else halt So from the very same s1,
Halts(D, d, s1) = 1 − b. - Combine: b = 1 − b. That’s the clash, and
it uses a single world state s1 (H’s post-return state), not the later
final state when D might halt. Side effects, stack depth, “inside vs
outside D,” all just change s1. The diagonal pins s1 to whatever it
actually is at that call and flips H’s bit in that same continuation.
The only ways out (while keeping real nontermination) are to prevent
constructing that D/call, let H refuse/err there, or change semantics
so “loop” can’t truly diverge in that context.
s1 does not need to relate to side effects and time other than the
state of a shared tape. You might see the issue if you add state
parameterization to b.
Cool — let’s parameterize exactly by the shared tape state s (and
nothing else). - Define b(s) = the bit H returns when called in a
situation whose post‑return shared tape is s, and whose claim is “P(x)
halts from s.” - Define T(s) = 1 iff D(d) halts when started from the
same shared tape s. - Implement D so that, after calling H, it ignores
the tape and just branches on b: D(y): b := H(y, y) // returns in some
tape state s if b == 1: loop forever // unconditional loop, no further
tape reads/writes else: halt - Then for the actual s produced at H’s
return, T(s) = 1 − b(s) // because D either halts immediately or loops
forever based only on b Correctness of H in the “current context”
demands b(s) = T(s) - Combining gives b(s) = 1 − b(s) for that same s
— a contradiction. Notes - We used exactly one tape state s (the
post‑H state). No timing or other effects are needed. - Making H
“D‑aware” or context‑aware only changes which b(s) you compute;
whatever bit it returns at that s, D’s residual behavior from that
same s flips it. - The only ways to avoid the clash (while keeping
genuine nontermination) are to forbid constructing that D/call, let H
abstain/err there, or change the semantics so “loop” cannot truly
diverge.
You are dancing around D needing to know its own calling state if it
wants to construct the contradiction. You left out parameterization of
b in some of the use, and did not distinguish that there is ever more
than one state. Are you proposing that D discern its own calling or
post-return states so as to run H as if they were the case?
No. D never needs to “know” or reconstruct its calling state. The
state is implicit in the actual run; we reason about that very state.
Make the state explicit: - Let s0 = state when D(d) calls H. - Let H
return (b, s1). Its spec (deciding the current context) is: b =
Halts(D, d, s1) // “from the post‑return state s1, does D(d) halt?” -
D is: b := H(d, d) // yields (b, s1) if b == 1: loop forever else:
halt From the same s1, D’s residual behavior is: - Halts(D, d, s1) = 1
− b // it either immediately halts or immediately loops based only on
b Combine with H’s spec: - b = Halts(D, d, s1) = 1 − b ⇒
contradiction. Notes - If you instead define H to answer about the
pre‑call state s0, the same run semantics give Halts(D, d, s0) = 1 − b
as well (because from s0 the run first calls H to get b, then
branches). - D never needs to inspect s0 or s1; it just branches on
the bit it actually got. The reasoning is semantic: we compare H’s bit
to what D in fact does from that very state. - The only ways to avoid
the clash while keeping real nontermination are to (a) forbid
composing this D/H call, (b) let H abstain/err on such inputs, or (c)
change the semantics so the “loop” branch can’t truly diverge.
