国立中正大学资讯工程所计算理论实验室荣誉出品.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

26、Original Role of algorithms(contd.)“A procedure is a finite sequence of instructions that can be mechanically carried out,such as a computer program A procedure which always terminates is called an algorithm.”-Hopcroft,J.E.and Ullman,J.D.HU69“An algorithm is a recipe,a set of instructions or the spe

27、cifications of a process for doing something.That something is usually solving a problem of some sort”-Rice J.K.and Rice J.N.RR6952-Dept.of CSIE,CCU,Taiwan-The Original Role of algorithms(contd.)“A TM can do anything that a computer can do.”-Sipser,M.S97ANYTHING?53-Dept.of CSIE,CCU,Taiwan-Let us see

28、 some counterexamplesDriving Home From Work EGW04Create a car that is capable of driving us home from work,where the locations of both work and home are provided as input parameters.Operating SystemsThey never terminate,if they are fine.Online algorithmsInputs are given dynamically or ongoingly.54-D

29、ept.of CSIE,CCU,Taiwan-According to the interactive view of computation,communication happens during the computation,not before or after it.Its time for NEW MODELS.Wegner has conjectured that interactive models of computation are more expressive than“algorithmic”ones such as Turing machines.W97,W985

30、5-Dept.of CSIE,CCU,Taiwan-It would therefore be interesting to find out what minimal extensions are necessary to TMs to capture the salient aspects of interactive computing.Motivated by these goals,Goldin et al.GSAS04 proposed a new way of interpreting TM computation,one that is both interactive and

31、 persistent:persistent Turing machines56-Dept.of CSIE,CCU,Taiwan-OutlineIntroductionTuring MachinesThe Turing Thesis MythAlgorithms and ComputabilityPersistent Turing Machines(PTMs)Turing Thesis Myth CorrectedConclusion57-Dept.of CSIE,CCU,Taiwan-Persistent Turing Machines(PTMs)An N3TM is a nondeterm

32、inistic 3-tape TM that has three semi-infinite tapes.A persistent Turing machine(PTM)is an N3TM having a read-only input tape,a read/write work tape and a write-only output tape.Moreover,a PTM is allowed to“remember”its previous work-tape contents upon commencing a new computation.58-Dept.of CSIE,CC

33、U,Taiwan-Three-tape Turing Machines(N3TM)s-current state w1-contents of input tape w2-contents of work tape w3-contents of output tape n1,n2,n3-tape head positionsConfigurations:inputworkoutputS SComputation=a sequence of transitions between configurations,from initial to halting.59-Dept.of CSIE,CCU

34、,Taiwan-N3TM macrostepsNotation:winw winshwwoutM|s060-Dept.of CSIE,CCU,Taiwan-Extending N3TM Computations Dynamic stream semantics-Inputs are streams of dynamically generated tokens(strings).-For each input token,there is an N3TM macrostep generating the corresponding output token.Persistence(memory

35、)-The contents w of the work tape at the beginning of each macrostep is the same as at the end of the previous one.in1S S0 0 S Sh hout1w1in1in2S S0 0w1 S Sh hout2w2in2.61-Dept.of CSIE,CCU,Taiwan-Persistent Stream Language(PSL)of a PTM:set of streams:.Persistent Turing Machine(PTM)PTMmemoryEnvironmen

36、tInteraction Streamstream of inputsstream of outputs62-Dept.of CSIE,CCU,Taiwan-Examples of the PTMsAnswering Machine(AM)PSL(AM)contains:Sequential objects as PTMsfAM(record Y,X)=(ok,XY)fAM(erase,X)=(done,)fAM(playback,X)=(X,X)(record See,ok),(erase,done),(record Chuang,ok),(record Chieh,ok),(playbac

37、k,Chuang Chieh),SeeChuangwork tapeChieh63-Dept.of CSIE,CCU,Taiwan-At each step,output first bit of previous step.inputs in1;outputs 1inputs in2;outputs 1st bit of in1inputs in3;outputs 1st bit of in2.PSL(Latch)contains:LatchLatch is a PTM working as a Labeled Transition SystemLatch has 3 states,mean

38、ing“contents of the work tape”The labels are input/output pairs,as in the interaction stream.Another example:Latch#10(1*,1)(1*,1)(0*,1)(0*,1)(0*,1)(0*,1)(1*,0)(1*,0)(1*,1)(1*,1)(0*,0)(0*,0)LatchLatch64-Dept.of CSIE,CCU,Taiwan-To simplify our discussion,we omit the other properties,language classes a

