Journal articles: 'Church-Turing thesis'

1

Copeland, B. Jack, and Oron Shagrir. "The Church-Turing thesis." Communications of the ACM 62, no. 1 (December 19, 2018): 66–74. http://dx.doi.org/10.1145/3198448.

Full text

APA, Harvard, Vancouver, ISO, and other styles

2

Piccinini, Gualtiero. "Computationalism, The Church–Turing Thesis, and the Church–Turing Fallacy." Synthese 154, no. 1 (January 2007): 97–120. http://dx.doi.org/10.1007/s11229-005-0194-z.

Full text

APA, Harvard, Vancouver, ISO, and other styles

3

BEGGS, EDWIN, JOSÉ FÉLIX COSTA, DIOGO POÇAS, and JOHN V. TUCKER. "AN ANALOGUE-DIGITAL CHURCH-TURING THESIS." International Journal of Foundations of Computer Science 25, no. 04 (June 2014): 373–89. http://dx.doi.org/10.1142/s0129054114400012.

Full text

Abstract:

We argue that dynamical systems involving discrete and continuous data can be modelled by Turing machines with oracles that are physical processes. Using the theory introduced in Beggs et al. [2,3], we consider the scope and limits of polynomial time computations by such systems. We propose a general polynomial time Church-Turing Thesis for feasible computations by analogue-digital systems, having the non-uniform complexity class BPP//log* as theoretical upper bound. We show why BPP//log* should be replace P/poly, which was proposed by Siegelmann for neural nets [23,24]. Then we examine whether other sources of hypercomputation can be found in analogue-digital systems besides the oracle itself. We prove that the higher polytime limit P/poly can be attained via non-computable analogue-digital interface protocols.

APA, Harvard, Vancouver, ISO, and other styles

4

Cleland, Carol E. "Is the Church-Turing thesis true?" Minds and Machines 3, no. 3 (August 1993): 283–312. http://dx.doi.org/10.1007/bf00976283.

Full text

APA, Harvard, Vancouver, ISO, and other styles

5

Cotogno, Paolo. "Hypercomputation and the Physical Church‐Turing Thesis." British Journal for the Philosophy of Science 54, no. 2 (June 1, 2003): 181–223. http://dx.doi.org/10.1093/bjps/54.2.181.

Full text

APA, Harvard, Vancouver, ISO, and other styles

6

Yao, Andrew Chi-Chih. "Classical physics and the Church--Turing Thesis." Journal of the ACM 50, no. 1 (January 2003): 100–105. http://dx.doi.org/10.1145/602382.602411.

Full text

APA, Harvard, Vancouver, ISO, and other styles

7

Sprevak, Mark D. "Kripke’s paradox and the Church–Turing thesis." Synthese 160, no. 2 (November 11, 2006): 285–95. http://dx.doi.org/10.1007/s11229-006-9120-2.

Full text

APA, Harvard, Vancouver, ISO, and other styles

8

Mikkilineni, Rao. "Going beyond Church–Turing Thesis Boundaries: Digital Genes, Digital Neurons and the Future of AI." Proceedings 47, no. 1 (May 11, 2020): 15. http://dx.doi.org/10.3390/proceedings2020047015.

Full text

Abstract:

The Church–Turing thesis deals with computing functions that are described by a list of formal, mathematical rules or sequences of event-driven actions such as modeling, simulation, business workflows, etc. All algorithms that are Turing computable fall within the boundaries of the Church–Turing thesis. There are two paths to pushing the boundaries. The first is to address the limitation in the clause “ignoring resource limitations”. The second is to search for computing models that solve problems that no ordinary Turing machine can solve using superrecursive algorithms. We argue that “structural machines” provide a new solution to managing both without disrupting the computation itself.

APA, Harvard, Vancouver, ISO, and other styles

9

Mikkilineni, Rao. "Going beyond Church–Turing Thesis Boundaries: Digital Genes, Digital Neurons and the Future of AI." Proceedings 47, no. 1 (May 11, 2020): 15. http://dx.doi.org/10.3390/proceedings47010015.

Full text

Abstract:

