White Rose University Consortium logo
University of Leeds logo University of Sheffield logo York University logo

Characterising Computational Devices with Logical Systems

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

[img]
Preview
Text
Whyman_RAJ_Mathematics_PhD_2018.pdf - Final eThesis - complete (pdf)
Available under License Creative Commons Attribution-Noncommercial-Share Alike 2.0 UK: England & Wales.

Download (16Mb) | Preview

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.

Item Type: Thesis (PhD)
Related URLs:
Keywords: Computability theory, complexity theory, quantum computation, physical computation, super-Turing computation, atemporal computation, non-causal computation, computable analysis, infinite time Turing machines, first-order logic, and second-order logic
Academic Units: The University of Leeds > Faculty of Maths and Physical Sciences (Leeds) > School of Mathematics (Leeds) > Pure Mathematics (Leeds)
Depositing User: Mr Richard Whyman
Date Deposited: 19 Dec 2018 11:38
Last Modified: 19 Dec 2018 11:38
URI: http://etheses.whiterose.ac.uk/id/eprint/22378

You do not need to contact us to get a copy of this thesis. Please use the 'Download' link(s) above to get a copy.
You can contact us about this thesis. If you need to make a general enquiry, please see the Contact us page.

Actions (repository staff only: login required)