19
views
0
recommends
+1 Recommend
0 collections
    0
    shares
      • Record: found
      • Abstract: found
      • Article: not found

      A Natural Axiomatization of Computability and Proof of Church's Thesis

      ,
      Bulletin of Symbolic Logic
      Association for Symbolic Logic

      Read this article at

      ScienceOpenPublisher
      Bookmark
          There is no author summary for this article yet. Authors can add summaries to their articles on ScienceOpen to make them more accessible to a non-specialist audience.

          Abstract

          Church's Thesis asserts that the only numeric functions that can be calculated by effective means are the recursive ones, which are the same, extensionally, as the Turing-computable numeric functions. The Abstract State Machine Theorem states that every classical algorithm is behaviorally equivalent to an abstract state machine. This theorem presupposes three natural postulates about algorithmic computation. Here, we show that augmenting those postulates with an additional requirement regarding basic operations gives a natural axiomatization of computability and a proof of Church's Thesis, as Gödel and others suggested may be possible. In a similar way, but with a different set of basic operations, one can prove Turing's Thesis, characterizing the effective string functions, and—in particular—the effectively-computable functions on string representations of numbers.

          Related collections

          Most cited references35

          • Record: found
          • Abstract: not found
          • Article: not found

          An Unsolvable Problem of Elementary Number Theory

            Bookmark
            • Record: found
            • Abstract: not found
            • Article: not found

            Formal Reductions of the General Combinatorial Decision Problem

              Bookmark
              • Record: found
              • Abstract: not found
              • Article: not found

              A note on the Entscheidungsproblem

                Bookmark

                Author and article information

                Journal
                applab
                Bulletin of Symbolic Logic
                Bull. symb. log.
                Association for Symbolic Logic
                1079-8986
                1943-5894
                September 2008
                January 2014
                : 14
                : 03
                : 299-350
                Article
                10.2178/bsl/1231081370
                5518dbfd-33d8-4ff0-8d6f-72f5ccb4462f
                © 2008
                History

                Comments

                Comment on this article