The Church–Turing thesis deals with computing functions that are described by a list of formal, mathematical rules or sequences of event-driven actions such as modeling, simulation, business workflows, etc. All algorithms that are Turing computable fall within the boundaries of the Church–Turing thesis. There are two paths to pushing the boundaries. The first is to address the limitation in the clause “ignoring resource limitations”. The second is to search for computing models that solve problems that no ordinary Turing machine can solve using superrecursive algorithms. We argue that “structural machines” provide a new solution to managing both without disrupting the computation itself.

APA, Harvard, Vancouver, ISO, and other styles

10

Piccinini, Gualtiero. "The Physical Church–Turing Thesis: Modest or Bold?" British Journal for the Philosophy of Science 62, no. 4 (December 1, 2011): 733–69. http://dx.doi.org/10.1093/bjps/axr016.

Full text

APA, Harvard, Vancouver, ISO, and other styles

11

Ben-Amram, Amir M. "The Church-Turing thesis and its look-alikes." ACM SIGACT News 36, no. 3 (September 2005): 113–14. http://dx.doi.org/10.1145/1086649.1086651.

Full text

APA, Harvard, Vancouver, ISO, and other styles

12

Horsten, Leon, and Herman Roelants. "The Church-Turing thesis and effective mundane procedures." Minds and Machines 5, no. 1 (February 1995): 1–8. http://dx.doi.org/10.1007/bf00974186.

Full text

APA, Harvard, Vancouver, ISO, and other styles

13

ARRIGHI, PABLO, and GILLES DOWEK. "THE PHYSICAL CHURCH-TURING THESIS AND THE PRINCIPLES OF QUANTUM THEORY." International Journal of Foundations of Computer Science 23, no. 05 (August 2012): 1131–45. http://dx.doi.org/10.1142/s0129054112500153.

Full text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

14

PORTER, CHRISTOPHER P. "ON ANALOGUES OF THE CHURCH–TURING THESIS IN ALGORITHMIC RANDOMNESS." Review of Symbolic Logic 9, no. 3 (July 14, 2016): 456–79. http://dx.doi.org/10.1017/s1755020316000113.

Full text

Abstract:

AbstractIn this article, I consider the status of several statements analogous to the Church–Turing thesis that assert that some definition of algorithmic randomness captures the intuitive conception of randomness. I argue that we should not only reject the theses that have appeared in the algorithmic randomness literature, but more generally that we ought not evaluate the adequacy of a definition of randomness on the basis of whether it captures the so-called intuitive conception of randomness to begin with. Instead, I argue that a more promising alternative is to evaluate the adequacy of a definition of randomness on the basis of whether it captures what I refer to as a “notion of almost everywhere typicality.” In support of my main claims, I will appeal to recent work in showing the connection between of algorithmic randomness and certain “almost everywhere” theorems from classical mathematics.

APA, Harvard, Vancouver, ISO, and other styles

15

Button, Tim. "SAD Computers and Two Versions of the Church–Turing Thesis." British Journal for the Philosophy of Science 60, no. 4 (December 1, 2009): 765–92. http://dx.doi.org/10.1093/bjps/axp038.

Full text

APA, Harvard, Vancouver, ISO, and other styles

16

Calude, Cristian S., Elena Calude, and Karl Svozil. "The complexity of proving chaoticity and the Church–Turing thesis." Chaos: An Interdisciplinary Journal of Nonlinear Science 20, no. 3 (September 2010): 037103. http://dx.doi.org/10.1063/1.3489096.

Full text

APA, Harvard, Vancouver, ISO, and other styles

17

Urbaniak, R. "How Not To Use the Church-Turing Thesis Against Platonism." Philosophia Mathematica 19, no. 1 (January 31, 2011): 74–89. http://dx.doi.org/10.1093/philmat/nkr001.

Full text

APA, Harvard, Vancouver, ISO, and other styles

18

Taylor, R. Gregory. "Motivating the Church-Turing thesis in the twenty-first century." ACM SIGCSE Bulletin 30, no. 3 (September 1998): 228–31. http://dx.doi.org/10.1145/290320.283551.

Full text

