Matches in DBpedia 2015-10 for { <http://dbpedia.org/resource/Church–Turing_thesis> ?p ?o }
- Church–Turing_thesis abstract "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 ("thesis") about the nature of computable functions. In simple terms, the Church–Turing thesis states that a function on the natural numbers is computable in an informal sense (i.e., computable by a human being using a pencil-and-paper method, 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. In the 1930s, several independent attempts were made to formalize the notion of computability: In 1933, Austrian-American mathematician Kurt Gödel, with Jacques Herbrand, created a formal definition of a class called general recursive functions. The class of general recursive functions is the smallest class of functions (possibly with more than one argument) which includes all constant functions, projections, the successor function, and which is closed under function composition and recursion. In 1936, Alonzo Church created a method for defining functions called the λ-calculus. Within λ-calculus, he defined an encoding of the natural numbers called the Church numerals. A function on the natural numbers is called λ-computable if the corresponding function on the Church numerals can be represented by a term of the λ-calculus. Also in 1936, before learning of Church's work, Alan Turing created a theoretical model for machines, now called Turing machines, that could carry out calculations from inputs by manipulating symbols on a tape. Given a suitable encoding of the natural numbers as sequences of symbols, a function on the natural numbers is called Turing computable if some Turing machine computes the corresponding function on encoded natural numbers.Church and Turing proved that these three formally defined classes of computable functions coincide: a function is λ-computable if and only if it is Turing computable if and only if it is general recursive. This has led mathematicians and computer scientists to believe that the concept of computability is accurately characterized by these three equivalent processes. Other formal attempts to characterize computability have subsequently strengthened this belief (see below).On the other hand, the Church–Turing thesis states that the above three formally-defined classes of computable functions coincide with the informal notion of an effectively calculable function. Since, as an informal notion, the concept of effective calculability does not have a formal definition, the thesis, although it has near-universal acceptance, cannot be formally proven.Since its inception, variations on the original thesis have arisen, including statements about what can physically be realized by a computer in our universe (Physical Church-Turing Thesis) and what can be efficiently computed (Complexity-Theoretic Church–Turing Thesis). These variations are not due to Church or Turing, but arise from later work in complexity theory and digital physics. The thesis also has implications for the philosophy of mind.".
- Church–Turing_thesis wikiPageExternalLink 164.pdf.
- Church–Turing_thesis wikiPageExternalLink computation-physicalsystems.
- Church–Turing_thesis wikiPageExternalLink tp2-ie.pdf.
- Church–Turing_thesis wikiPageExternalLink transcendental-idealism-and-posts-variant-of-the-church-turing-thesis.
- Church–Turing_thesis wikiPageID "6854".
- Church–Turing_thesis wikiPageLength "47747".
- Church–Turing_thesis wikiPageOutDegree "132".
- Church–Turing_thesis wikiPageRevisionID "680405549".
- Church–Turing_thesis wikiPageWikiLink ACM_SIGACT.
- Church–Turing_thesis wikiPageWikiLink Abstract_machine.
- Church–Turing_thesis wikiPageWikiLink Alan_Turing.
- Church–Turing_thesis wikiPageWikiLink Alonzo_Church.
- Church–Turing_thesis wikiPageWikiLink BPP_(complexity).
- Church–Turing_thesis wikiPageWikiLink BQP.
- Church–Turing_thesis wikiPageWikiLink Bounded-error_probabilistic_polynomial.
- Church–Turing_thesis wikiPageWikiLink Busy_Beaver.
- Church–Turing_thesis wikiPageWikiLink Busy_beaver.
- Church–Turing_thesis wikiPageWikiLink Category:Alan_Turing.
- Church–Turing_thesis wikiPageWikiLink Category:Computability_theory.
- Church–Turing_thesis wikiPageWikiLink Category:Philosophy_of_computer_science.
- Church–Turing_thesis wikiPageWikiLink Category:Theory_of_computation.
- Church–Turing_thesis wikiPageWikiLink Cellular_automata.
- Church–Turing_thesis wikiPageWikiLink Cellular_automaton.
- Church–Turing_thesis wikiPageWikiLink Church_encoding.
- Church–Turing_thesis wikiPageWikiLink Church_numerals.
- Church–Turing_thesis wikiPageWikiLink Church_thesis.
- Church–Turing_thesis wikiPageWikiLink Churchs_thesis_(constructive_mathematics).
- Church–Turing_thesis wikiPageWikiLink Church–Turing_thesis.
- Church–Turing_thesis wikiPageWikiLink Church–Turing–Deutsch_principle.
- Church–Turing_thesis wikiPageWikiLink Combinatory_logic.
- Church–Turing_thesis wikiPageWikiLink Complexity_theory.
- Church–Turing_thesis wikiPageWikiLink Computability.
- Church–Turing_thesis wikiPageWikiLink Computability_logic.
- Church–Turing_thesis wikiPageWikiLink Computability_theory.
- Church–Turing_thesis wikiPageWikiLink Computability_theory_(computation).
- Church–Turing_thesis wikiPageWikiLink Computable_function.
- Church–Turing_thesis wikiPageWikiLink Computable_number.
- Church–Turing_thesis wikiPageWikiLink Computational_complexity_theory.
- Church–Turing_thesis wikiPageWikiLink Computer.
- Church–Turing_thesis wikiPageWikiLink Constant_function.
- Church–Turing_thesis wikiPageWikiLink Constructive_mathematics.
- Church–Turing_thesis wikiPageWikiLink Constructivism_(mathematics).
- Church–Turing_thesis wikiPageWikiLink Continuous_function.
- Church–Turing_thesis wikiPageWikiLink Conways_Game_of_Life.
- Church–Turing_thesis wikiPageWikiLink Conways_game_of_life.
- Church–Turing_thesis wikiPageWikiLink Counter_machine.
- Church–Turing_thesis wikiPageWikiLink David_Hilbert.
- Church–Turing_thesis wikiPageWikiLink Decidability_(logic).
- Church–Turing_thesis wikiPageWikiLink Digital_physics.
- Church–Turing_thesis wikiPageWikiLink Effective_method.
- Church–Turing_thesis wikiPageWikiLink Effectively_calculable.
- Church–Turing_thesis wikiPageWikiLink Emil_Leon_Post.
- Church–Turing_thesis wikiPageWikiLink Emil_Post.
- Church–Turing_thesis wikiPageWikiLink Entscheidungsproblem.
- Church–Turing_thesis wikiPageWikiLink Formal_system.
- Church–Turing_thesis wikiPageWikiLink Function_(mathematics).
- Church–Turing_thesis wikiPageWikiLink Function_composition.
- Church–Turing_thesis wikiPageWikiLink Gödel,_Escher,_Bach.
- Church–Turing_thesis wikiPageWikiLink Gödel,_Escher,_Bach:_an_Eternal_Golden_Braid.
- Church–Turing_thesis wikiPageWikiLink Halting_problem.
- Church–Turing_thesis wikiPageWikiLink Hao_Wang_(academic).
- Church–Turing_thesis wikiPageWikiLink History_of_the_Church–Turing_thesis.
- Church–Turing_thesis wikiPageWikiLink Hypercomputation.
- Church–Turing_thesis wikiPageWikiLink Hypercomputer.
- Church–Turing_thesis wikiPageWikiLink Hypothesis.
- Church–Turing_thesis wikiPageWikiLink Ibid..
- Church–Turing_thesis wikiPageWikiLink Inductive_reasoning.
- Church–Turing_thesis wikiPageWikiLink J.B._Rosser.
- Church–Turing_thesis wikiPageWikiLink J._Barkley_Rosser.
- Church–Turing_thesis wikiPageWikiLink Jack_Copeland.
- Church–Turing_thesis wikiPageWikiLink Jacques_Herbrand.
- Church–Turing_thesis wikiPageWikiLink Joachim_Lambek.
- Church–Turing_thesis wikiPageWikiLink John_Lucas_(philosopher).
- Church–Turing_thesis wikiPageWikiLink Kurt_Gödel.
- Church–Turing_thesis wikiPageWikiLink Lambda_calculus.
- Church–Turing_thesis wikiPageWikiLink Markov_algorithm.
- Church–Turing_thesis wikiPageWikiLink Martin_Davis.
- Church–Turing_thesis wikiPageWikiLink Marvin_Minsky.
- Church–Turing_thesis wikiPageWikiLink Model_of_computation.
- Church–Turing_thesis wikiPageWikiLink Monte_Carlo_method.
- Church–Turing_thesis wikiPageWikiLink Natural_law.
- Church–Turing_thesis wikiPageWikiLink Natural_number.
- Church–Turing_thesis wikiPageWikiLink Natural_numbers.
- Church–Turing_thesis wikiPageWikiLink P_(complexity).
- Church–Turing_thesis wikiPageWikiLink Philosophy_of_mind.
- Church–Turing_thesis wikiPageWikiLink Physical_change.
- Church–Turing_thesis wikiPageWikiLink Physical_process.
- Church–Turing_thesis wikiPageWikiLink Pointer_machine.
- Church–Turing_thesis wikiPageWikiLink Polynomial-time_reduction.
- Church–Turing_thesis wikiPageWikiLink Post–Turing_machine.
- Church–Turing_thesis wikiPageWikiLink Probabilistic_Turing_machine.
- Church–Turing_thesis wikiPageWikiLink Probabilistic_algorithms.
- Church–Turing_thesis wikiPageWikiLink Quantum_Turing_machine.
- Church–Turing_thesis wikiPageWikiLink Quantum_algorithm.
- Church–Turing_thesis wikiPageWikiLink Quantum_algorithms.
- Church–Turing_thesis wikiPageWikiLink Quantum_mechanics.
- Church–Turing_thesis wikiPageWikiLink Random-access_machine.
- Church–Turing_thesis wikiPageWikiLink Random_Access_Machine.
- Church–Turing_thesis wikiPageWikiLink Randomized_algorithm.