Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Refuting the strong Church-Turing thesis: The interactive nature of computing

Dina Goldin, Peter W. Wegner

Published Jan 1, 2008• 5 citations
OpenAlex

Related papers

Quantum Computers: the Church-Turing Hypothesis Versus the Turing Principle

Christopher G. Timpson

Springer eBooks•Jan 1, 2004•12 citations

Computing Beyond the Church-Turing Limit

Robert Jones

Bulletin of the American Physical Society•May 2, 2009•0 citations

Algorithmic Information Content, Church — Turing Thesis, Physical Entropy, and Maxwell’s Demon

Wojciech Hubert Zurek

NATO ASI series. Series B : Physics•Jan 1, 1991•40 citations

The Church-Turing-Deutsch Principle in Quantum Computation.

P. Prashant

FCS•Jan 1, 2006•0 citations

Quantum computation: From Church-Turing thesis to Qubits

Shankhadip Kundu, Rajdeep Kundu, Shubhabrata Kundu +4 more

In the paper we interpret the Church Turing thesis of Computation Algorithm and how it differs from the strong Church Turing thesis in the field of computation. Church Turing thesis can be classified as Strong Church Turing thesis and Normal Church Turing thesis. Church Turing hypothesis says “that a computing problem can be solved in any computer if and only if it can be solved on a very simple ‘machine’, named TURING MACHINE”. We introspect the difference in the model of computers that are developed on these two competitive algorithms. We will also be studying the physical realization of bits in a quantum computer with special mention to the commercial quantum computer systems offered at the moment. Our objective is to find out the relation of a quantum bit and the Strong Church Turing Thesis converging the gap between theoretical model and physical structure.

IEEE Annual Ubiquitous Computing, Electronics & Mobile Communication Conference (UEMCON)•Oct 1, 2016•8 citations

Limits of Computation and Physical Reality

Apostolos Syropoulos

The physical laws of the universe dictate what can and what cannot be computed. The Church-Turing Thesis (CTT) is based on the assumption that the Turing machine is the ultimate computing device and according to the CTT something is computable only if it can be computed by a Turing machine. However, the CTT has not been proved and it can be definitely proved in a universe with specific properties. Whether our universe is such a universe is an open problem as it is an open problem whether the universe behaves like a machine. A broader approach that rejects the CTT and shows that the mechanistic universe and the CTT are incompatible is proposed and discussed thoroughly.

WORLD SCIENTIFIC eBooks•Feb 1, 2020•0 citations
In the paper we interpret the Church Turing thesis of Computation Algorithm and how it differs from the strong Church Turing thesis in the field of computation. Church Turing thesis can be classified as Strong Church Turing thesis and Normal Church Turing thesis. Church Turing hypothesis says “that a computing problem can be solved in any computer if and only if it can be solved on a very simple ‘machine’, named TURING MACHINE”. We introspect the difference in the model of computers that are developed on these two competitive algorithms. We will also be studying the physical realization of bits in a quantum computer with special mention to the commercial quantum computer systems offered at the moment. Our objective is to find out the relation of a quantum bit and the Strong Church Turing Thesis converging the gap between theoretical model and physical structure.
The physical laws of the universe dictate what can and what cannot be computed. The Church-Turing Thesis (CTT) is based on the assumption that the Turing machine is the ultimate computing device and according to the CTT something is computable only if it can be computed by a Turing machine. However, the CTT has not been proved and it can be definitely proved in a universe with specific properties. Whether our universe is such a universe is an open problem as it is an open problem whether the universe behaves like a machine. A broader approach that rejects the CTT and shows that the mechanistic universe and the CTT are incompatible is proposed and discussed thoroughly.