APA, Harvard, Vancouver, ISO, and other styles

19

Galton, Antony. "The Church–Turing thesis: Still valid after all these years?" Applied Mathematics and Computation 178, no. 1 (July 2006): 93–102. http://dx.doi.org/10.1016/j.amc.2005.09.086.

Full text

APA, Harvard, Vancouver, ISO, and other styles

20

Goldin, Dina, and Peter Wegner. "The Interactive Nature of Computing: Refuting the Strong Church–Turing Thesis." Minds and Machines 18, no. 1 (January 1, 2008): 17–38. http://dx.doi.org/10.1007/s11023-007-9083-1.

Full text

APA, Harvard, Vancouver, ISO, and other styles

21

Dershowitz, Nachum, and Evgenia Falkovich. "A Formalization and Proof of the Extended Church-Turing Thesis -Extended Abstract-." Electronic Proceedings in Theoretical Computer Science 88 (July 30, 2012): 72–78. http://dx.doi.org/10.4204/eptcs.88.6.

Full text

APA, Harvard, Vancouver, ISO, and other styles

22

Weng, Juyang. "Autonomous Programming for General Purposes: Theory." International Journal of Humanoid Robotics 17, no. 04 (August 2020): 2050016. http://dx.doi.org/10.1142/s0219843620500164.

Full text

Abstract:

The universal Turing Machine (TM) is a model for Von Neumann computers — general-purpose computers. A human brain, linked with its biological body, can inside-skull-autonomously learn a universal TM so that he acts as a general-purpose computer and writes a computer program for any practical purposes. It is unknown whether a robot can accomplish the same. This theoretical work shows how the Developmental Network (DN), linked with its robot body, can accomplish this. Unlike a traditional TM, the TM learned by DN is a super TM — Grounded, Emergent, Natural, Incremental, Skulled, Attentive, Motivated, and Abstractive (GENISAMA). A DN is free of any central controller (e.g., Master Map, convolution, or error back-propagation). Its learning from a teacher TM is one transition observation at a time, immediate, and error-free until all its neurons have been initialized by early observed teacher transitions. From that point on, the DN is no longer error-free but is always optimal at every time instance in the sense of maximal likelihood, conditioned on its limited computational resources and the learning experience. This paper extends the Church–Turing thesis to a stronger version — a GENISAMA TM is capable of Autonomous Programming for General Purposes (APFGP) — and proves both the Church–Turing thesis and its stronger version.

APA, Harvard, Vancouver, ISO, and other styles

23

Dowek, Gilles. "The physical Church–Turing thesis and non-deterministic computation over the real numbers." Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences 370, no. 1971 (July 28, 2012): 3349–58. http://dx.doi.org/10.1098/rsta.2011.0322.

Full text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

24

BEGGS, EDWIN, JOSÉ FÉLIX COSTA, and JOHN V. TUCKER. "THREE FORMS OF PHYSICAL MEASUREMENT AND THEIR COMPUTABILITY." Review of Symbolic Logic 7, no. 4 (September 9, 2014): 618–46. http://dx.doi.org/10.1017/s1755020314000240.

Full text

Abstract:

AbstractWe have begun a theory of measurement in which an experimenter and his or her experimental procedure are modeled by algorithms that interact with physical equipment through a simple abstract interface. The theory is based upon using models of physical equipment as oracles to Turing machines. This allows us to investigate the computability and computational complexity of measurement processes. We examine eight different experiments that make measurements and, by introducing the idea of an observable indicator, we identify three distinct forms of measurement process and three types of measurement algorithm. We give axiomatic specifications of three forms of interfaces that enable the three types of experiment to be used as oracles to Turing machines, and lemmas that help certify an experiment satisfies the axiomatic specifications. For experiments that satisfy our axiomatic specifications, we give lower bounds on the computational power of Turing machines in polynomial time using nonuniform complexity classes. These lower bounds break the barrier defined by the Church-Turing Thesis.

APA, Harvard, Vancouver, ISO, and other styles

25

