Skip to main content

Finite Expected Runtime Does Not Compose

A generator starts with a counter of one, doubles it on every flip of a fair coin, and returns it after the first heads. A countdown decrements its input to zero. Each program has finite expected runtime for every fixed input. Running the countdown on the generator's output has infinite expected runtime [Kaminski et al. 2016].

The counter is unbounded, and we count one tick per flip or decrement. With @ert and post 0, the specifications bound the expected tick count.

The Two Programs​

The Generator​

Caesar verifies that the generator takes at most two coin flips on average.

Generator Runtime Upper Bound
Expected: Verified
@ert
coproc generator() -> (stake: UInt)
pre 2
post 0
{
stake = 1
var more: Bool = true
@invariant(2 * [more])
while more {
tick 1
more = flip(0.5)
stake = 2 * stake
}
}

The Countdown​

The countdown takes one tick for each unit of its input, and Caesar verifies the upper bound.

Countdown Runtime Upper Bound
Expected: Verified
@ert
coproc countdown(init_stake: UInt) -> (stake: UInt)
pre init_stake
post 0
{
stake = init_stake
@invariant(stake)
while stake > 0 {
tick 1
stake = stake - 1
}
}

Their Composition​

Caesar verifies that every natural number is a lower bound on the expected runtime of the composed program. The expected runtime is therefore infinite.

Arbitrary Lower Bound on Expected Runtime
Expected: Verified
@ert
proc composition(target: UInt) -> (stake: UInt)
pre target
post 0
{
stake = 1
var more: Bool = true
@omega_invariant(n, ite(more, stake * (n ⊓ target), stake))
while more {
tick 1
more = flip(0.5)
stake = 2 * stake
}
@omega_invariant(n, n ⊓ stake)
while stake > 0 {
tick 1
stake = stake - 1
}
}

Stopping on flip kk has probability 2−k2^{-k} and leaves 2k2^k decrements, so each possible stopping time contributes 2−k⋅2k=12^{-k} \cdot 2^k = 1 tick to the expected countdown cost. The generator's omega invariant adds these contributions, and the countdown's supplies the cost when the generator stops. The target appears only in the proof, so every bound applies to the same program.

The composition terminates almost surely because the first heads arrives with probability one and every resulting countdown is finite.

References​