Back to search

University of Leeds

Characterising Computational Devices with Logical Systems

Abstract

dc:description.abstract

In 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

Chain of custody

source
Harvested from
White Rose University Consortium
Base URL
etheses.whiterose.ac.uk/cgi/oai2
Last updated
2026-11-18
Source record
OAI-PMH GetRecord
related terms
citation

Whyman, Richard Arthur James. Characterising Computational Devices with Logical Systems. doctoral thesis, University of Leeds, 2018.