WEIHRAUCH, KLAUS, and NING ZHONG. "IS WAVE PROPAGATION COMPUTABLE OR CAN WAVE COMPUTERS BEAT THE TURING MACHINE?" Proceedings of the London Mathematical Society 85, no. 2 (July 23, 2002): 312–32. http://dx.doi.org/10.1112/s0024611502013643.

Full text

Abstract:

According to the Church-Turing Thesis a number function is computable by the mathematically defined Turing machine if and only if it is computable by a physical machine. In 1983 Pour-El and Richards defined a three-dimensional wave $u(t,x)$ such that the amplitude $u(0,x)$ at time 0 is computable and the amplitude $u(1,x)$ at time 1 is continuous but not computable. Therefore, there might be some kind of wave computer beating the Turing machine. By applying the framework of Type 2 Theory of Effectivity (TTE), in this paper we analyze computability of wave propagation. In particular, we prove that the wave propagator is computable on continuously differentiable waves, where one derivative is lost, and on waves from Sobolev spaces. Finally, we explain why the Pour-El-Richards result probably does not help to design a wave computer which beats the Turing machine.2000 Mathematical Subject Classification: 03D80, 03F60, 35L05, 68Q05.

APA, Harvard, Vancouver, ISO, and other styles

26

ALVES, TIAGO DE CASTRO. "TOWARDS AN EVALUATION OF THE NORMALISATION THESIS ON IDENTITY OF PROOFS: THE CASE OF CHURCH-TURING THESIS AS TOUCHSTONE." Manuscrito 43, no. 3 (September 2020): 114–63. http://dx.doi.org/10.1590/0100-6045.2020.v43n3.ta.

Full text

APA, Harvard, Vancouver, ISO, and other styles

27

Pégny, Maël. "How to Make a Meaningful Comparison of Models: The Church–Turing Thesis Over the Reals." Minds and Machines 26, no. 4 (November 19, 2016): 359–88. http://dx.doi.org/10.1007/s11023-016-9407-0.

Full text

APA, Harvard, Vancouver, ISO, and other styles

28

YUE, HOUGUANG. "FROM COMPUTING TO INTERACTION: ON THE EXPRESSIVENESS OF ASYNCHRONOUS PI-CALCULUS." International Journal of Foundations of Computer Science 24, no. 03 (April 2013): 349–73. http://dx.doi.org/10.1142/s0129054113500081.

Full text

Abstract:

In line with the framework of Theory of Interaction proposed by Yuxi Fu, we formalize the asynchronous theory in model independent way. Borrowing the idea from Church-Turing Thesis, we introduce ℂ-calculus as a minimal interaction model. We give model independent characterization for asynchronous bisimulation equivalence which is generalized to subbisimilarity used as the criteria for Interaction Completeness of interaction models. We present an encoding from ℂ-calculus to asynchronous π-calculus and prove that it satisfies the subbisimilarity statements.

APA, Harvard, Vancouver, ISO, and other styles

29

Sieg, Wilfried. "Step by Recursive Step: Church's Analysis of Effective Calculability." Bulletin of Symbolic Logic 3, no. 2 (June 1997): 154–80. http://dx.doi.org/10.2307/421012.

Full text

Abstract:

AbstractAlonzo Church's mathematical work on computability and undecidability is well-known indeed, and we seem to have an excellent understanding of the context in which it arose. The approach Church took to the underlying conceptual issues, by contrast, is less well understood. Why, for example, was “Church's Thesis” put forward publicly only in April 1935, when it had been formulated already in February/March 1934? Why did Church choose to formulate it then in terms of Gödel's general recursiveness, not his own λ-definability as he had done in 1934? A number of letters were exchanged between Church and Paul Bernays during the period from December 1934 to August 1937; they throw light on critical developments in Princeton during that period and reveal novel aspects of Church's distinctive contribution to the analysis of the informal notion of effective calculability. In particular, they allow me to give informed, though still tentative answers to the questions I raised; the character of my answers is reflected by an alternative title for this paper, Why Church needed Gödel's recursiveness for his Thesis. In Section 5, I contrast Church's analysis with that of Alan Turing and explore, in the very last section, an analogy with Dedekind's investigation of continuity.

