처치-튜링 명제

수학노트
둘러보기로 가기 검색하러 가기

노트

말뭉치

  1. 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.[1]
  2. The Church-Turing thesis states the equivalence between the mathematical concepts of algorithm or computation and Turing-Machine.[2]
  3. Hence, Church-Turing thesis also states that λ-calculus and recursive functions also correspond to the concept of computability.[2]
  4. In 1930, this statement was first formulated by Alonzo Church and is usually referred to as Church’s thesis, or the Church-Turing thesis.[3]
  5. There are various equivalent formulations of the Turing-Church thesis (which is also known as Turing's thesis, Church's thesis, and the Church-Turing thesis).[4]
  6. The Turing-Church thesis is the assertion that this set contains every function whose values can be obtained by a method satisfying the above conditions for effectiveness.[4]
  7. When the thesis is expressed in terms of the formal concept proposed by Turing, it is appropriate to refer to the thesis also as 'Turing's thesis'; and mutatis mutandis in the case of Church.[4]
  8. He argued for the claim (Turing's thesis) that whenever there is an effective method for obtaining the values of a mathematical function, the function can be computed by a Turing machine.[4]
  9. The Church-Turing thesis encompasses more kinds of computations than those originally envisioned, such as those involving cellular automata, combinators, register machines, and substitution systems.[5]
  10. There are conflicting points of view about the Church-Turing thesis.[5]
  11. Church's thesis and Turing's thesis are thus equivalent, if attention is restricted to functions of positive integers.[6]
  12. Later in this article we examine complexity-theoretic and physical versions of the Church-Turing thesis but first turn to the question of the justification of the theses introduced so far.[6]
  13. The Church-Turing thesis is the assertion that this set S contains every function whose values can be obtained by a method satisfying the above conditions for effectiveness.[7]
  14. The Church-Turing thesis is about computation as this term was used in 1936, viz.[7]
  15. This promise is hindered by the widespread belief, incorrectly known as the Church-Turing thesis, that no model of computation more expressive than Turing machines can exist.[8]
  16. The Church-Turing thesis: A Turing machine that halts on all inputs is the precise, formal notion corresponding to the intuitive notion of an algorithm.[9]
  17. The Church-Turing thesis cannot be proved because it relates a formal concept (Turing machines) to a vaguely dened informal one.[9]
  18. Also, the fact that all reasonable extensions to Turing machines do not increase their power, is a justication of the Church-Turing thesis.[9]
  19. Using the Church-Turing thesis, if one can show that a problem cannot be solved on a Turing machine, then it is reasonable to conclude that it cannot be solved by any computer or by any human.[9]
  20. The extended Church-Turing thesis is a foundational principle in computer science.[10]
  21. So, their two statements merged into one, which we now call Church-Turing thesis.[11]
  22. So, we can present the following equivalent formulation of the Church-Turing thesis: Equivalent formulation of the Church-Turing thesis.[11]
  23. To prove that the Ackermann function is computable is easy with todays tools Turing machines and Church-Turing thesis.[12]
  24. The Church-Turing thesis also does not provide insight into a working Theory of the Mind - the human brain and sentience is still a mystery.[13]
  25. The church-turing thesis: Consensus and opposition.[13]
  26. There are various proposed derivation of the Church-Turing thesis from physics laws.[14]
  27. Oron Shagrir have written several philosophical papers about the Church-Turing thesis see his webpage.[14]
  28. " One aspect of the effecient Church-Turing thesis (again, both in its classical and quantum version) is that NP hard problems cannot be computed efficiently by any computational device.[14]
  29. The fact that the class of E partial functions is closed under all known techniques of this sort is another bit of evidence in favor of the Church-Turing thesis.[15]
  30. Right back in Chapter 2 we stated Turing's Thesis: a numerical (total) function is effectively computable by some algorithmic routine if and only if it is computable by a Turing machine.[16]
  31. The Church Turing thesis is perhaps best understood as a definition of the types of functions that are calculable in the real world - not as a theorem to be proven.[17]
  32. This paper defends a modest version of the Physical Church-Turing thesis (CT).[18]
  33. Venn diagrams representing The Church-Turing thesis and its converse.[18]
  34. This claim is called the Church-Turing thesis.[19]
  35. The Church-Turing thesis is appealed to in two ways.[19]
  36. Then we can invoke the Church-Turing thesis to justify the claim that the same function is computed by some Turing machine, even if we have not in fact constructed it.[19]
  37. From this, using the Church-Turing thesis, one can conclude that it cannot be eectively computed, using any procedure whatsoever.[19]
  38. I propose this idea as an alternative foundation for the Church-Turing thesis, both for human and machine computation.[20]
  39. The previous result combined with a similar one with the Turing Machine, led to the Church-Turing thesis.[21]

소스

  1. ↑ Church–Turing thesis
  2. ↑ 이동: 2.0 2.1 Church-Turing Thesis
  3. ↑ Church’s Thesis for Turing Machine
  4. ↑ 이동: 4.0 4.1 4.2 4.3 AlanTuring.net The Turing-Church Thesis
  5. ↑ 이동: 5.0 5.1 Church-Turing Thesis -- from Wolfram MathWorld
  6. ↑ 이동: 6.0 6.1 The Church-Turing Thesis: Logical Limit or Breachable Barrier?
  7. ↑ 이동: 7.0 7.1 The Church-Turing Thesis (Stanford Encyclopedia of Philosophy)
  8. ↑ The Church-Turing Thesis: Breaking the Myth
  9. ↑ 이동: 9.0 9.1 9.2 9.3 1 undecidability; the church-turing thesis
  10. ↑ Quantum computation and extended church-turing thesis
  11. ↑ 이동: 11.0 11.1 Church-turing thesis
  12. ↑ A brief note on church-turing thesis and r.e. sets
  13. ↑ 이동: 13.0 13.1 Church-Turing Thesis — Vish Ravindran
  14. ↑ 이동: 14.0 14.1 14.2 Physics and Church–Turing Thesis
  15. ↑ The church-turing thesis
  16. ↑ The Church–Turing Thesis (Chapter 34)
  17. ↑ Church-Turing Thesis
  18. ↑ 이동: 18.0 18.1 The physical church-turing thesis: modest or bold?1
  19. ↑ 이동: 19.0 19.1 19.2 19.3 Mac.1 the church-turing thesis
  20. ↑ “the church-turing “thesis” as a special corollary of gödel’s
  21. ↑ What is the church-turing thesis?

메타데이터

위키데이터

Spacy 패턴 목록

  • [{'LOWER': 'church'}, {'OP': '*'}, {'LOWER': 'turing'}, {'LEMMA': 'thesis'}]
  • [{'LOWER': 'turing'}, {'OP': '*'}, {'LOWER': 'church'}, {'LEMMA': 'thesis'}]
  • [{'LOWER': 'church'}, {'OP': '*'}, {'LOWER': 'turing'}, {'LEMMA': 'conjecture'}]
  • [{'LOWER': 'church'}, {'LOWER': "'s"}, {'LEMMA': 'thesis'}]
  • [{'LOWER': 'church'}, {'LOWER': "'s"}, {'LEMMA': 'conjecture'}]
  • [{'LOWER': 'turing'}, {'LOWER': "'s"}, {'LEMMA': 'thesis'}]
원본 주소 "https://wiki.mathnt.net/index.php?title=처치-튜링_명제&oldid=52681"