The Church-Turing Thesis: Breaking the Myth Export

@article{citeulike:915177, abstract = {According to the interactive view of computation, communication happens during the computation, not before or after it. This approach, distinct from concurrency theory and the theory of computation, represents a paradigm shift that changes our understanding of what is computation and how it is modeled. Interaction machines extend Turing machines with interaction to capture the behavior of concurrent systems, promising to bridge these two fields. This promise is hindered by the widespread belief, incorrectly known as the Church-Turing thesis, that no model of computation more expressive than Turing machines can exist. Yet Turing's original thesis only refers to the computation of functions and explicitly excludes other computational paradigms such as interaction. In this paper, we identify and analyze the historical reasons for this widespread belief. Only by accepting that it is false can we begin to properly investigate formal models of interaction machines. We conclude the paper by presenting one such model, Persistent Turing Machines (PTMs). PTMs capture sequential interaction, which is a limited form of concurrency; they allow us to formulate the Sequential Interaction Thesis, going beyond the expressiveness of Turing machines and of the Church-Turing thesis.}, author = {Goldin, Dina and Wegner, Peter}, citeulike-article-id = {915177}, citeulike-linkout-0 = {http://dx.doi.org/10.1007/11494645_20}, citeulike-linkout-1 = {http://www.springerlink.com/content/prut3chrhdckem3y}, doi = {10.1007/11494645_20}, journal = {New Computational Paradigms}, keywords = {indirect, indirect-interaction}, pages = {152--168}, posted-at = {2008-06-08 04:59:05}, priority = {3}, publisher = {Springer}, title = {The Church-Turing Thesis: Breaking the Myth}, url = {http://dx.doi.org/10.1007/11494645_20}, year = {2005} }

TY - JOUR ID - citeulike:915177 L3 - citeulike-article-id:915177 N2 - According to the interactive view of computation, communication happens during the computation, not before or after it. This approach, distinct from concurrency theory and the theory of computation, represents a paradigm shift that changes our understanding of what is computation and how it is modeled. Interaction machines extend Turing machines with interaction to capture the behavior of concurrent systems, promising to bridge these two fields. This promise is hindered by the widespread belief, incorrectly known as the Church-Turing thesis, that no model of computation more expressive than Turing machines can exist. Yet Turing’s original thesis only refers to the computation of functions and explicitly excludes other computational paradigms such as interaction. In this paper, we identify and analyze the historical reasons for this widespread belief. Only by accepting that it is false can we begin to properly investigate formal models of interaction machines. We conclude the paper by presenting one such model, Persistent Turing Machines (PTMs). PTMs capture sequential interaction, which is a limited form of concurrency; they allow us to formulate the Sequential Interaction Thesis, going beyond the expressiveness of Turing machines and of the Church-Turing thesis. JF - New Computational Paradigms EP - 168 TI - The Church-Turing Thesis: Breaking the Myth PB - Springer SP - 152 KW - indirect KW - indirect-interaction AU - Goldin, Dina AU - Wegner, Peter PY - 2005/// UR - http://dx.doi.org/10.1007/11494645_20 ER -