The Experts below are selected from a list of 300 Experts worldwide ranked by ideXlab platform
Gilles Dowek - One of the best experts on this subject based on the ideXlab platform.
-
the physical church Turing Thesis and non deterministic computation over the real numbers
Philosophical Transactions of the Royal Society A, 2012Co-Authors: Gilles DowekAbstract:On the real numbers, the notions of a semi-decidable relation and that of an effectively enumerable relation differ. The second only seems to be adequate to express, in an algorithmic way, non-deterministic physical theories, where magnitudes are represented by real numbers.
-
around the physical church Turing Thesis cellular automata formal languages and the principles of quantum theory
Language and Automata Theory and Applications, 2012Co-Authors: Gilles DowekAbstract:The physical Church-Turing Thesis explains the Galileo Thesis, but also suggests an evolution of the language used to describe nature. It can be proved from more basic principle of physics, but it also questions these principles, putting the emphasis on the principle of a bounded density of information. This principle itself questions our formulation of quantum theory, in particular the choice of a field for the scalars and the origin of the infinite dimension of the vector spaces used as state spaces.
-
The Physical Church-Turing Thesis and the Principles of Quantum Theory
International Journal of Foundations of Computer Science, 2012Co-Authors: Pablo Arrighi, Gilles DowekAbstract:As was emphasized by Deutsch, quantum computation shatters complexity theory, but is innocuous to computability theory. Yet Nielsen and others have shown how quantum theory as it stands could breach the physical Church-Turing Thesis. We draw a clear line as to when this is the case, in a way that is inspired by Gandy. Gandy formulates postulates about physics, such as homogeneity of space and time, bounded density and velocity of information -- and proves that the physical Church-Turing Thesis is a consequence of these postulates. We provide a quantum version of the theorem. Thus this approach exhibits a formal non-trivial interplay between theoretical physics symmetries and computability assumptions.
-
The physical Church-Turing Thesis and the principles of quantum theory
2011Co-Authors: Pablo Arrighi, Gilles DowekAbstract:Notoriously, quantum computation shatters complexity theory, but is innocuous to computability theory. Yet several works have shown how quantum theory as it stands could breach the physical Church-Turing Thesis. We draw a clear line as to when this is the case, in a way that is inspired by Gandy. Gandy formulates postulates about physics, such as homogeneity of space and time, bounded density and velocity of information --- and proves that the physical Church-Turing Thesis is a consequence of these postulates. We provide a quantum version of the theorem. Thus this approach exhibits a formal non-trivial interplay between theoretical physics symmetries and computability assumptions.
Valery S. Shchesnovich - One of the best experts on this subject based on the ideXlab platform.
-
Sufficient condition for the mode mismatch of single photons for scalability of the boson-sampling computer
Physical Review A, 2014Co-Authors: Valery S. ShchesnovichAbstract:The boson sampler proposed by Aaronson and Arkhipov is a nonuniversal quantum computer, which can serve as evidence against the extended Church-Turing Thesis. It samples the probability distribution at the output of a linear unitary optical network with indistinguishable single photons at the input. Four experimental groups have already tested their small-scale prototypes with up to four photons. A boson sampler with a few dozens of single photons is believed to be hard to simulate on a classical computer. For scalability of a realistic boson sampler with current technology it is necessary to know the effect of the photon mode mismatch on its operation. Here a nondeterministic model of the boson sampler is analyzed, which employs partially indistinguishable single photons emitted by identical sources. A sufficient condition on the average mutual fidelity $\ensuremath{\langle}\mathcal{F}\ensuremath{\rangle}$ of the single photons is found, which guarantees that the realistic boson sampler outperforms the classical computer. Moreover, the boson-sampler computer with partially indistinguishable single photons is scalable and has more power than classical computers when the single-photon mode mismatch $1\ensuremath{-}\ensuremath{\langle}\mathcal{F}\ensuremath{\rangle}$ scales as $O({N}^{\ensuremath{-}3/2})$ with the total number of photons $N$.
Oron Shagrir - One of the best experts on this subject based on the ideXlab platform.
-
the church Turing Thesis logical limit or breachable barrier
Communications of The ACM, 2018Co-Authors: Jack B Copeland, Oron ShagrirAbstract:In its original form, the Church-Turing Thesis concerned computation as Alan Turing and Alonzo Church used the term in 1936---human computation.
-
computability Turing gdel church and beyond
2013Co-Authors: Jack B Copeland, Carl J Posy, Oron ShagrirAbstract:In the 1930s a series of seminal works published by Alan Turing, Kurt Gdel, Alonzo Church, and others established the theoretical basis for computability. This work, advancing precise characterizations of effective, algorithmic computability, was the culmination of intensive investigations into the foundations of mathematics. In the decades since, the theory of computability has moved to the center of discussions in philosophy, computer science, and cognitive science. In this volume, distinguished computer scientists, mathematicians, logicians, and philosophers consider the conceptual foundations of computability in light of our modern understanding. Some chapters focus on the pioneering work by Turing, Gdel, and Church, including the Church-Turing Thesis and Gdel's response to Church's and Turing's proposals. Other chapters cover more recent technical developments, including computability over the reals, Gdel's influence on mathematical logic and on recursion theory and the impact of work by Turing and Emil Post on our theoretical understanding of online and interactive computing; and others relate computability and complexity to issues in the philosophy of mind, the philosophy of science, and the philosophy of mathematics. Contributors:Scott Aaronson, Dorit Aharonov, B. Jack Copeland, Martin Davis, Solomon Feferman, Saul Kripke, Carl J. Posy, Hilary Putnam, Oron Shagrir, Stewart Shapiro, Wilfried Sieg, Robert I. Soare, Umesh V. Vazirani
-
the church Turing Thesis as a special corollary of godel s completeness theorem
2013Co-Authors: Jack B Copeland, Carl J Posy, Oron ShagrirAbstract:This chapter contains sections titled: 4.1 The Previously Received View and More Recent Challenges, 4.2 Computation as a Special Form of Mathematical Argument, 4.3 Von Neumann's Problem of Characterizing and Proving Unsolvability and Godel's Theorem IX, 4.4 Some Clarificatory Remarks on the Present Characterization, 4.5 Conclusion, Notes, References
-
physical hypercomputation and the church Turing Thesis
Minds and Machines, 2003Co-Authors: Oron Shagrir, Itamar PitowskyAbstract:We describe a possible physical device that computes a function that cannot be computed by a Turing machine. The device is physical in the sense that it is compatible with General Relativity. We discuss some objections, focusing on those which deny that the device is either a computer or computes a function that is not Turing computable. Finally, we argue that the existence of the device does not refute the Church–Turing Thesis, but nevertheless may be a counterexample to Gandy's Thesis.
Jack B Copeland - One of the best experts on this subject based on the ideXlab platform.
-
the church Turing Thesis logical limit or breachable barrier
Communications of The ACM, 2018Co-Authors: Jack B Copeland, Oron ShagrirAbstract:In its original form, the Church-Turing Thesis concerned computation as Alan Turing and Alonzo Church used the term in 1936---human computation.
-
computability Turing gdel church and beyond
2013Co-Authors: Jack B Copeland, Carl J Posy, Oron ShagrirAbstract:In the 1930s a series of seminal works published by Alan Turing, Kurt Gdel, Alonzo Church, and others established the theoretical basis for computability. This work, advancing precise characterizations of effective, algorithmic computability, was the culmination of intensive investigations into the foundations of mathematics. In the decades since, the theory of computability has moved to the center of discussions in philosophy, computer science, and cognitive science. In this volume, distinguished computer scientists, mathematicians, logicians, and philosophers consider the conceptual foundations of computability in light of our modern understanding. Some chapters focus on the pioneering work by Turing, Gdel, and Church, including the Church-Turing Thesis and Gdel's response to Church's and Turing's proposals. Other chapters cover more recent technical developments, including computability over the reals, Gdel's influence on mathematical logic and on recursion theory and the impact of work by Turing and Emil Post on our theoretical understanding of online and interactive computing; and others relate computability and complexity to issues in the philosophy of mind, the philosophy of science, and the philosophy of mathematics. Contributors:Scott Aaronson, Dorit Aharonov, B. Jack Copeland, Martin Davis, Solomon Feferman, Saul Kripke, Carl J. Posy, Hilary Putnam, Oron Shagrir, Stewart Shapiro, Wilfried Sieg, Robert I. Soare, Umesh V. Vazirani
-
the church Turing Thesis as a special corollary of godel s completeness theorem
2013Co-Authors: Jack B Copeland, Carl J Posy, Oron ShagrirAbstract:This chapter contains sections titled: 4.1 The Previously Received View and More Recent Challenges, 4.2 Computation as a Special Form of Mathematical Argument, 4.3 Von Neumann's Problem of Characterizing and Proving Unsolvability and Godel's Theorem IX, 4.4 Some Clarificatory Remarks on the Present Characterization, 4.5 Conclusion, Notes, References
-
the church Turing Thesis
Neuroquantology, 2007Co-Authors: Jack B CopelandAbstract:There are various equivalent formulations of the Church-Turing Thesis. A common one is that every effective computation can be carried out by a Turing machine. The Church-Turing Thesis is often misunderstood, particularly in recent writing in the philosophy of mind.
Gualtiero Piccinini - One of the best experts on this subject based on the ideXlab platform.
-
the physical church Turing Thesis modest or bold
The British Journal for the Philosophy of Science, 2011Co-Authors: Gualtiero PiccininiAbstract:AbstractThis article defends a modest version of the Physical Church-Turing Thesis (CT). Following an established recent trend, I distinguish between what I call Mathematical CT—the Thesis supporte...
-
computationalism the church Turing Thesis and the church Turing fallacy
Synthese, 2007Co-Authors: Gualtiero PiccininiAbstract:The Church–Turing Thesis (CTT) is often employed in arguments for computationalism. I scrutinize the most prominent of such arguments in light of recent work on CTT and argue that they are unsound. Although CTT does nothing to support computationalism, it is not irrelevant to it. By eliminating misunderstandings about the relationship between CTT and computationalism, we deepen our appreciation of computationalism as an empirical hypoThesis.
