Revisiting the Cobham-Edmonds Thesis: A Quantum Perspective

(Philosophy of Science, English)

he theory of computation is a very dynamically evolving field within theoretical computer science. Nowadays, the most widely accepted approach to computability is the one introduced in the form of the Church-Turing thesis. This approach identifies the class of effectively computable functions as equivalent to the class of functions computable by a Turing machine. The fact is, however, that the original thesis justifies only one of its implications (→): that every effectively computable function is computable by some Turing machine. The second implication (←) is quite obviously doomed to fail if we want to adopt computability in any practical sense. Such considerations have finally led to the emergence of the concept of feasible computability. Just like the notion of 'effective' computability from the Church-Turing thesis, the concept of 'feasibility' also seems to be a more intuitive than mathematical one. Over the years various researchers have proposed different approaches to define feasibility, embodying different philosophical and formal intuitions. Today, it is common to use the definition proposed by the Cobham-Edmonds thesis and identify the class of feasible functions with the class containing functions computable in polynomial time (P, PTIME).

Birth of the idea of applying extraordinary quantum effects to speed-up computational process dates back to Feynman and Deutsch. It began to gain even more interest after the quantum factorization algorithm introduced by Shor in 1994, giving a glimpse of the real quantum speed-up one can achieve, compared to all known classical algorithms. Quantum computing has, without doubt, broadened our understanding of the nature of computing and our cognitive limitations. Recent advances made in the field of computation and complexity theory have soon lead to the - in some sense anticipated - question which quantum algorithms can be regarded as ''practical''.

Presented results allow us to formulate a conjecture that the problem of feasibility in theory of computation should today be discussed within the broader context of quantum computing. In the light of conducted discussions, we draw a conclusion, that to attack the problem of feasibility it may not be sufficient just to simply ''translate'' Cobham's and Edmonds' ideas into the quantum world and one has to take into account problems specific for operating on quantum matter.

Chair: Aleksandra Gomułczak

Time: 16:00-16:30, 14 September 2018 (Friday)

Location: SR 1.005

Agnieszka Proszewska

(Jagiellonian University, Polska)

Agnieszka Proszewska is a PhD candidate and teaching assistant in the Faculty of Philosophy at the Jagiellonian University in Cracow, where she teaches logic and set theory, computation theory and philosophy of science. She received a MA in Philosophy and a MA in Swedish Philology from Jagiellonian University and is currently working on her Master's thesis in theoretical computer science at the Faculty of Physics, Astronomy and Applied Computer Science. Her research interests focus on the philosophy of natural sciences, structural frameworks, mathematical logic and theories of complexity and computation.

© 2019 SOPhiA. All rights reserved.
Last update: 2014-04-01.