Impossible Programs: Three Ways to End Before You Start
Table of Contents
1. Premise
Riff on Carin Meier, "A Program that Ends Before it Starts" (2026-05-30).
A program is t0,s0 -> t1,s1. "Ends before it starts" demands t1 < t0. That
is impossible iff you insist on a single global total order over events. Every
escape in the post works by quietly dropping that total order on a different
axis. Name the axis and the construct, and the impossibility collapses into
something ordinary.
| Blog dead-end | Axis abandoned | Construct | Lang |
|---|---|---|---|
| "redefine the t0/t1 relation" | order over data | lazy self-reference | clj |
| "send a message back" | order over control | first-class continuation | guile |
| "different clocks / time dilation" | order over time | no global clock (frames) | ruby |
| "quantum" | (none; real refusal) | nothing | -- |
2. Clojure: the result is defined before it is computed
fibs is consumed inside its own initializer. The thunk exists at t0; each
element is produced by reading earlier elements of the same not-yet-realized
sequence. Self-consumption via laziness is a fixed point: the value's definition
references its future. This is Bird's "circular programs" (1984) in disguise;
the same trick gives repmin, where the global minimum is threaded downward
before the upward pass has computed it.
;; element n is built from elements n-1, n-2 of a seq that is not yet realized. ;; the binding `fibs` appears in its own value. data-dependency time travel. (def fibs (lazy-cat [0 1] (map + fibs (rest fibs)))) (take 10 fibs) ;; => (0 1 1 2 3 5 8 13 21 34) ;; the pointed version: repmin. one structural pass; every leaf is replaced by ;; the tree's minimum, which is *injected before it is known* via a promise. (defn repmin [tree] (let [m (promise) go (fn go [t] (if (number? t) [t (delay @m)] ; emit the min we do not have yet (let [[lm l] (go (first t)) [rm r] (go (second t))] [(min lm rm) [l r]]))) [the-min shape] (go tree)] (deliver m the-min) ; t1 fills what t0 already referenced (clojure.walk/postwalk #(if (delay? %) @% %) shape))) (repmin [[1 [4 2]] [3 [9 0]]]) ;; => [[0 [0 0]] [0 [0 0]]]
3. Guile: the end re-enters the start carrying the answer
call/cc reifies "the rest of the program" as a re-runnable value. Capture it at
t0, run to t1, then invoke it: control drops back to the t0 binding site, now
holding t1's result. Side-effect order is t0, t1, t0', but the binding first
reached at t0 receives the future's value. This is the continuation-as-time-
machine framing (Friedman & Felleisen). Guile gives full re-entrant call/cc, so
the captured continuation can fire more than once.
(use-modules (ice-9 format)) (define k* #f) (define (run) (let ((msg (call/cc (lambda (k) (set! k* k) 'start)))) (cond ((eq? msg 'start) (display "t0: started, answer not computed yet\n") (future)) ; off to compute, then jump back (else (format #t "t0': answer ~a arrived at the start site\n" msg) msg)))) (define (future) (display "t1: computing... done\n") (k* 42)) ; re-enter run at the call/cc point (run) ;; t0: started, answer not computed yet ;; t1: computing... done ;; t0': answer 42 arrived at the start site ;; => 42
4. Ruby: the end timestamp precedes the start, in another frame
No fake threads. Model proper-time vs coordinate-time directly. A clock higher in the gravity well runs faster, so the same proper-time computation completes in less of our coordinate time. The post's integrated offsets over a century (Everest +2.3 ms, geosync +1.7 s, both faster than Cincinnati) fall straight out. If the faster frame messages its result back, we learn it before our local copy finishes. "Before" is a frame choice, which is exactly the relativity-of- simultaneity argument that motivates Lamport's partial order on events (1978).
SECONDS_PER_CENTURY = 100 * 365.25 * 86_400 Runner = Struct.new(:name, :gain_per_century) do def rate_gain # fractional clock-rate gain vs the kitchen gain_per_century / SECONDS_PER_CENTURY end end KITCHEN = Runner.new("Cincinnati kitchen", 0.0) EVEREST = Runner.new("Mt Everest", 2.3e-3) SATELLITE = Runner.new("Geosync satellite", 1.7) # coordinate time elapsed before a runner reports `proper_seconds` of work done def finishes_at(runner, proper_seconds) proper_seconds / (1.0 + runner.rate_gain) end work = SECONDS_PER_CENTURY # a 100-yr computation, so the offset shows [KITCHEN, EVEREST, SATELLITE].each do |r| done = finishes_at(r, work) puts format("%-20s done at t = %.6f s (Δ vs kitchen: %+.3f s)", r.name, done, done - work) end # Cincinnati kitchen done at t = 3155760000.000000 s (Δ vs kitchen: +0.000 s) # Mt Everest done at t = 3155759999.997700 s (Δ vs kitchen: -0.002 s) # Geosync satellite done at t = 3155759998.300000 s (Δ vs kitchen: -1.700 s)
5. Synthesis and refutation condition
All three are the same move: replace a total order with a partial order, then pick a linear extension where end precedes start. Data dependencies, control flow, and event time are each only partially ordered until you impose a clock.
Refutation condition. A genuine t1 < t0 under a single global total clock is
impossible: it is either retrocausality (no) or a halting oracle (no). Each
example here is honest only because it abandons that clock on one axis. The Ruby
case carries its own cost note: the speedup is the integrated dilation, 1.7 s per
century of computation. Blast radius of usefulness: nil. You pay 100 years to
arrive 1.7 seconds early, which is precisely why it stays a thought experiment and
not an accelerator.
The remaining axes for the other impossible things before breakfast: reversible computation (Bennett 1973), where the program is time-symmetric and t0/t1 are interchangeable by construction; and the quine, which ends where it starts rather than before. Quantum stays off the table for the same reason Carin shelved it.
6. Prior art
- R. Bird, "Using circular programs to eliminate multiple traversals," Acta Informatica, 1984.
- D. Friedman & M. Felleisen, continuation-as-time-machine framing; the "yin-yang" puzzle folklore.
- L. Lamport, "Time, Clocks, and the Ordering of Events in a Distributed System," CACM, 1978.
- C. Bennett, "Logical Reversibility of Computation," IBM J. R&D, 1973.