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

Text
Whyman_RAJ_Mathematics_PhD_2018.pdf  Final eThesis  complete (pdf) Available under License Creative Commons AttributionNoncommercialShare 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, type2 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 firstorder logic is equal to the class Turing machine computable problems. Whereas the class infinite problems that are computable by a finite firstorder theory machine is equal to the class type2 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 firstorder theory machine in polynomial resources is equal to $NP \cap coNP$. Since there are problems which appear to lie in $NP \cap coNP \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/noncausal component to the apparent speedup offered by quantum computers.
Item Type:  Thesis (PhD) 

Related URLs:  
Keywords:  Computability theory, complexity theory, quantum computation, physical computation, superTuring computation, atemporal computation, noncausal computation, computable analysis, infinite time Turing machines, firstorder logic, and secondorder 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.