Matches in DBpedia 2016-04 for { <http://wikidata.dbpedia.org/resource/Q309157> ?p ?o }
- Q309157 subject Q7035970.
- Q309157 subject Q8362290.
- Q309157 subject Q8596994.
- Q309157 subject Q9384007.
- Q309157 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 about the nature of computable functions. It states that a function on the natural numbers is computable by a human being 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.".
- Q309157 wikiPageExternalLink 164.pdf.
- Q309157 wikiPageExternalLink computation-physicalsystems.
- Q309157 wikiPageExternalLink tp2-ie.pdf.
- Q309157 wikiPageExternalLink transcendental-idealism-and-posts-variant-of-the-church-turing-thesis.
- Q309157 wikiPageWikiLink Q1029256.
- Q309157 wikiPageWikiLink Q1071239.
- Q309157 wikiPageWikiLink Q1089708.
- Q309157 wikiPageWikiLink Q11030584.
- Q309157 wikiPageWikiLink Q11348.
- Q309157 wikiPageWikiLink Q1137814.
- Q309157 wikiPageWikiLink Q1148456.
- Q309157 wikiPageWikiLink Q1191836.
- Q309157 wikiPageWikiLink Q1239172.
- Q309157 wikiPageWikiLink Q12916.
- Q309157 wikiPageWikiLink Q1427965.
- Q309157 wikiPageWikiLink Q1481571.
- Q309157 wikiPageWikiLink Q163310.
- Q309157 wikiPageWikiLink Q170058.
- Q309157 wikiPageWikiLink Q1701524.
- Q309157 wikiPageWikiLink Q176916.
- Q309157 wikiPageWikiLink Q179976.
- Q309157 wikiPageWikiLink Q189156.
- Q309157 wikiPageWikiLink Q1900936.
- Q309157 wikiPageWikiLink Q1930388.
- Q309157 wikiPageWikiLink Q193803.
- Q309157 wikiPageWikiLink Q197970.
- Q309157 wikiPageWikiLink Q204815.
- Q309157 wikiPageWikiLink Q205084.
- Q309157 wikiPageWikiLink Q2103034.
- Q309157 wikiPageWikiLink Q21199.
- Q309157 wikiPageWikiLink Q232207.
- Q309157 wikiPageWikiLink Q23407.
- Q309157 wikiPageWikiLink Q242028.
- Q309157 wikiPageWikiLink Q244615.
- Q309157 wikiPageWikiLink Q244761.
- Q309157 wikiPageWikiLink Q249984.
- Q309157 wikiPageWikiLink Q2565212.
- Q309157 wikiPageWikiLink Q2574032.
- Q309157 wikiPageWikiLink Q2623817.
- Q309157 wikiPageWikiLink Q264164.
- Q309157 wikiPageWikiLink Q2651576.
- Q309157 wikiPageWikiLink Q2661997.
- Q309157 wikiPageWikiLink Q2703890.
- Q309157 wikiPageWikiLink Q284164.
- Q309157 wikiPageWikiLink Q29524.
- Q309157 wikiPageWikiLink Q309157.
- Q309157 wikiPageWikiLink Q3240978.
- Q309157 wikiPageWikiLink Q327637.
- Q309157 wikiPageWikiLink Q332905.
- Q309157 wikiPageWikiLink Q335148.
- Q309157 wikiPageWikiLink Q3387984.
- Q309157 wikiPageWikiLink Q351366.
- Q309157 wikiPageWikiLink Q41390.
- Q309157 wikiPageWikiLink Q41585.
- Q309157 wikiPageWikiLink Q41719.
- Q309157 wikiPageWikiLink Q430001.
- Q309157 wikiPageWikiLink Q4353569.
- Q309157 wikiPageWikiLink Q448086.
- Q309157 wikiPageWikiLink Q484511.
- Q309157 wikiPageWikiLink Q5116527.
- Q309157 wikiPageWikiLink Q5157263.
- Q309157 wikiPageWikiLink Q5295939.
- Q309157 wikiPageWikiLink Q5347270.
- Q309157 wikiPageWikiLink Q583461.
- Q309157 wikiPageWikiLink Q5869238.
- Q309157 wikiPageWikiLink Q601325.
- Q309157 wikiPageWikiLink Q622849.
- Q309157 wikiPageWikiLink Q649732.
- Q309157 wikiPageWikiLink Q652719.
- Q309157 wikiPageWikiLink Q655328.
- Q309157 wikiPageWikiLink Q676835.
- Q309157 wikiPageWikiLink Q68.
- Q309157 wikiPageWikiLink Q7035970.
- Q309157 wikiPageWikiLink Q707977.
- Q309157 wikiPageWikiLink Q7208369.
- Q309157 wikiPageWikiLink Q7251.
- Q309157 wikiPageWikiLink Q7345768.
- Q309157 wikiPageWikiLink Q7390263.
- Q309157 wikiPageWikiLink Q746264.
- Q309157 wikiPageWikiLink Q7632653.
- Q309157 wikiPageWikiLink Q765620.
- Q309157 wikiPageWikiLink Q7661893.
- Q309157 wikiPageWikiLink Q7663875.
- Q309157 wikiPageWikiLink Q787114.
- Q309157 wikiPageWikiLink Q7879073.
- Q309157 wikiPageWikiLink Q796890.
- Q309157 wikiPageWikiLink Q8061506.
- Q309157 wikiPageWikiLink Q818888.
- Q309157 wikiPageWikiLink Q818895.
- Q309157 wikiPageWikiLink Q818930.
- Q309157 wikiPageWikiLink Q831517.
- Q309157 wikiPageWikiLink Q8362290.
- Q309157 wikiPageWikiLink Q846354.
- Q309157 wikiPageWikiLink Q8596994.
- Q309157 wikiPageWikiLink Q877945.