39、nd the equivalence hierarchy concerning to PTMs.However,we can find abundant information in the following two journal papers.(about 65 pages)W98 appeared in Theoretical Computer Science(Vol.192,1998)GSAS04 appeared in Information and Computation(Vol.194,2004)and65-Dept.of CSIE,CCU,Taiwan-OutlineIntr

40、oductionTuring MachinesThe Turing Thesis MythAlgorithms and ComputabilityPersistent Turing Machines(PTMs)Turing Thesis Myth CorrectedConclusion66-Dept.of CSIE,CCU,Taiwan-Corrected Turing ThesisClaim 1.All algorithmic problems are function-based.Clam 2.All function-based problems can be described by

41、an algorithm.Claim 3.Algorithms are what early computers do.67-Dept.of CSIE,CCU,Taiwan-Claim 4.TMs serve as a general model for early computers.Claim 5.TMs can simulate any algorithmic computing device.Claim 6.TMs cannot compute all problems,nor can they do everything that real computers can do.68-D

42、ept.of CSIE,CCU,Taiwan-OutlineIntroductionTuring MachinesThe Turing Thesis MythAlgorithms and ComputabilityPersistent Turing Machines(PTMs)Turing Thesis Myth CorrectedConclusion69-Dept.of CSIE,CCU,Taiwan-Any question?70-Dept.of CSIE,CCU,Taiwan-Thank youReferences65 An Undergraduate Program in Comput

43、er Science-Preliminary Recommendations,A Report from the ACM Curriculum Committee on Computer Science,Communications of the ACM,Vol.8,No.9,September 1965,pp.543-552.68 Curriculum 68:Recommendations for Academic Programs in Computer Science,A Report of the ACM Curriculum Committee on Computer Science

44、,Communications of the ACM,Vol.11,No.3,March 1968,pp.151-197.04 SIGACT News,ACM Press,March 2004,p.49.B91 Intelligence Without Reason,Brooks,R.,MIT AI Lab Technical Report 1293,1991.D58 Computability&Unsolvability,Davis,M.,McGraw-Hill,1958.D04 The Field of Programmers Myth,Denning,P.,Communications

45、of the ACM,July,2004.EGW04 Turings Ideas and Models of Computation.In Alan Turing:Life and Legacy of a Great Thinker,ed.Christof Teuscher,Springer,2004.GMR89 The Knowledge Complexity of Interactive Proof Systems,Goldwasser,S.,Micali,S.and Rackoff,C.,SIAM Journal on Computing,Vol.18,No.1,1989,pp.186-

46、208.72-Dept.of CSIE,CCU,Taiwan-GSAS04 Turing Machines,Transition Systems,and Interaction,Goldin,D.Q.,Smolka,S.A.,Attie,P.C.and Sonderegger,E.L.,Information and Computation,Vol.194,Issue 2,November 2004,pp.101-128.HU69 Formal Languages and Their Relation to Automata,Hopcroft,J.E.and Ullman,J.D.,Addis

47、on-Wesley,1969.K68 The Art of Computer Programming,Vol.1:Fundamental Algorithms,Knuth,D.E.,1968.LT89 An Introduction to Input/Output Automata,Lynch,N.and Tuttle,M.,CWI Quarterly,Vol.2,No.3,September 1989,pp.219-246.RR69 Computer Science:Problems,Algorithms,Languages,Information and Computers,Rice,J.

48、K.and Rice J.N.,Holt,Rinehart and Winston,1969.RN94 Artificial Intelligence:A Modern Approach,Russel S.and Norveig,P.,Addison-Wesley,1994.R67 Theory of Recursive Functions and Effective Computability,Rogers,H.Jr.,McGraw-Hill,1967.S92 Recursive Functions,Sanchis,L.,North Holland,1992.73-Dept.of CSIE,

49、CCU,Taiwan-S97 Introduction to the Theory of Computation,Sipser,M.,PWS Publishing Company,1997.T37 On Computable Numbers,with an Application to the Entscheidungsproblem,Proceedings of the London Mathematical Society,Turing,A.,Vol.42,No.2,1936,pp.230-265;A correction:ibid,Vol.43,1937,pp.544-546.LW00

50、The Turing Machine Paradigm in Contemporary Computing,Leeuwen J.v.,Wiedermann,J.,Mathematics Unlimited 2001 and Beyond,eds.,Enquist,B.and Schmidt,W.,Springer-Verlag,2000.W68 Programming Languages,Information Structures and Machine Organization,Wegner,P.,McGraw-Hill,1968.W97 Why Interaction is More P