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 --

impossible-decision-tree.png

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.