Abstract
dc:description.abstractIn this thesis we shall present and develop the concept of a theory machine. Theory machines describe computation via logical systems, providing an overarching formalism for characterising computational systems such as Turing machines, type-2 machines, quantum computers, infinite time Turing machines, and various physical computation devices. Notably we prove that the class of finite problems that are computable by a finite theory machine acting in first-order logic is equal to the class Turing machine computable problems. Whereas the class infinite problems that are computable by a finite first-order theory machine is equal to the class type-2 machine computable problems. A key property of a theory machine computation is that it does not have to occur in a causally ordered manner. A consequence of this fact is that the class of problems that are computable by finite first-order theory machine in polynomial resources is equal to $NP \cap co-NP$. Since there are problems which appear to lie in $NP \cap co-NP \setminus P$ that are efficiently solvable by a quantum computer (such as the factorisation problem), this gives weight to the argument that there is an atemporal/non-causal component to the apparent speed-up offered by quantum computers.
Degree
thesis:*- Name dc:type.qualificationname
- Ph.D
- Level dc:type.qualificationlevel
- doctoral
- Grantor dc:publisher.institution
- University of Leeds
- Year dc:date.issued
- 2018
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Whyman, Richard Arthur James
- Advisor dc:contributor.advisor
-
- Kisil, Vladimir Vladimirovich
- ORCID person:identifier.orcid
Rights
- Language dc:language.dcterms_iso639_2
- eng
Identifiers
dc:identifier.*- Identifier
- uk.bl.ethos.762514