A Note on the Theorems of Church‐Turing and Trachtenbrot

Mathematical Logic Quarterly 40 (3):422-424 (1994)
  Copy   BIBTEX

Abstract

We sketch proofs of the theorems of Church-Turing and Trachtenbrot using a semi-monomorphic axiomatization

Categories

Keywords

Reprint years

DOI

10.1002/malq.19940400311

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 91,475

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

My notes

Similar books and articles

The Church-Turing ‘Thesis’ as a Special Corollary of Gödel’s Completeness Theorem.Saul A. Kripke - 2013 - In B. J. Copeland, C. Posy & O. Shagrir (eds.), Computability: Gödel, Turing, Church, and beyond. MIT Press.
Dilemmas of Ambiguity and Vagueness.Leon Felkins - 1996
Godel's theorem, church's theorem, and mechanism.J. J. C. Smart - 1961 - Synthese 13 (1):105-10.
The Church-Turing Thesis.B. Jack Copeland - 2014 - In Edward N. Zalta (ed.), The Stanford Encyclopedia of Philosophy. Stanford, CA: The Metaphysics Research Lab.
SAD computers and two versions of the Church–Turing thesis.Tim Button - 2009 - British Journal for the Philosophy of Science 60 (4):765-792.
Analogy and diagonal argument.Zbigniew Tworak - 2006 - Logic and Logical Philosophy 15 (1):39-66.
What Turing did after he invented the universal Turing machine.Diane Proudfoot & Jack Copeland - 2000 - Journal of Logic, Language and Information 9:491-509.
A natural axiomatization of computability and proof of Church’s thesis.Nachum Dershowitz & Yuri Gurevich - 2008 - Bulletin of Symbolic Logic 14 (3):299-350.
Physical hypercomputation and the church–turing thesis.Oron Shagrir & Itamar Pitowsky - 2003 - Minds and Machines 13 (1):87-101.
Turing's golden: How well Turing's work stands today.Justin Leiber - 2006 - Philosophical Psychology 19 (1):13-46.
A formal theorem in church's theory of types.M. H. A. Newman & A. M. Turing - 1942 - Journal of Symbolic Logic 7 (1):28-33.
Thinking machines: Some fundamental confusions. [REVIEW]John T. Kearns - 1997 - Minds and Machines 7 (2):269-87.

Analytics

Added to PP
2013-12-01

Downloads
44 (#357,900)

6 months
3 (#974,323)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

No citations found.

Add more citations

References found in this work

No references found.

Add more references