Publications
LOWER BOUND
What no machine, however fast, will ever get around.
What is LOWER BOUND?
In computer science, a lower bound is a cost that no method can beat, however clever. Sorting n items by comparing them takes about n log₂ n comparisons, whatever the algorithm. Erasing a bit releases at least kT ln 2 of heat, whatever the machine. And some questions have no algorithm that answers them in every case: whether an arbitrary program will ever stop, for instance.
LOWER BOUND is the series in which the laboratory investigates these limits. Each file starts from an established fact, follows it until something gives way, and ends on an open question. Every claim comes with its source.
Why here? Because LOWER BOUND applies our method to the science of computation: find the limit, reduce each idea to its shortest form, and look for what could prove us wrong.
Ref. Knuth, 1973; Landauer, 1961; Turing, 1936