APA, Harvard, Vancouver, ISO, and other styles

30

Argaman, Nathan. "Quantum Computation and Arrows of Time." Entropy 23, no. 1 (December 30, 2020): 49. http://dx.doi.org/10.3390/e23010049.

Full text

Abstract:

Quantum physics is surprising in many ways. One surprise is the threat to locality implied by Bell’s Theorem. Another surprise is the capacity of quantum computation, which poses a threat to the complexity-theoretic Church-Turing thesis. In both cases, the surprise may be due to taking for granted a strict arrow-of-time assumption whose applicability may be limited to the classical domain. This possibility has been noted repeatedly in the context of Bell’s Theorem. The argument concerning quantum computation is described here. Further development of models which violate this strong arrow-of-time assumption, replacing it by a weaker arrow which is yet to be identified, is called for.

APA, Harvard, Vancouver, ISO, and other styles

31

Quinon, Paula. "Implicit and Explicit Examples of the Phenomenon of Deviant Encodings." Studies in Logic, Grammar and Rhetoric 63, no. 1 (September 1, 2020): 53–67. http://dx.doi.org/10.2478/slgr-2020-0027.

Full text

Abstract:

AbstractThe core of the problem discussed in this paper is the following: the Church-Turing Thesis states that Turing Machines formally explicate the intuitive concept of computability. The description of Turing Machines requires description of the notation used for the input and for the output. Providing a general definition of notations acceptable in the process of computations causes problems. This is because a notation, or an encoding suitable for a computation, has to be computable. Yet, using the concept of computation, in a definition of a notation, which will be further used in a definition of the concept of computation yields an obvious vicious circle. The circularity of this definition causes trouble in distinguishing on the theoretical level, what is an acceptable notation from what is not an acceptable notation, or as it is usually referred to in the literature, “deviant encodings”.Deviant encodings appear explicitly in discussions about what is an adequate or correct conceptual analysis of the concept of computation. In this paper, I focus on philosophical examples where the phenomenon appears implicitly, in a “disguised” version. In particular, I present its use in the analysis of the concept of natural number. I also point at additional phenomena related to deviant encodings: conceptual fixed points and apparent “computability” of uncomputable functions. In parallel, I develop the idea that Carnapian explications provide a much more adequate framework for understanding the concept of computation, than the classical philosophical analysis.

APA, Harvard, Vancouver, ISO, and other styles

32

Copeland, Jack. "The Church-Turing Thesis." NeuroQuantology 2, no. 2 (September 5, 2007). http://dx.doi.org/10.14704/nq.2004.2.2.40.

Full text

APA, Harvard, Vancouver, ISO, and other styles

33

D'Abramo, Germano. "WITHDRAWN: On the Church-Turing Thesis." Chaos, Solitons & Fractals, October 2007. http://dx.doi.org/10.1016/j.chaos.2007.08.048.

Full text

APA, Harvard, Vancouver, ISO, and other styles

34

"Where does AlphaGo go: from church-turing thesis to AlphaGo thesis and beyond." IEEE/CAA Journal of Automatica Sinica 3, no. 2 (April 2016): 113–20. http://dx.doi.org/10.1109/jas.2016.7471613.

Full text

APA, Harvard, Vancouver, ISO, and other styles

35

Braverman, Mark, Jonathan Schneider, and Cristóbal Rojas. "Space-Bounded Church-Turing Thesis and Computational Tractability of Closed Systems." Physical Review Letters 115, no. 9 (August 27, 2015). http://dx.doi.org/10.1103/physrevlett.115.098701.

Full text

APA, Harvard, Vancouver, ISO, and other styles

36

De Benedetto, Matteo. "Explication as a Three-Step Procedure: the case of the Church-Turing Thesis." European Journal for Philosophy of Science 11, no. 1 (January 6, 2021). http://dx.doi.org/10.1007/s13194-020-00337-2.

Full text

Abstract:

