Impossible Programs: Three Ways to End Before You Start
Table of Contents
1. Premise
Checked against the primary source (gigasquidsoftware.com/blog/2026/05/30/a-program-that-ends-before-it-starts/). All four blog dead-ends match verbatim — vector-embedding t0/t1 redefinition ("Yeah no, let's move on"), message-back continuation, time dilation, and quantum refusal — as do the integrated century offsets (Everest +2.3ms, geosync +1.7s, both faster than Cincinnati).
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
Ran both snippets unmodified (clojure -M). `(take 10 fibs)` => (0 1 1 2 3 5 8 13 21 34); `(repmin [[1 [4 2]] [3 [9 0]]])` => [[0 [0 0]] [0 [0 0]]]. Output matches the comments exactly.
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
Ran unmodified under Guile 2.2. Output matches the comments exactly: t0 start, t1 computing, t0' answer 42 arrived, final value 42.
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
Ran unmodified under ruby. Output matches the comments exactly (kitchen +0.000s, Everest -0.002s, satellite -1.700s). The input rate-gain constants (2.3e-3, 1.7) match the blog's stated century totals (Everest +2.3ms, geosync +1.7s) verbatim.
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
Bird's title was truncated, dropping "of data"; corrected against the primary source (Acta Informatica 21, 239-250, 1984, doi:10.1007/BF00264249). Lamport 1978 and Bennett 1973 citations checked against primary sources and are accurate as given.
- R. Bird, "Using circular programs to eliminate multiple traversals of data," 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.
7. Related
- Reversible Pipeline Transforms – reversible computation, from the other side
- Lambda Calculus Implementation in Scheme – the lazy self-reference in miniature
- Scheme: Notes and Examples – call/cc and the rest of Scheme