Beyond Blum: What is a Resource?

Journal article

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.

Authors: Blakey, E

• Publication status: Published
• Peer review status: Peer reviewed
• Publisher: Old City Publishing Inc.
• Journal: International Journal of Unconventional Computing
• Volume: 6
• Issue: 3-4
• Pages: 223-238
• Publication date: 2010-01-01
• Edition: Author's Original
• EISSN: 1548-7202
• ISSN: 1548-7199
• Language: English
• Keywords: resource; computational complexity; non-Turing/non-standard computer; dominance; normalization; Blum's axioms
• Subjects: Computer science (mathematics)