paradox dragon

By /
⏱ 2 min read

I met three dragons. One always tells the truth, other one always lies and the last one alternates between lie and truth.

Dragon 1: You may ask us one question, then you must guess which dragon is which

Dragon 2: He’s lying. You may get three questions

Dragon 3: Oh no. It’s definitely one question

2026 Update: Paradoxes in Computer Science — The Halting Problem

Classical paradoxes (Liar’s Paradox, Russell’s Paradox, Barber Paradox) have direct analogs in computer science. The most famous: Turing’s proof that the Halting Problem is undecidable. These aren’t just philosophical puzzles — they set fundamental limits on what programs can compute.

def halting_proof_sketch():
    """
    The Halting Problem: Can we write HALT(P, I) that determines
    whether program P halts on input I?

    Turing's proof by contradiction (1936):

    Assume HALT(P, I) exists. Define:

        def paradox(P):
            if HALT(P, P):      # P halts on its own source code
                while True:     # Run forever (infinite loop)
                    pass
            # else: P loops -> we halt immediately (return None)

    Ask: does paradox(paradox) halt?

    Case A: HALT(paradox, paradox) = True (predicts it halts)
        -> paradox enters infinite loop -> does NOT halt
        -> Contradiction.

    Case B: HALT(paradox, paradox) = False (predicts infinite loop)
        -> paradox skips the while loop and returns immediately
        -> DOES halt
        -> Contradiction.

    Therefore HALT cannot exist.
    """
    print("Halting problem: undecidable (Turing, 1936)")
    print()
    print("Liar's paradox analog:")
    print("  'This statement is false.'")
    print("  If true -> it's false. If false -> it's true.")
    print("  paradox() does the same with program execution.")

halting_proof_sketch()

# What CAN be decided: bounded computation
def check_bounded(fn, input_val, max_steps=1000):
    """
    We cannot solve halting in general, but we CAN check bounded runs.
    Returns ('halted', result) or ('timeout', None).
    """
    # Simulate a simple counter-based program (not arbitrary code)
    # This is a safe approximation used by linters and static analyzers
    steps = 0
    try:
        result = fn(input_val)
        return ('halted', result)
    except RecursionError:
        return ('timeout', None)

# Example: detect infinite recursion in a bounded way
def safe_fibonacci(n, memo={}):
    if n  {result}")  # halted -> 55

# Real implications of undecidability:
undecidable_in_practice = [
    "TypeScript type checker: intentionally unsound to stay decidable",
    "Python mypy: uses type approximations, reports false positives",
    "Java null analysis: 'might be null' warnings, not 'is null' proofs",
    "Infinite loop detection: IDEs warn but cannot guarantee correctness",
]

print("nReal-world implications:")
for item in undecidable_in_practice:
    print(f"  - {item}")

Why this matters in FAANG interviews: Understanding undecidability explains why static analysis tools (linters, type checkers) can never be 100% precise — they must choose between false positives and false negatives. TypeScript’s type system is intentionally unsound in places to remain decidable and performant. Knowing these fundamental limits helps you design better tooling and set realistic expectations for automated verification systems.

Scroll to Top