Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR14-044 | 2nd April 2014 18:43

Additively efficient universal computers


Authors: Daniel Dewey
Publication: 4th April 2014 12:34
Downloads: 1110


We give evidence for a stronger version of the extended Church-Turing thesis: among the set of physically possible computers, there are computers that can simulate any other realizable computer with only additive constant overhead in space, time, and other natural resources. Complexity-theoretic results that hold for these computers can therefore be assumed to hold up to constant overhead on any other realizable computer. To support this claim, we offer an informal argument originally due to Deutsch, a formalization of that argument into a theorem showing sufficient conditions for the existence of additively efficient universal computers in arbitrary settings, and arguments that these sufficient conditions hold on physical resources including time and space. We also provide a formal setting in which we can prove that additively efficient universal computers exist.

ISSN 1433-8092 | Imprint