Beyond Blum: What is a Resource?
Ed Blakey
When analysing a Turing machine’s complexity, we can appeal to decades of experience to determine which resources (typically time steps or tape cells) to measure. More fundamentally, we have Blum’s criteria for admission as a valid resource.
When analysing a non-Turing computer’s complexity, the situation is less clear. What resources are relevant for, say, an analogue computer? Can we meaningfully compare a Turing machine’s time complexity with an optical computer’s precision complexity? Crucially, what should we admit as a resource in the context of non-standard computation?
Our aim is to specify a suitable, non-Turing-computer (in fact, not necessarily-Turing-computer) analogue of Blum’s axioms. We start with the existing axioms, but show that, alone, they are insufficient. Accordingly, we further restrict the notion of resource: we define normality of resource, advocating consideration only of normal resources during non-standard computers’ complexity analyses. This eliminates some ‘deceptive’ complexity behaviour encountered with Blum’s axioms alone.
Keywords: Computational complexity; non-Turing/non-standard computer; resource; Blum’s axioms; normalization; dominance.