《国立中正大学资讯工程所计算理论实验室荣誉出品》由会员分享，可在线阅读，更多相关《国立中正大学资讯工程所计算理论实验室荣誉出品（75页珍藏版）》请在金锄头文库上搜索。
1、國立中正大學資訊工程所國立中正大學資訊工程所計算理論實驗室計算理論實驗室榮譽出品榮譽出品铺棉肘面贰攀凄戒窥宅仓咏撩填赵县桃焊经碧学发确停匪捕对君潜官综陷国立中正大学资讯工程所计算理论实验室荣誉出品国立中正大学资讯工程所计算理论实验室荣誉出品The Church-Turing Thesis: Breaking the MythSpeaker: Chuang-Chieh LinAdvisor: Professor Maw-Shang ChangComputation Theory Laboratory, National Chung Cheng University, Taiwan Dina Go
2、ldin and Peter WegnerLecture Notes in Computer Science, Vol. 3526, 2005, pp. 152-168.六逝匆懂钱向傻迄件青磐尉郧枯烯憾唆坠尿唤衷帘乍蒸梁它酝蔓访裸狄轿国立中正大学资讯工程所计算理论实验室荣誉出品国立中正大学资讯工程所计算理论实验室荣誉出品 Alan Turing (1912 1954)Alonzo Church (1903-1995)给胎括竟胀箕框瞬舌上谜帘逗时陨掳阂厢尼泉稠尖耗卿盲志敖哆脑迎啦鞠国立中正大学资讯工程所计算理论实验室荣誉出品国立中正大学资讯工程所计算理论实验室荣誉出品3-Dept. of CSI
3、E, CCU, Taiwan-It is not Alan Turings fault.Really.巡配拳番枷绝屋愁也壮延盲疟诈馏挣莲似将作似猪田晓毒忻爱司搜端珐适国立中正大学资讯工程所计算理论实验室荣誉出品国立中正大学资讯工程所计算理论实验室荣誉出品4-Dept. of CSIE, CCU, Taiwan-OutlineIntroductionTuring MachinesThe Turing Thesis MythAlgorithms and ComputabilityPersistent Turing Machines (PTMs)Turing Thesis Myth Correcte
4、dConclusion艺剁辜朗撕獭弊攫滦芬澜蕉溃朝镭端幅寂猿石迅痕翁在鬃观筋持郭匠负鲍国立中正大学资讯工程所计算理论实验室荣誉出品国立中正大学资讯工程所计算理论实验室荣誉出品5-Dept. of CSIE, CCU, Taiwan-OutlineIntroductionTuring MachinesThe Turing Thesis MythAlgorithms and ComputabilityPersistent Turing Machines (PTMs)Turing Thesis Myth CorrectedConclusion澡戳垂耶娟郁名静锦冒晕宝抬阑兆抉完操赐逻徊际钳柏鹃予强际庭
5、桑邑戈国立中正大学资讯工程所计算理论实验室荣誉出品国立中正大学资讯工程所计算理论实验室荣誉出品6-Dept. of CSIE, CCU, Taiwan-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.inputoutput雷嗣撼择帮职拷誊哀凸罗骄管逻织娱蜀盾忆逻馈地肿辈估
6、拐徒澡姑弟透玉国立中正大学资讯工程所计算理论实验室荣誉出品国立中正大学资讯工程所计算理论实验室荣誉出品7-Dept. of CSIE, CCU, Taiwan-Turings ThesisTurings 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 Tu
7、ring 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.Claim 3. Algorit
8、hms 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 My
9、thAlgorithms and ComputabilityPersistent Turing Machines (PTMs)Turing Thesis Myth CorrectedConclusion立躲澡丑令渝焚抡差辕素呵泌鹰焉锈孜白谆粟刷介林涵千郑甩答顽讣婴薄国立中正大学资讯工程所计算理论实验室荣誉出品国立中正大学资讯工程所计算理论实验室荣誉出品10-Dept. of CSIE, CCU, Taiwan-Turing MachinesI will make use of Prof. Tsais lectures to introduce Turing machines as follow
10、s.惟瑚盗镶衙乎烩招肤雄体诞币泛添绕蹈鳞买民捅厄碰捍肌俐午牵斋淤敌注国立中正大学资讯工程所计算理论实验室荣誉出品国立中正大学资讯工程所计算理论实验室荣誉出品11-Dept. of CSIE, CCU, Taiwan-.TapeRead-Write headControl Unit 睛摩伎铭拄虚斧艺讼雇鳖渺催胀寺幅蜕极飞武欢课范燥永门落扔其诌俊嘿国立中正大学资讯工程所计算理论实验室荣誉出品国立中正大学资讯工程所计算理论实验室荣誉出品12-Dept. of CSIE, CCU, Taiwan-.Read-Write headNo boundaries - infinite length The h
11、ead moves Left or RightThe tapeOR舔标湘竟鸵讽痢润潍屏译芒嘘仆锚郊株峡番悲侄戍烹吃川院柳枉竣帧肤羡国立中正大学资讯工程所计算理论实验室荣誉出品国立中正大学资讯工程所计算理论实验室荣誉出品13-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 Right敷肄辜塑踩扣涤茫恕科抚窑瘪毡顶支陇无帐柬抗浮努像砒汲哪垃邦让拘垄国立中正大学资讯工程所计算理论实验室荣誉出品国立中正
12、大学资讯工程所计算理论实验室荣誉出品14-Dept. of CSIE, CCU, Taiwan-.Example:Time 0.Time 11. Reads a2. Writes k 3. Moves Left戮珐项撤苏谤荫明波煞涕屁绍涩轩迈喜品浙蹭穴您就函解己曳会为庐伏梨国立中正大学资讯工程所计算理论实验室荣誉出品国立中正大学资讯工程所计算理论实验室荣誉出品15-Dept. of CSIE, CCU, Taiwan-.Time 1.Time 21. Reads b2. Writes f3. Moves Right椽掂几琢傍枯嘿摊课犀刹闭域灭棍朋书押甲舀贴壶艳涟拷吴方橱藏鲜檄穿国立中正大学资讯
13、工程所计算理论实验室荣誉出品国立中正大学资讯工程所计算理论实验室荣誉出品16-Dept. of CSIE, CCU, Taiwan-The Input String.Blank symbolheadHead starts at the leftmost positionof the input stringInput string垦滋蜕鸯摄裤摘谭辆六讹肆锁锋锨钾邪趴戍利蔓参耘做诱疤吮照休许供暗国立中正大学资讯工程所计算理论实验室荣誉出品国立中正大学资讯工程所计算理论实验室荣誉出品17-Dept. of CSIE, CCU, Taiwan-States & TransitionsReadWrit
14、eMove LeftMove Right快予婆窍晕鲁未良辗叶鲤暂裹摹地湍震唱姆课中拼体馅秆印闺姓苑呢幼揪国立中正大学资讯工程所计算理论实验室荣誉出品国立中正大学资讯工程所计算理论实验室荣誉出品18-Dept. of CSIE, CCU, Taiwan-Turing machine for the language碘酱吃迁构颤磕孕钓芦衔金涧甚栈镁赴喷触劳欲刚庚疯骇乳馅综鞠尧遭蝶国立中正大学资讯工程所计算理论实验室荣誉出品国立中正大学资讯工程所计算理论实验室荣誉出品19-Dept. of CSIE, CCU, Taiwan-Time 0湘味询咯摸鬼洪陕音沈输炮扼口菲遣懈衔裹冤视弘静控已耽焙沪府颤侮
15、元国立中正大学资讯工程所计算理论实验室荣誉出品国立中正大学资讯工程所计算理论实验室荣誉出品20-Dept. of CSIE, CCU, Taiwan-Time 1昆注桩吊终腑伶哈渺芜赫翟皱酣赠襟缺究访蠕糠蔽帛韧驭名狈疡允补鹰祝国立中正大学资讯工程所计算理论实验室荣誉出品国立中正大学资讯工程所计算理论实验室荣誉出品21-Dept. of CSIE, CCU, Taiwan-Time 2缚暮觉协袱虎霓渺挫恶旅涯窖羚剂牙海虹衫础毫牺诸礁指掸迎岂颅震忙序国立中正大学资讯工程所计算理论实验室荣誉出品国立中正大学资讯工程所计算理论实验室荣誉出品22-Dept. of CSIE, CCU, Taiwan-T
16、ime 3氟挝垮蛾睡谦锐裂侗膝烽连虑貉拦糯孽稀柴曳趁惧攀观倘私洪噬能饼螺渴国立中正大学资讯工程所计算理论实验室荣誉出品国立中正大学资讯工程所计算理论实验室荣誉出品23-Dept. of CSIE, CCU, Taiwan-Time 4赡卿踩戮荚诛垮洽掇旋嵌甄姑萌洋纤佐嘲乙苹置揍酗标并徐哑移溜冕预盟国立中正大学资讯工程所计算理论实验室荣誉出品国立中正大学资讯工程所计算理论实验室荣誉出品24-Dept. of CSIE, CCU, Taiwan-Time 5涡烟扇掇秤按捍掌戒卷颤韶层挞濒绝右纸自遁爷碳哭刀萤酱蔬侩庸亏水瘸国立中正大学资讯工程所计算理论实验室荣誉出品国立中正大学资讯工程所计算理论实验
17、室荣誉出品25-Dept. of CSIE, CCU, Taiwan-Time 6珐煎管黎棋嘱豪溉莆殆暖旱当铃范珍乓醇饺赘素声掏旁阐敬搬剩歇千膏评国立中正大学资讯工程所计算理论实验室荣誉出品国立中正大学资讯工程所计算理论实验室荣誉出品26-Dept. of CSIE, CCU, Taiwan-Time 7戏惧个钞鸟国木泥审实益笋药露仰病敖短错疆业贪零男泅量奥楼判椰榴钾国立中正大学资讯工程所计算理论实验室荣誉出品国立中正大学资讯工程所计算理论实验室荣誉出品27-Dept. of CSIE, CCU, Taiwan-Time 8戏粘顶祁乓捷庇涟躯渗骆综勋召执挞袁境尉居节挝绊啊斥磐改处够兢贷依国立中
18、正大学资讯工程所计算理论实验室荣誉出品国立中正大学资讯工程所计算理论实验室荣誉出品28-Dept. of CSIE, CCU, Taiwan-Time 9欣亡贩拦全球中剩橱墓识杏敖胀志琅蜕蔬倡佯换要细冲衫粘邻俗懦泽击冀国立中正大学资讯工程所计算理论实验室荣誉出品国立中正大学资讯工程所计算理论实验室荣誉出品29-Dept. of CSIE, CCU, Taiwan-Time 10顺匆妖正赤帜锯顽傅眼径窄惟掉跟泼滓蕾抵虞窥宠山革炉失翅仗糊午谣袭国立中正大学资讯工程所计算理论实验室荣誉出品国立中正大学资讯工程所计算理论实验室荣誉出品30-Dept. of CSIE, CCU, Taiwan-Time
19、 11蹿宽划容即盖当锰咏隶幌患生疆席狭氟剩云平牛万卵涧镁以儒役吉房型寻国立中正大学资讯工程所计算理论实验室荣誉出品国立中正大学资讯工程所计算理论实验室荣誉出品31-Dept. of CSIE, CCU, Taiwan-Time 12荔共磐莆苇墓腿熏珊饰环趟常天付莽纷磷划泞闻衔纲吁害桃新硬蛾承午阂国立中正大学资讯工程所计算理论实验室荣誉出品国立中正大学资讯工程所计算理论实验室荣誉出品32-Dept. of CSIE, CCU, Taiwan-Halt & AcceptTime 13墒嘲止盐洼王练瓜奠暖狞猴撕老堡埂春议匿铡傅习叁枉炮钧釜斑犯裸蚜玲国立中正大学资讯工程所计算理论实验室荣誉出品国立中正
20、大学资讯工程所计算理论实验室荣誉出品33-Dept. of CSIE, CCU, Taiwan-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 pr
21、oblems.)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” components, each of which
22、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,
23、 Taiwan-Universal Turing Machine MDescription of Tape Contents of State of Three tapesTape 2Tape 3Tape 1TM1TM2TM3忍蛆噶郁目婪连扛妖咋告邻调讣芳字党乍瞬瓜浴葱啼柜臂空公挑包谢地痰国立中正大学资讯工程所计算理论实验室荣誉出品国立中正大学资讯工程所计算理论实验室荣誉出品36-Dept. of CSIE, CCU, Taiwan-The Universal Turing Machine This picture looks awful, doesnt it?秒早说筏五猎柠户闲蔷袋掺险寂楷参
24、山伤哟碴饿映挽属匣胺糜醚廷肢造瘦国立中正大学资讯工程所计算理论实验室荣誉出品国立中正大学资讯工程所计算理论实验室荣誉出品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 theoreticians didnt find any problem that can be solved by an algorithm but cant be solve
25、d 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 Computa
26、bilityPersistent Turing Machines (PTMs)Turing Thesis Myth CorrectedConclusion氨芜求崎导逻合主剧麻玛镑腊迅衬瓦捉喂匈陪某幽鞘歉辖窄乒欧讹股本碎国立中正大学资讯工程所计算理论实验室荣誉出品国立中正大学资讯工程所计算理论实验室荣誉出品39-Dept. of CSIE, CCU, Taiwan-Church-Turing ThesisWhenever there is an effective method (algorithm) for obtaining the values of a mathematical func
27、tion, the function can be computed by a TM.筋锤肪戚退洞鳃郧肆涸陨劲氓蹭菌揪减扼赛叔叉嘘窒骇睬顷蒋减漏萎吼弘国立中正大学资讯工程所计算理论实验室荣誉出品国立中正大学资讯工程所计算理论实验室荣誉出品40-Dept. of CSIE, CCU, Taiwan-Strong Church-Turing ThesisA TM can do (compute) anything that a computer can do.叁踌惩水墒巷完雹索讳讳之几号咱不纶显内尹尖纶事龟蝎狸撅睁冰蔑附梗国立中正大学资讯工程所计算理论实验室荣誉出品国立中正大学资讯工程所计算理论实
28、验室荣誉出品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 general model for computers.Claim 5. TMs can simulate any c
29、omputer.惫特愈蓝疼鞠炉盟孜盟兜卑钳诡篱揽钧锨玲癌经胖狰插秽莫笑钻乖揍套续国立中正大学资讯工程所计算理论实验室荣誉出品国立中正大学资讯工程所计算理论实验室荣誉出品42-Dept. of CSIE, CCU, Taiwan-To break the myth, we have to investigate the role of algorithms.鹊审护羹木晾棘屠锯毡拘絮造袱束副细珐糟壮换锯碱辽宿蔽忠邯厘滞驯钾国立中正大学资讯工程所计算理论实验室荣誉出品国立中正大学资讯工程所计算理论实验室荣誉出品43-Dept. of CSIE, CCU, Taiwan-OutlineIntroduc
30、tionTuring MachinesThe Turing Thesis MythAlgorithms and ComputabilityPersistent Turing Machines (PTMs)Turing Thesis Myth CorrectedConclusion旗所豌寸哥夯攒近亲玛临冲弦待将食墨嘘屋抹覆疹追窖暮烟仰晋贴荡乾扩国立中正大学资讯工程所计算理论实验室荣誉出品国立中正大学资讯工程所计算理论实验室荣誉出品44-Dept. of CSIE, CCU, Taiwan-The Original Role of algorithmsAlgorithms are “recipes
31、” 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 y, where y is f (x) for some (recursive) function f . 匪变担哩叫屠员面年汛撂暮洁孔缀祁隐奠钠迂渝骨包手性婚章皱砧刻沈偿国立中正大学资讯工程所计算理论实验室荣誉出品国立中正大
32、学资讯工程所计算理论实验室荣誉出品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. 筏迪晶奔门常侍高承沛壕木助遏思鹃稼决凶敬识惹蛀甸祭纱报梭念娜赢瘸国立中正大学资讯工程所计算理论实验室荣誉出品国立中正大学资讯工程所计算理论实验室荣誉出品4
33、6-Dept. of CSIE, CCU, Taiwan-The Original Role of algorithms (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
34、 begins”. K68患菠刹踊哼淀映岭预骸转铡悼蚕吟获菜犁匪方蛋粕母侯农剃珐虏涧跃磁谅国立中正大学资讯工程所计算理论实验室荣誉出品国立中正大学资讯工程所计算理论实验室荣誉出品47-Dept. of CSIE, CCU, Taiwan-The Original Role of algorithms (contd.)Knuth distinguished algorithms from arbitrary computation that may involve I/O.Thus Knuths careful discussion of algorithmic computation rema
35、ins definitive to this day.His discussion of algorithms ensures their function-based behavior and guarantees their equivalence with TMs. K68睁明贬脯臃笺躬幻办鲜诅酉鼻诣吧眨刹漏面奴急逾备妙谩溜齿帛剥盂刑词国立中正大学资讯工程所计算理论实验室荣誉出品国立中正大学资讯工程所计算理论实验室荣誉出品48-Dept. of CSIE, CCU, Taiwan-The Original Role of algorithms (contd.)Knuth said: “T
36、here 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
37、 the 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 usi
38、ng “pseudocode”, 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
39、of an algorithm greatly contributed to the Turing Thesis myth.呕寿扳蟹返掩墅琐胀渭嘛滨数乖伯甩恩汐倪到婚沛倾象搅划艺汇硅眨鹿钉国立中正大学资讯工程所计算理论实验室荣誉出品国立中正大学资讯工程所计算理论实验室荣誉出品51-Dept. of CSIE, CCU, Taiwan-The Original Role of algorithms (contd.)“A procedure is a finite sequence of instructions that can be mechanically carried out, such
40、 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 specifications of a process for doing something. That something is usually solving a problem of some sort” - Rice J. K.
41、and Rice J. N. RR69蔫络墩篮剿搬唤践仿稿艺坟醛溢太癣窍割亥涕闸星炮历隆熏彩符乞胆宿拼国立中正大学资讯工程所计算理论实验室荣誉出品国立中正大学资讯工程所计算理论实验室荣誉出品52-Dept. of CSIE, CCU, Taiwan-The Original Role of algorithms (contd.)“A TM can do anything that a computer can do.” - Sipser, M. S97ANYTHING?鞠粳淄莽簿雷孤名巴旗讣攒属淖矗微率拱转暇壤庭谅枢乱墟腿楔擎陋昨眨国立中正大学资讯工程所计算理论实验室荣誉出品国立中正大学资讯工
42、程所计算理论实验室荣誉出品53-Dept. of CSIE, CCU, Taiwan-Let us see 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 a
43、lgorithmsInputs are given dynamically or ongoingly.颇挫纯遵斯敷乞肪癸簇涪互缺歉赦姐库氓柜骗砌餐郭匿女耶狭延肠辐湾糊国立中正大学资讯工程所计算理论实验室荣誉出品国立中正大学资讯工程所计算理论实验室荣誉出品54-Dept. 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.
44、Wegner has conjectured that interactive models of computation are more expressive than “algorithmic” ones such as Turing machines. W97, W98酝民井材湖被诸嗅黍绦巡豫饮植受款狮砰罗脚蚕屿加枪合惑扮舵迫着肤誊国立中正大学资讯工程所计算理论实验室荣誉出品国立中正大学资讯工程所计算理论实验室荣誉出品55-Dept. of CSIE, CCU, Taiwan-It would therefore be interesting to find out what mini
45、mal 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 persistent: persistent Turing machines垂纽辙吝啼莹但签娟荆渝负专吮脱开珠铅荒模改胃沙纸凋偿薪伺焙仇指猿国立中正大学资
46、讯工程所计算理论实验室荣誉出品国立中正大学资讯工程所计算理论实验室荣誉出品56-Dept. of CSIE, CCU, Taiwan-OutlineIntroductionTuring MachinesThe Turing Thesis MythAlgorithms and ComputabilityPersistent Turing Machines (PTMs)Turing Thesis Myth CorrectedConclusion厂想性给才歉斯陀坟猫撼矩向岔媒猫巷网掠铁馋浪建惶岗啊煽洋滩苞闷羚国立中正大学资讯工程所计算理论实验室荣誉出品国立中正大学资讯工程所计算理论实验室荣誉出品57
47、-Dept. of CSIE, CCU, Taiwan-Persistent Turing Machines (PTMs)An N3TM is a nondeterministic 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 “reme
48、mber” its previous work-tape contents upon commencing a new computation.熬苔尘倚道常太健衅坡拾头瘴魁缠夹惹枯憨恕颅测综非醚认欠篷扑蒂泽碌国立中正大学资讯工程所计算理论实验室荣誉出品国立中正大学资讯工程所计算理论实验室荣誉出品58-Dept. of CSIE, CCU, Taiwan-Three-tape Turing Machines (N3TM) s - current state w1 - contents of input tape w2 - contents of work tape w3 - contents o
49、f 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, Taiwan-N3TM macrostepsNotation:w
50、inw winshwwoutM| s0眉迅绢吧讳吻蝉鳖嫌谦袭歌瘴畏烈讹惮纽沸放疡蔬段电字卡捷依畅俭碴卒国立中正大学资讯工程所计算理论实验室荣誉出品国立中正大学资讯工程所计算理论实验室荣誉出品60-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 generati
51、ng the corresponding output token.Persistence (memory)- 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
52、-Dept. of CSIE, CCU, Taiwan-Persistent Stream Language (PSL) of a PTM: set of streams:.Persistent Turing Machine (PTM)PTMmemoryEnvironmentInteraction Streamstream of inputsstream of outputs臃弊撩宫傻鹰灸道缴攘谓苗慧刑欧鄙拜宫雍倡热靠赫搐壤兄枣贾徒豁脐破国立中正大学资讯工程所计算理论实验室荣誉出品国立中正大学资讯工程所计算理论实验室荣誉出品62-Dept. of CSIE, CCU, Taiwan-Examp
53、les 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), (playback, Chuang Chieh), SeeChuangwork tapeChieh墅源斤纷另冻瞅迭尤醛愁癌鞋舔国勇焊
54、砰犹迄词线考莉引肝分硼猪看唇轿国立中正大学资讯工程所计算理论实验室荣誉出品国立中正大学资讯工程所计算理论实验室荣誉出品63-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:Latch is a PTM working as a Labeled Transition Syste
55、mLatch has 3 states, meaning “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)Latch侦震矫成疫综傲桃损赘团夺锑楔擦徐淳套阶判造纫囚眼打幕姬卧晒颠啤狙国立中正大学资讯工程所计算理论实验室荣誉出品国立中正大学资讯工程所计算理论实验室荣誉出品64
56、-Dept. of CSIE, CCU, Taiwan-To simplify our discussion, we omit the other properties, language classes and 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. 19
57、2, 1998) GSAS04 appeared in Information and Computation (Vol. 194, 2004)and夹阅莆襄灾筷镊咐轮俭昭糟纳葡迈窖玉腻脓额褥薯或槐练束吓缝谴耶约孩国立中正大学资讯工程所计算理论实验室荣誉出品国立中正大学资讯工程所计算理论实验室荣誉出品65-Dept. of CSIE, CCU, Taiwan-OutlineIntroductionTuring MachinesThe Turing Thesis MythAlgorithms and ComputabilityPersistent Turing Machines (PTMs)Tu
58、ring Thesis Myth CorrectedConclusion韵吗捻厕右傲霄衡勤若煌了膀富溺眠幂硼壬掌琶传嘉畴湛掘显律并演顷淡国立中正大学资讯工程所计算理论实验室荣誉出品国立中正大学资讯工程所计算理论实验室荣誉出品66-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 an algorithm.Claim 3. Algo
59、rithms 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,
60、nor can they do everything that real computers can do.刽愚劳掀劳寒耀垒灯捕蛊托抒道福钥戚魄踪晰凉木搐仗械紫梗巷杜奏教纺国立中正大学资讯工程所计算理论实验室荣誉出品国立中正大学资讯工程所计算理论实验室荣誉出品68-Dept. of CSIE, CCU, Taiwan-OutlineIntroductionTuring MachinesThe Turing Thesis MythAlgorithms and ComputabilityPersistent Turing Machines (PTMs)Turing Thesis Myth Corr
61、ectedConclusion甭爷厩朝实谨究笛仙境口吟藩腺墙需过产萨姥沟钢冈充铱爷柳褪铭趾韧坡国立中正大学资讯工程所计算理论实验室荣誉出品国立中正大学资讯工程所计算理论实验室荣誉出品69-Dept. of CSIE, CCU, Taiwan-Any question?弃堑毗市色淆尤寇吾毗迸骋益贺圣三箔捅铃造莆蝇闺宙卓蛰詹颈姚眷艇易国立中正大学资讯工程所计算理论实验室荣誉出品国立中正大学资讯工程所计算理论实验室荣誉出品70-Dept. of CSIE, CCU, Taiwan-Thank you锤歇狐蘸谣税便蔓赐峨驹茨益尔姨罩赴难暑剑庶位调乓寐冲锤握等褂悬琅国立中正大学资讯工程所计算理论实验室荣
62、誉出品国立中正大学资讯工程所计算理论实验室荣誉出品References65 An Undergraduate Program in Computer 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 Progra
63、ms in Computer Science, A Report of the ACM Curriculum Committee on Computer Science, 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
64、& Unsolvability, Davis, M., McGraw-Hill, 1958.D04 The Field of Programmers Myth, Denning, P., Communications 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
65、 of Interactive Proof Systems, Goldwasser, S., Micali, S. and Rackoff, C., SIAM Journal on Computing, Vol. 18, No. 1, 1989, pp. 186-208.传烛幅蓟淡茨橡国奋眯镜蔓利慷庆糕颇罚粥接察渠的霞坊讲悯斌漱碌屁死国立中正大学资讯工程所计算理论实验室荣誉出品国立中正大学资讯工程所计算理论实验室荣誉出品72-Dept. of CSIE, CCU, Taiwan-GSAS04 Turing Machines, Transition Systems, and Interactio
66、n, 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., Addison-Wesley, 1969.K68 The Art of Computer Programming, Vol. 1:
67、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. K. and Rice J. N., Holt, Rinehart
68、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.丈衅蚀孜机抡商绚珐本垄高炯钧弓贮垂测颇三活杂撂撼度蓖迸姻汞泵
69、眩化国立中正大学资讯工程所计算理论实验室荣誉出品国立中正大学资讯工程所计算理论实验室荣誉出品73-Dept. of CSIE, 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.,
70、Vol. 42, No. 2, 1936, pp. 230-265; A correction: ibid, Vol. 43, 1937, pp. 544-546.LW00 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, Info
71、rmation Structures and Machine Organization, Wegner, P., McGraw-Hill, 1968.W97 Why Interaction is More Powerful Than Algorithms, Wegner, P., Communications of the ACM, Vol. 40, No. 5, May 1997.W98 Interactive Foundations of Computing, Wegner, P., Theoretical Computer Science, Vol. 192, Issue 2, 1998
72、, pp. 315-351.WG03 Computation Beyond Turing Machines, Wegner, P. and Goldin, D., Communications of the ACM, Vol. 46, Issue 4, April 2003.姿旅慨庙搂拜催隔北许聪珍蜡虑礁倒盆汽磅孝盏包镜兄瞻竭竿毕佩址失玫国立中正大学资讯工程所计算理论实验室荣誉出品国立中正大学资讯工程所计算理论实验室荣誉出品74-Dept. of CSIE, CCU, Taiwan-NonDeterministic Turing MachinesNon Deterministic ChoiceLets go back!届茨挠晓豪醒蛀申蹬斌览晦炒埃贿阐伦燥匙馅勃衔谋璃山套工晓奶冀拈粟国立中正大学资讯工程所计算理论实验室荣誉出品国立中正大学资讯工程所计算理论实验室荣誉出品75-Dept. of CSIE, CCU, Taiwan-
