For any constructible function , there exists a function
such that for all functions
, the following two statements are equivalent:
1. There exists an algorithm such that for all inputs
,
computes
in volume
.
2.
is constructible and
.
Here, the volume is the combined number of active edges during all steps,
which is the number of state-changes needed to run a certain Turing
machine on a particular input.