国立中正大学资讯工程所计算理论实验室荣誉出品.ppt
《国立中正大学资讯工程所计算理论实验室荣誉出品.ppt》由会员分享,可在线阅读,更多相关《国立中正大学资讯工程所计算理论实验室荣誉出品.ppt(75页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、国立中正大学资讯工程所计算理论实验室荣誉出品 Still waters run deep.流静水深流静水深,人静心深人静心深 Where there is life,there is hope。有生命必有希望。有生命必有希望The Church-Turing Thesis:Breaking the MythSpeaker:Chuang-Chieh LinAdvisor:Professor Maw-Shang ChangComputation Theory Laboratory,National Chung Cheng University,Taiwan Dina Goldin and Pete
2、r WegnerLecture Notes in Computer Science,Vol.3526,2005,pp.152-168.Alan Turing(1912 1954)Alonzo Church(1903-1995)3-Dept.of CSIE,CCU,Taiwan-It is not Alan Turings fault.Really.4-Dept.of CSIE,CCU,Taiwan-OutlineIntroductionTuring MachinesThe Turing Thesis MythAlgorithms and ComputabilityPersistent Turi
3、ng Machines(PTMs)Turing Thesis Myth CorrectedConclusion5-Dept.of CSIE,CCU,Taiwan-OutlineIntroductionTuring MachinesThe Turing Thesis MythAlgorithms and ComputabilityPersistent Turing Machines(PTMs)Turing Thesis Myth CorrectedConclusion6-Dept.of CSIE,CCU,Taiwan-What Is Computation?The theory of compu
4、tation views computation as a closed box transformation of inputs to outputs,completely captured by Turing machines,which will be introduced later.inputoutput7-Dept.of CSIE,CCU,Taiwan-Turings ThesisTurings thesis:LCMs can do anything that could be described as“rule of thumb”or“purely mechanical”(194
5、8)In the above sentence,LCMs means logical computing machines,that are Turings expressions for Turing machines.Let us see the myth first.8-Dept.of CSIE,CCU,Taiwan-The Turing Thesis MythClaim 1.All computable problems are function-based.Clam 2.All computable problems can be described by an algorithm.
6、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.9-Dept.of CSIE,CCU,Taiwan-OutlineIntroductionTuring MachinesThe Turing Thesis MythAlgorithms and ComputabilityPersistent Turing Machines(PTMs)Turi
7、ng Thesis Myth CorrectedConclusion10-Dept.of CSIE,CCU,Taiwan-Turing MachinesI will make use of Prof.Tsais lectures to introduce Turing machines as follows.11-Dept.of CSIE,CCU,Taiwan-.TapeRead-Write headControl Unit 12-Dept.of CSIE,CCU,Taiwan-.Read-Write headNo boundaries-infinite length The head mov
8、es Left or RightThe tapeOR13-Dept.of CSIE,CCU,Taiwan-.Read-Write headThe head at each time step:1.Reads a symbol 2.Writes a symbol 3.Moves Left or Right14-Dept.of CSIE,CCU,Taiwan-.Example:Time 0.Time 11.Reads a2.Writes k 3.Moves Left15-Dept.of CSIE,CCU,Taiwan-.Time 1.Time 21.Reads b2.Writes f3.Moves
9、 Right16-Dept.of CSIE,CCU,Taiwan-The Input String.Blank symbolheadHead starts at the leftmost positionof the input stringInput string17-Dept.of CSIE,CCU,Taiwan-States&TransitionsReadWriteMove LeftMove Right18-Dept.of CSIE,CCU,Taiwan-Turing machine for the language19-Dept.of CSIE,CCU,Taiwan-Time 020-
10、Dept.of CSIE,CCU,Taiwan-Time 121-Dept.of CSIE,CCU,Taiwan-Time 222-Dept.of CSIE,CCU,Taiwan-Time 323-Dept.of CSIE,CCU,Taiwan-Time 424-Dept.of CSIE,CCU,Taiwan-Time 525-Dept.of CSIE,CCU,Taiwan-Time 626-Dept.of CSIE,CCU,Taiwan-Time 727-Dept.of CSIE,CCU,Taiwan-Time 828-Dept.of CSIE,CCU,Taiwan-Time 929-Dep
11、t.of CSIE,CCU,Taiwan-Time 1030-Dept.of CSIE,CCU,Taiwan-Time 1131-Dept.of CSIE,CCU,Taiwan-Time 1232-Dept.of CSIE,CCU,Taiwan-Halt&AcceptTime 1333-Dept.of CSIE,CCU,Taiwan-Turing machines with stay option,semi-infinite tape,multitape,nondeterministic have the same power as the standard Turing machine wh
12、ich 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”.34-Dept.of CSIE,CCU,Taiwan-Here we introduce the concept of the universal TM.We regard TMs as“hardwired”
13、components,each of which execute only one program.An universal TM is a reprogrammable machine that can simulate any other TM,say M.Input of a universal TM M:Description of transitions of MInitial tape contents of MFor example:35-Dept.of CSIE,CCU,Taiwan-Universal Turing Machine MDescription of Tape C
14、ontents of State of Three tapesTape 2Tape 3Tape 1TM1TM2TM336-Dept.of CSIE,CCU,Taiwan-The Universal Turing Machine This picture looks awful,doesnt it?37-Dept.of CSIE,CCU,Taiwan-Yet,are TMs so wonderful that they can solve all computational problems in the computer science?Professor Tsai and many theo
15、reticians didnt find any problem that can be solved by an algorithm but cant be solved by any Turing machine.We were taught that TMs can simulates any computer.Many computer theoreticians believe that.38-Dept.of CSIE,CCU,Taiwan-OutlineIntroductionTuring MachinesThe Turing Thesis MythAlgorithms and C
16、omputabilityPersistent Turing Machines(PTMs)Turing Thesis Myth CorrectedConclusion39-Dept.of CSIE,CCU,Taiwan-Church-Turing ThesisWhenever there is an effective method(algorithm)for obtaining the values of a mathematical function,the function can be computed by a TM.40-Dept.of CSIE,CCU,Taiwan-Strong
17、Church-Turing ThesisA TM can do(compute)anything that a computer can do.41-Dept.of CSIE,CCU,Taiwan-The Turing Thesis MythClaim 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.TMs serve as a
18、general model for computers.Claim 5.TMs can simulate any computer.42-Dept.of CSIE,CCU,Taiwan-To break the myth,we have to investigate the role of algorithms.43-Dept.of CSIE,CCU,Taiwan-OutlineIntroductionTuring MachinesThe Turing Thesis MythAlgorithms and ComputabilityPersistent Turing Machines(PTMs)
19、Turing Thesis Myth CorrectedConclusion44-Dept.of CSIE,CCU,Taiwan-The Original Role of algorithmsAlgorithms are“recipes”for carrying out function-based computation,that can be followed mechanically.Given some finite input x,an algorithm describes the steps for effectively transforming it to an output
20、 y,where y is f(x)for some(recursive)function f.45-Dept.of CSIE,CCU,Taiwan-The Original Role of algorithms(contd.)The notion of an algorithm is a mathematical concept much older than TMs.For example the Euclids algorithm for finding common divisors.46-Dept.of CSIE,CCU,Taiwan-The Original Role of alg
21、orithms(contd.)Donald E.Knuth explicitly specified that algorithms are closed;no new input is accepted once the computation has begun.“An algorithm has zero or more inputs,i.e.,quantities which are given to it initially before the algorithm begins”.K6847-Dept.of CSIE,CCU,Taiwan-The Original Role of
22、algorithms(contd.)Knuth distinguished algorithms from arbitrary computation that may involve I/O.Thus Knuths careful discussion of algorithmic computation remains definitive to this day.His discussion of algorithms ensures their function-based behavior and guarantees their equivalence with TMs.K6848
23、-Dept.of CSIE,CCU,Taiwan-The Original Role of algorithms(contd.)Knuth said:“There are many other essentially equivalent ways to formulate the concept of an effective computational method(for example,using TMs).”49-Dept.of CSIE,CCU,Taiwan-The Original Role of algorithms(contd.)The coexistence of the
24、informal(algorithms-based)and the formal(TM-based)approaches to defining solvable problems can be found in all modern textbook on algorithms or computability.This has proved tremendously convenient for computer scientists,by allowing us to describe function-based computation informally using“pseudoc
25、ode”,with the knowledge that an equivalent Turing machine can be constructed.50-Dept.of CSIE,CCU,Taiwan-The Original Role of algorithms(contd.)As we will see,these inconsistencies in the various definitions of an algorithm greatly contributed to the Turing Thesis myth.51-Dept.of CSIE,CCU,Taiwan-The
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 国立 中正 大学 资讯 工程 计算 理论 实验室 荣誉 出品
限制150内