Church–Turing thesis  

From The Art and Popular Culture Encyclopedia

(Difference between revisions)
Jump to: navigation, search
Revision as of 07:09, 7 June 2016
Jahsonic (Talk | contribs)

← Previous diff
Current revision
Jahsonic (Talk | contribs)

Line 15: Line 15:
*[[Oracle (computer science)]] *[[Oracle (computer science)]]
*[[Super-recursive algorithm]] *[[Super-recursive algorithm]]
- 
-== Footnotes == 
-{{reflist|2}} 
- 
-==References== 
-*Barwise, Jon, H. J. Keisler, and K. Kunen, Editors, 1980, The Kleene Symposium, 426 pages, North-Holland Publishing Company, Amsterdam, ISBN 0-444-85345-6 
-*{{cite journal|last=Ben-Amram|first=A.M.|year=2005|title=The Church-Turing Thesis and its Look-Alikes 
-|journal=[[SIGACT News]]|volume=36|issue=3|pages=113–116|doi=10.1145/1086649.1086651}} 
-*{{cite journal|last=Bernstein|first=E|author2=Vazirani, U.|year=1997|title=Quantum complexity theory|journal=[[SIAM Journal on Computing]]|volume=26|issue=5|pages=1411–1473|doi=10.1137/S0097539796300921}} 
-*{{cite journal|last=Blass|first=Andreas|authorlink=Andreas Blass|author2=[[Yuri Gurevich]] |year=2003|title=Algorithms: A Quest for Absolute Definitions|journal=Bulletin of European Association for Theoretical Computer Science|issue=81|url=http://research.microsoft.com/~gurevich/Opera/164.pdf}} 
-*{{cite book|last=Burgin|first=Mark|title=Monographs in computer science|publisher=Springer|year=2005|chapter=Super-recursive algorithms|isbn=0-387-95569-0}} 
-*{{cite journal|last=Church|first=Alonzo|year=1932|title=A set of Postulates for the Foundation of Logic|journal=Annals of Mathematics|issue=2|volume=33|pages=346–366| jstor=1968337|doi=10.2307/1968337}} 
-*{{cite journal|last=Church|first=Alonzo|year=1936|title=An Unsolvable Problem of Elementary Number Theory|journal=American Journal of Mathematics|issue=58|pages=345–363|jstor=2371045|volume=58|doi=10.2307/2371045}} 
-*{{cite journal|last=Church|first=Alonzo|year=1936|title=A Note on the Entscheidungsproblem|journal=Journal of Symbolic Logic|issue=1|pages=40–41|doi=10.2307/2269326 }} 
-*{{cite journal|last=Church|first=Alonzo|year=1937|title=Review: A. M. Turing, On Computable Numbers, with an Application to the Entscheidungsproblem|journal=Journal of Symbolic Logic|issue=2|pages=42–43|doi=10.2307/2268810 }} 
-*{{cite book|last=Church|first=Alonzo|title=The Calculi of Lambda-Conversion|publisher=Princeton University Press|location=Princeton|year=1941}} 
-*{{cite book|last=Cooper|first=S. B.|author2=Odifreddi, P.|title=Computability and Models: Perspectives East and West|editor=S. B. Cooper & S. S. Goncharov|publisher=Kluwer Academic/Plenum Publishers|year=2003|pages=137–160|chapter=Incomputability in Nature}} 
-*{{cite book|title=The Undecidable, Basic Papers on Undecidable Propositions, Unsolvable Problems And Computable Functions|editor=[[Martin Davis|Davis, Martin]]|publisher=Raven Press|location=New York|year=1965}} Includes original papers by Gödel, Church, Turing, Rosser, Kleene, and Post mentioned in this section. 
-*{{cite journal|author=Eberbach, E.|author2=Wegner, P.|date=October 2003|title=Beyond Turing Machines|journal=Bulletin of the European Association for Theoretical Computer Science|issue=81|pages=279–304}} 
-* {{cite book|last=Gabbay|first=D.M.|year=2001|title=Handbook of Philosophical Logic|edition=2nd|volume=1}} 
-*{{cite book|last=Gandy|first=Robin|title=The Kleene Symposium|editor=H.J. Barwise, H.J. Keisler, and K. Kunen|publisher=North-Holland Publishing Company|year=1980|pages=123–148|chapter=Church's Thesis and the Principles for Mechanisms|authorlink=Robin Gandy}} 
-*{{cite book|last=Gandy|first=Robin|title=The universal Turing Machine: A Half-Century Survey|editor=[[Rolf Herken]]|publisher=Wien Springer–Verlag|location=New York|date=1994–5|pages=51ff|isbn=3-211-82637-8}} 
-*{{cite book|last=Gödel|first=Kurt|others=Kleene and Rosser (lecture note-takers); Institute for Advanced Study (lecture sponsor)|title=The Undecidable|editor=Davis, M.|publisher=Raven Press|location=New York|year=1965|chapter=On Undecidable Propositions of Formal Mathematical Systems|origyear=1934}} 
-*{{cite journal|first=Kurt|last=Gödel|title=On The Length of Proofs|year=1936|journal=Ergenbnisse eines mathematishen Kolloquiums|publisher=Heft|issue=7|pages=23–24|language=German}} Cited by Kleene (1952) as "Über die Lāange von Beweisen", in ''Ergebnisse eines math. Koll'', etc. 
-*{{cite journal|last=Gurevich|first=Yuri|date=June 1988|title=On Kolmogorov Machines and Related Issues|journal=Bulletin of European Association for Theoretical Computer Science|issue=35|pages=71–82|authorlink=Yuri Gurevich}} 
-*{{cite journal|last=Gurevich|first=Yuri|date=July 2000|title=Sequential Abstract State Machines Capture Sequential Algorithms|journal=ACM Transactions on Computational Logic|volume=1|issue=1|pages=77–111|url=http://research.microsoft.com/~gurevich/Opera/141.pdf|doi=10.1145/343369.343384}} 
-*{{cite journal|last=Herbrand|first=Jacques|year=1932|title=Sur la non-contradiction de l'arithmétique|journal=Journal fur die reine und angewandte Mathematik|issue=166|pages=1–8|authorlink=Jacques Herbrand}} 
-*{{cite book|last=Hofstadter|first=Douglas R.|title=[[Gödel, Escher, Bach: an Eternal Golden Braid]]|chapter=Chapter XVII: Church, Turing, Tarski, and Others|authorlink=Douglas Hofstadter}} 
-*{{cite journal|last=Kleene|first=Stephen Cole|year=1935|title=A Theory of Positive Integers in Formal Logic|journal=American Journal of Mathematics|issue=57|pages=153–173 & 219–244|authorlink=Stephen Cole Kleene|jstor=2372027|volume=57|doi=10.2307/2372027}} 
-*{{cite journal|last=Kleene|first=Stephen Cole|year=1936|title=Lambda-Definability and Recursiveness|journal=Duke Mathematical Journal|issue=2|pages=340–353|doi=10.1215/s0012-7094-36-00227-2 }} 
-*{{cite journal|last=Kleene|first=Stephen Cole|title= Recursive Predicates and Quantifiers|journal=American Mathematical Society Transactions|volume= 54| issue = 1 |pages=41–73|year=1943 |doi= 10.2307/1990131|jstor=1990131|publisher=Transactions of the American Mathematical Society, Vol. 53, No. 1}} Reprinted in ''The Undecidable'', p. 255ff. Kleene refined his definition of "general recursion" and proceeded in his chapter "12. Algorithmic theories" to posit "Thesis I" (p. 274); he would later repeat this thesis (in Kleene 1952:300) and name it "Church's Thesis" (Kleene 1952:317) (i.e., the [[Church thesis]]). 
-*{{cite book|last=Kleene|first=Stephen Cole|title=Introduction to Metamathematics|publisher=North-Holland|year=1952|oclc=523942}} 
-*{{cite book|last=Knuth|first=Donald|title=The Art of Computer Programming|publisher=Addison–Wesley|year=1973|edition=2nd|volume=1/Fundamental Algorithms|authorlink=Donald Knuth}} 
-*{{cite journal|last=Kugel|first=Peter|date=November 2005|title=Communications of the ACM|journal=It's time to think outside the computational box|volume=48|issue=11}} 
-*{{cite book|author=Lewis, H.R.|authorlink=Harry R. Lewis|author2=Papadimitriou, C.H. |authorlink2=Christos H. Papadimitriou |title=Elements of the Theory of Computation|publisher=Prentice-Hall|location=Upper Saddle River, NJ, USA|year=1998}} 
-*{{cite book|last=Manna|first=Zohar|title=Mathematical Theory of Computation|location=Dover|year=1974|isbn=978-0-486-43238-0|origyear=2003|authorlink=Zohar Manna}} 
-*{{cite journal|last=Markov|first=A.A.|year=1960|title=The Theory of Algorithms|journal=American Mathematical Society Translations|volume=2|issue=15|pages=1–14|origyear=1954|authorlink=Andrey Markov, Jr.}} 
-* {{cite book|last=Olszewski|first=Adam|year=2006|title=Church's Thesis After 70 Years}} 
-*{{cite book|author=Pour-El, M.B.|author2=Richards, J.I.|title=Computability in Analysis and Physics|publisher=[[Springer Verlag]]|year=1989}} 
-*{{cite journal|last=Rosser|first=J. B.|year=1939|title=An Informal Exposition of Proofs of Godel's Theorem and Church's Theorem|journal=The Journal of Symbolic Logic|volume=4|pages=53–60|authorlink=J. B. Rosser|doi=10.2307/2269059|jstor=2269059|issue=2|publisher=The Journal of Symbolic Logic, Vol. 4, No. 2}} 
-*Sieg, Wilfried, Richard Sommer, and Carolyn Talcott (eds.), 2002, Reflections on the Foundations of Mathematics: Essays in Honor of Solomon Feferman, Lecture Notes in Logic 15, 444 pages, A K Peters, Ltd., ISBN 1-56881-169-1 
-*{{cite journal|last=Soare|first=Robert|year=1996|title=Computability and Recursion|journal=Bulletin of Symbolic Logic|issue=2|pages=284–321|authorlink=Robert Soare}} 
-*{{cite journal|last=Syropoulos|first=Apostolos|year=2008|title=Hypercomputation: Computing Beyond the Church–Turing Barrier|publisher=Springer|isbn=978-0-387-30886-9}} 
-* {{Citation | last= Turing | first= A. M. | author-link = Alan Turing |year = 1937 | title = On Computable Numbers, with an Application to the Entscheidungsproblem | origyear = Delivered to the Society November 1936 | periodical = Proceedings of the London Mathematical Society | series = 2 | volume = 42 | pages = 230–65 | doi= 10.1112/plms/s2-42.1.230 | url = http://www.comlab.ox.ac.uk/activities/ieg/e-library/sources/tp2-ie.pdf | ref= harv}} and {{Cite news| last = Turing | first = A.M. | publication-date = 1937 | title = On Computable Numbers, with an Application to the Entscheidungsproblem: A correction | periodical = Proceedings of the London Mathematical Society | series = 2 | volume = 43 | pages = 544–6 | doi = 10.1112/plms/s2-43.6.544 | year = 1938 }} (See also: Davis 1965:115ff) 
- 
-==External links== 
-*{{cite SEP |url-id=church-turing |title=The Church–Turing Thesis |last=Copeland |first=B. Jack |author-link=Jack Copeland }}. 
-* [http://plato.stanford.edu/entries/computation-physicalsystems/ Computation in Physical Systems] —a comprehensive philosophical treatment of relevant issues 
-* [https://egtheory.wordpress.com/2014/09/11/transcendental-idealism-and-posts-variant-of-the-church-turing-thesis/ Transcendental idealism and Post’s variant of the Church-Turing thesis] —EGTheory blog 
-* {{cite arxiv|last1=Schmidhuber|first1=Juergen|title=A Computer Scientist's View of Life, the Universe, and Everything|arxiv=quant-ph/9904050|date=13 April 1999}} 
- 
-{{Mathematical logic}} 
-{{Metalogic}} 
- 
-{{DEFAULTSORT:Church-Turing Thesis}} 
-[[Category:Computability theory]] 
-[[Category:Alan Turing]] 
-[[Category:Theory of computation]] 
-[[Category:Philosophy of computer science]] 
- 
-[[lt:Tiuringo mašina#Tiuringo tezė]] 
- 
{{GFDL}} {{GFDL}}

Current revision

Related e

Wikipedia
Wiktionary
Shop


Featured:

In computability theory, the Church–Turing thesis (also known as the Turing–Church thesis, the Church–Turing conjecture, Church's thesis, Church's conjecture, and Turing's thesis) is a hypothesis about the nature of computable functions. It states that a function on the natural numbers is computable by a human being following an algorithm, ignoring resource limitations, if and only if it is computable by a Turing machine. The thesis is named after American mathematician Alonzo Church and the British mathematician Alan Turing. Before the precise definition of computable function, mathematicians often used the informal term effectively calculable to describe functions that are computable by paper-and-pencil methods.

See also




Unless indicated otherwise, the text in this article is either based on Wikipedia article "Church–Turing thesis" or another language Wikipedia page thereof used under the terms of the GNU Free Documentation License; or on research by Jahsonic and friends. See Art and Popular Culture's copyright notice.

Personal tools