Apples and oranges Comparing unconventional computersReportar como inadecuado

Apples and oranges Comparing unconventional computers - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

Reference: Ed Blakey, (2010). Apples & oranges? Comparing unconventional computers. International Journal of Computers, 4 (4), 185-192.Citable link to this page:


Apples & oranges? Comparing unconventional computers

Abstract: Complexity theorists routinely compare—via the pre-ordering induced by asymptotic notation—the efficiency of computers so as to ascertain which offers the most efficient solution to a given problem. Tacit in this statement, however, is that the computers conform to a standard computational model: that is, they are Turing machines, random-access machines or similar. However, whereas meaningful comparison between these conventional computers is well understood and correctly practised, that of non-standard machines (such as quantum, chemical and optical computers) is rarely even attempted and, where it is, is often attempted under the typically false assumption that the conventional-computing approach to comparison is adequate in the unconventional-computing case. We discuss in the present paper a computational-model-independent approach to the comparison of computers' complexity (and define the corresponding complexity classes). Notably, the approach allows meaningful comparison between an unconventional computer and an existing, digital-computer benchmark that solves the same problem.

Publication status:PublishedPeer Review status:Peer reviewedVersion:Publisher's version

Bibliographic Details

Publisher: North Atlantic University Union (NAUN)

Publisher Website:

Host: International Journal of Computerssee more from them

Publication Website:

Issue Date: 2010

Copyright Date: 2010


Eissn: 1998-4308

Urn: uuid:440697b7-5b35-4504-b76a-092a729cd572 Item Description

Type: Article: post-print;

Language: en

Version: Publisher's versionKeywords: computational complexity computational resource dominance theoretical computer science unconventional computationSubjects: Computer science (mathematics) Tiny URL: ora:4935


Autor: Ed Blakey - institutionUniversity of Oxford facultyMathematical, Physical and Life Science



Documentos relacionados