AbstractIn recent years two different axiomatic characterizations of the intuitive concept of effective calculability have been proposed, one by Sieg and the other by Dershowitz and Gurevich. Analyzing them from the perspective of Carnapian explication, I argue that these two characterizations explicate the intuitive notion of effective calculability in two different ways. I will trace back these two ways to Turing’s and Kolmogorov’s informal analyses of the intuitive notion of calculability and to their respective outputs: the notion of computorability and the notion of algorithmability. I will then argue that, in order to adequately capture the conceptual differences between these two notions, the classical two-step picture of explication is not enough. I will present a more fine-grained three-step version of Carnapian explication, showing how with its help the difference between these two notions can be better understood and explained.

APA, Harvard, Vancouver, ISO, and other styles

37

Yoshida, Beni. "Remarks on black hole complexity puzzle." Journal of High Energy Physics 2020, no. 10 (October 2020). http://dx.doi.org/10.1007/jhep10(2020)103.

Full text

Abstract:

Abstract Recently a certain conceptual puzzle in the AdS/CFT correspondence, concerning the growth of quantum circuit complexity and the wormhole volume, has been identified by Bouland-Fefferman-Vazirani and Susskind. In this note, we propose a resolution of the puzzle and save the quantum Extended Church-Turing thesis by arguing that there is no computational shortcut in measuring the volume due to gravitational backreaction from bulk observers. A certain strengthening of the firewall puzzle from the computational complexity perspective, as well as its potential resolution, is also presented.

APA, Harvard, Vancouver, ISO, and other styles

38

Castro-Manzano, José Martín. "Inteligencia Artificial, la vía negativa y el estatus computacional de la persona. Artificial Intelligence, the Negative Way and the Computational Status of Persons." Metafísica y persona, no. 13 (May 26, 2017). http://dx.doi.org/10.24310/metyper.2015.v0i13.2718.

Full text

Abstract:

Una de las preguntas más interesantes que la inteligencia artificial y la filosofía de la computación han hecho nacer es la pregunta por nuestro estatus computacional como personas humanas. En este trabajo discutimos dicho estatus mostrando la argumentación por vía negativa de Bringsjord para justificar que somos entidades computacionales sui generis. Para discutir el estatus computacional revisamos el concepto de “inteligencia artificial” y su relación con la Tesis de Church-Turing. Posteriormente comentamos la discusión Lucas vs Bringsjord para concluir por qué se dice que somos hipermáquinas.One of the most interesting questions that artificial intelligence and philosophy of computing have generated is the question about the computational status of human persons. In this paper we discuss the computational status of human persons by showing Bringsjord’s negative way argumentation in order to justify that we are sui generis computational entities. As a means to discuss the computational status we review the concept of “artificial intelligence” and its relation with the Church-Turing Thesis. Then we comment on the Lucas vs Bringsjord discussion for the purpose of concluding why it is said that we are hypermachines.

APA, Harvard, Vancouver, ISO, and other styles

39

Liu, Junyu, and Yuan Xin. "Quantum simulation of quantum field theories as quantum chemistry." Journal of High Energy Physics 2020, no. 12 (December 2020). http://dx.doi.org/10.1007/jhep12(2020)011.

Full text

Abstract:

Abstract Conformal truncation is a powerful numerical method for solving generic strongly-coupled quantum field theories based on purely field-theoretic technics without introducing lattice regularization. We discuss possible speedups for performing those computations using quantum devices, with the help of near-term and future quantum algorithms. We show that this construction is very similar to quantum simulation problems appearing in quantum chemistry (which are widely investigated in quantum information science), and the renormalization group theory provides a field theory interpretation of conformal truncation simulation. Taking two-dimensional Quantum Chromodynamics (QCD) as an example, we give various explicit calculations of variational and digital quantum simulations in the level of theories, classical trials, or quantum simulators from IBM, including adiabatic state preparation, variational quantum eigensolver, imaginary time evolution, and quantum Lanczos algorithm. Our work shows that quantum computation could not only help us understand fundamental physics in the lattice approximation, but also simulate quantum field theory methods directly, which are widely used in particle and nuclear physics, sharpening the statement of the quantum Church-Turing Thesis.

APA, Harvard, Vancouver, ISO, and other styles

Journal articles on the topic 'Church-Turing thesis'

Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles