Quantifying resource use in computations

It is currently not possible to quantify the resources needed to perform
a computation. As a consequence, it is not possible to reliably evaluate
the hardware resources needed for the application of algorithms or the
running of programs. This is apparent in both computer science, for in-
stance, in cryptanalysis, and in neuroscience, for instance, comparative
neuro-anatomy. A System versus Environment game formalism is pro-
posed based on Computability Logic that allows to define a computational
work function that describes the theoretical and physical resources needed
to perform any purely algorithmic computation. Within this formalism,
the cost of a computation is defined as the sum of information storage over
the steps of the computation. The size of the computational device, eg,
the action table of a Universal Turing Machine, the number of transistors
in silicon, or the number and complexity of synapses in a neural net, is
explicitly included in the computational cost. The proposed cost function
leads in a natural way to known computational trade-offs and can be used
to estimate the computational capacity of real silicon hardware and neural
nets. The theory is applied to a historical case of 56 bit DES key recovery,
as an example of application to cryptanalysis. Furthermore, the relative
computational capacities of human brain neurons and the C. elegans ner-
vous system are estimated as an example of application to neural nets.
keywords: computation, compatibility logic, neural nets, cryptanalysis