国立中正大学资讯工程所计算理论实验室荣誉出品.pptVIP

The Church-Turing Thesis: Breaking the Myth Speaker: Chuang-Chieh Lin Advisor: Professor Maw-Shang Chang Computation Theory Laboratory, National Chung Cheng University, Taiwan It is not Alan Turing’s fault. Really. Outline Introduction Turing Machines The Turing Thesis Myth Algorithms and Computability Persistent Turing Machines (PTMs) Turing Thesis Myth Corrected Conclusion Outline Introduction Turing Machines The Turing Thesis Myth Algorithms and Computability Persistent Turing Machines (PTMs) Turing Thesis Myth Corrected Conclusion What Is Computation? The theory of computation views computation as a closed box transformation of inputs to outputs, completely captured by Turing machines, which will be introduced later. Turing’s Thesis Turing’s thesis: LCMs can do anything that could be described as “rule of thumb” or “purely mechanical” (1948) In the above sentence, LCMs means logical computing machines, that are Turings expressions for Turing machines. Let us see the myth first. The Turing Thesis Myth Claim 1. All computable problems are function-based. Clam 2. All computable problems can be described by an algorithm. Claim 3. Algorithms are what computers do. Claim 4. Turing machines serve as a general model for computers. Claim 5. Turing machines can simulate any computer. Outline Introduction Turing Machines The Turing Thesis Myth Algorithms and Computability Persistent Turing Machines (PTMs) Turing Thesis Myth Corrected Conclusion Turing Machines I will make use of Prof. Tsai’s lectures to introduce Turing machines as follows. The Input String States Transitions Turing machines with stay option, semi-infinite tape, multitape, nondeterministic have the same power as the standard Turing machine which is we just introduced. That is, they can recognize the same class of languages. (i.e., they can solve the same problems.) To simplify our discussion, we use “TM ” to stand for the noun “Turing machine”. Here we introduce the concept of the universal