第一部分 背景和歷史 第1章~第7章

術語卡

• 術語：奧卡姆剃刀（Occam's Razor）
• 印象：entia non sunt multiplicanda praeter necessitatem（如無必要勿增實體）跪妥。意思是簡約之法則，是由14世紀邏輯學家、圣方濟各會修士奧卡姆的威廉（William of Occam碳想，約1287年至1347年，奧卡姆（Ockham）位于英格蘭的薩里郡）提出的一個解決問題的法則，他在《箴言書注》2卷15題說“切勿浪費較多東西，去做‘用較少的東西堂淡，同樣可以做好的事情’“峭螅”換一種說法绢淀，如果關于同一個問題有許多種理論，每一種都能作出同樣準確的預言瘾腰，那么應該挑選其中使用假定最少的皆的。盡管越復雜的方法通常能作出越好的預言，但是在不考慮預言能力（即結果大致相同）的情況下蹋盆，假設越少越好费薄。
• 出處：維基百科

人名卡

• 人名：梅拉妮·米歇爾（Melanie Mitchell）
• 印象：Melanie Mitchell is a professor of computer science at Portland State University. She has worked at the Santa Fe Institute and Los Alamos National Laboratory. Her major work has been in the areas of analogical reasoning, Complex Systems, genetic algorithms and cellular automata, and her publications in those fields are frequently cited.[1]
  She received her PhD in 1990 from the University of Michigan under Douglas Hofstadter and John Holland, for which she developed the Copycat cognitive architecture. She is the author of "Analogy-Making as Perception", essentially a book about Copycat. She has also critiqued Stephen Wolfram's A New Kind of Science[2]
  and showed that genetic algorithms could find better solutions to the majority problem for one-dimensional cellular automata. She is the author of An Introduction to Genetic Algorithms, a widely known introductory book published by MIT Press in 1996. She is also author of Complexity: A Guided Tour (Oxford University Press, 2009), which won the 2010 Phi Beta Kappa Science Book Award.
  梅拉妮·米歇爾（Melanie Mitchell）是波特蘭州立大學計算機科學教授。她曾在圣菲研究所和洛斯阿拉莫斯國家實驗室工作怪嫌。她的主要工作是在類比推理义锥，復雜系統(tǒng)，遺傳算法和細胞自動機等領域岩灭，她在這些領域的出版物經(jīng)常被引用[1]她于1990年從密西根大學道格拉斯·侯世達（Douglas Hofstadter）和約翰·H·霍蘭（John Holland）獲得博士學位，她發(fā)展了Copycat cognitive architecture赂鲤。她是“Analogy-Making as Perception”的作者噪径，本質上是一本關于“COPYCAT”的書。她還批評了斯蒂芬·沃爾夫拉姆的“A New kind of Science”一種新科學数初，并表明遺傳算法可以為一維細胞自動機的多數(shù)問題找到更好的解決方案找爱。她是遺傳算法簡介的作者，1996年由麻省理工學院出版社出版的一本廣為人知的入門書泡孩。她還是Complexity: A Guided Tour復雜性導論（牛津大學出版社车摄，2009年）的作者，獲得了2010年菲貝卡“Phi Beta Kappa”獎。
• 出處：維基百科Melanie Mitchell

• 人名：馮·諾依曼 德語：John von Neumann （1903年12月28日－1957年2月8日）
• 印象：是出生于匈牙利的美國籍猶太人數(shù)學家吮播，現(xiàn)代計算機與博弈論的重要創(chuàng)始人变屁，在泛函、遍歷論意狠、幾何粟关、拓撲和數(shù)值分析等眾多數(shù)學領域及計算機學、量子力學和經(jīng)濟學中都有重大貢獻环戈。
  馮·諾伊曼從小就以過人的智力與記憶力而聞名闷板。馮·諾伊曼一生中發(fā)表了大約150篇論文，其中有60篇純數(shù)學論文院塞，20篇物理學以及60篇應用數(shù)學論文遮晚。他最后的作品是一個在醫(yī)院未完成的手稿，后來以書名《計算機與人腦》發(fā)布拦止，表現(xiàn)了他生命最后時光的興趣方向鹏漆。
  1926年，馮·諾伊曼以22歲的年齡獲得了布達佩斯大學數(shù)學博士學位创泄，相繼在柏林大學和漢堡大學擔任數(shù)學講師艺玲。
  1930年，馮·諾伊曼接受了普林斯頓大學客座教授的職位鞠抑。初到美國時饭聚，他在紐約對當?shù)鼐用癖硌葸^默記電話簿的驚人記憶力。1931年搁拙，馮·諾伊曼成為普林斯頓大學終身教授秒梳。1933年轉入普林斯頓高等研究院，與愛因斯坦等人成為該院最初的四位教授之一箕速，不須上課酪碘。這一年，他部分解決了希爾伯特第五問題盐茎，證明了局部歐幾里得緊群是李群兴垦。1937年成為美國公民，1938年獲博修獎字柠。
  1954年探越，馮·諾伊曼任美國原子能委員會委員。1954年夏天窑业，右肩受傷钦幔，手術時發(fā)現(xiàn)患有骨癌，治療期間常柄，依然參加每周三次的原子能委員會會議鲤氢，甚至美國國防部長搀擂，陸、海卷玉、空三軍參謀長聚集在病房開會哨颂。晚年，有學生請教他做事的方法揍庄，他說：“簡單（simple）咆蒿。”
• 著作:
  -1923. 《關于超限數(shù)的引入》(On the introduction of transfinite numbers), 346–54.
  -1925. 《集合論的一種公理化》(An axiomatization of set theory), 393–413.
  -1932. 《量子力學的數(shù)學基礎》(Mathematical Foundations of Quantum Mechanics), Beyer, R. T., trans., Princeton Univ. Press. 1996 edition: ISBN 978-0-691-02893-4.
  -1944. 《博弈論與經(jīng)濟行為》(Theory of Games and Economic Behavior), with Morgenstern, O., Princeton Univ. Press, online at archive.org. 2007 edition: ISBN 978-0-691-13061-3.
  -1945. 《就EDVAC的報告的首份手稿》(First Draft of a Report on the EDVAC) TheFirstDraft.pdf.
  -1963. 《馮諾依曼作品選集》(Collected Works of John von Neumann), Taub, A. H., ed., Pergamon Press. ISBN 978-0-08-009566-0.
  -1966. 《自復制自動機理論》(Theory of Self-Reproducing Automata), Burks, A. W., ed., University of Illinois Press. ISBN 978-0-598-37798-2.
  von Neumann, John. Continuous geometry. Princeton Landmarks in Mathematics. 普林斯頓大學出版社. 1998 [1960]. ISBN 978-0-691-05893-1. MR 0120174.
  von Neumann, John. Halperin, Israel, 編. Continuous geometries with a transition probability. Memoirs of the American Mathematical Society 34. 1981 [1937]. ISBN 9780821822524. MR 634656.
  -1958. 《計算機與人腦》(The Computer and the Brain, 去世后出版)
• 參考：維基百科

復雜系統(tǒng)的共性

• 個人一般都遵循相對簡單的規(guī)則蚂子，不存在中央控制或者領導者沃测。大量個體的集體行為產(chǎn)生出了復雜、不斷變化而且難以預測的行為模式食茎。
• 利用來自內(nèi)部和外部環(huán)境中的信息和信號蒂破，同時也產(chǎn)生信息和信號。
• 可以通過學習和進化過程進行適應别渔，即改變自身的行為以增加生存或成功的機會附迷。
  總結：復雜系統(tǒng)由大量組分組成的網(wǎng)絡，不存在中央控制哎媚，通過簡單運作規(guī)則產(chǎn)生出復雜的集體行為和復雜的信息處理喇伯，并通過學習和進化產(chǎn)生適應性。
  《復雜》第1章 P14

牛頓三大定律

• 任何情況下拨与，一切物體在不受外力作用時稻据，總保持靜止或勻速直線運動狀態(tài)。
• 物體的加速度與物體的質量成反比买喧。
• 兩個物體之間的作用力和反作用力捻悯，在同一條直線上，大小相等淤毛，方向相反今缚。

邏輯斯蒂映射（Logistic map）

x_t+1=Rx_t(1-x_t)
R=出生率和死亡率的效應
x=種群規(guī)模的“承載率”， x的初始值x₀介于0和1之間低淡。
R固定不變姓言，x_t迭代后會趨于一定數(shù)值。
R=2, x_t=0.5查牌∈缕冢“不動點”
R=2.5, x_t=0.6≈窖眨“不動點”
R=3.1, x_t在2個值0.5580141和0.7645665之間振蕩∫镩伲“吸引子”
R=3.49, x_t在4個值0.872,0.389,0.829和0.494之間振蕩胁孙。R介于3.4~3.5,振蕩周期從2增加到4
R介于3.54~3.55,振蕩周期增加到8
R介于3.564~3.565,振蕩周期增加到16
R介于3.5687~3.5688,振蕩周期增加到32
R約等于3.569946時唠倦，周期已趨于無窮大。
R等于大于3.569946時涮较，x的值不再進入振蕩稠鼻，它們會變成混沌。
將x₀狂票，x₁候齿，x₂···的值組成的序列稱為x的軌跡逐漸發(fā)散開，軌道極為敏感地依賴于x₀
邏輯斯蒂映射極為簡單闺属，并且完全是確定性：每個x_t值都有且僅有一個映射值x_t+1慌盯。然而得到的混沌軌道非常隨機。因此掂器，表面上的隨機可以來自非常簡單的確定性系統(tǒng)亚皂。
對于任何能產(chǎn)生混沌的R值，只要x₀有不確定性国瓮，不管精確到小數(shù)點后多少位灭必，最終都會在t大于某個值時變得無法預測。
總結：數(shù)學生物學家梅對這些驚人的特性進行了總結

• 明顯的不穩(wěn)定波動不一定表明環(huán)境的變化莫測或是采樣有錯誤乃摹；
• 在混沌鐘禁漓，不管初始條件有多接近，在足夠長的時間之后孵睬，它們的軌道還是會相互分開播歼，意味著即使我們的模型很簡單，所有的參數(shù)也都完全確定肪康，長期預測也仍然是不可能的荚恶。
• 參考：《復雜》2011， P33-41

費根鮑姆常數(shù)

• 物理學家費根鮑姆的發(fā)現(xiàn)讓倍周期之路得以在數(shù)學界聞名磷支。
• R值谒撼，表示指倍周期分叉點的數(shù)值
  R₁≈3.0 ======> 周期2¹=2
  R₂≈3.44949 ======> 周期2²=4
  R₃≈3.54409 ======> 周期2³=8
  R₄≈3.564407 ======> 周期2⁴=16
  R₅≈3.568759 ======> 周期2⁵=32
  R₆≈3.569692 ======> 周期2⁶=64
  R₇≈3.569891 ======> 周期2⁷=128
  R₈≈3.569934 ======> 周期2⁸=256
  ······
  R_∞≈3.469946
• 隨著周期增大，R值之間的距離越來越近雾狈。即R值增大廓潜，分叉之間的間隔越來越短。費根鮑姆計算了R值的收斂速度善榛，約等于常數(shù)4.6692016辩蛋。新的周期倍增比前面的周期倍增出現(xiàn)的速度快大約4.6692016倍。

• 他的理論在多個物理動力系統(tǒng)的實驗中得到了證實移盆，包括流體悼院、電路、激光和化學反應咒循。在這些系統(tǒng)中都發(fā)現(xiàn)了倍周器分叉据途，在這些實驗中很難準確測量分叉點R值绞愚，實驗得到的費根鮑姆常數(shù)也仍然界在接近4.6692016的誤差范圍之內(nèi)。

  
  
  image.png

混沌系統(tǒng)

• 對于其初始位置和動量的測量如果有極其微小的不精確颖医，也會導致對其的長期預測產(chǎn)生巨大的誤差位衩。即“對初始條件的敏感依賴性”
• 例子：即使很簡單的計算機氣象模型，也會有對初始條件的敏感依賴性熔萧，雖然有高度復雜的氣象計算模型糖驴，天氣預報也最多只能做到大致準確預測一個星期。
• 提出：物理學家李天巖（T.Y.Li）和約克（James Yorke）佛致。
• 普適性贮缕，“混沌中的秩序”
  • 突然的周期倍增被稱為分叉（bifurcation）。不斷分叉直至混沌的過程就是 “通往混沌的倍周期之路”晌杰。
  • 費根保姆常數(shù)：新的周期倍增比前面的周期倍增出現(xiàn)的速度快大約4.6692016倍跷睦。

熱力學定律

• 印象：是研究熱現(xiàn)象中物態(tài)轉變和能量轉換規(guī)律的學科；它著重研究物質的平衡狀態(tài)以及與準平衡態(tài)的物理肋演、化學過程抑诸。熱力學定義許多宏觀的變數(shù)（像溫度、內(nèi)能爹殊、熵蜕乡、壓強等），描述各變數(shù)之間的關系梗夸。熱力學描述數(shù)量非常多的微觀粒子的平均行為层玲，其定律可以用統(tǒng)計力學推導而得。
• 熱力學第零定律：在不受外界影響的情況下反症，只要A和B同時與C處于熱平衡辛块，即使A和B沒有熱接觸，他們?nèi)匀惶幱跓崞胶鉅顟B(tài)铅碍。這個定律說明润绵，互相處于熱平衡的物體之間必然具有相等的溫度。

• 熱力學第一定律：能量守恒定律對非孤立系統(tǒng)的擴展胞谈。此時能量可以以功W或熱量Q的形式傳入或傳出系統(tǒng)尘盼。熱力學第一定律表達式為：
  

• 熱力學第二定律：孤立系統(tǒng)熵（失序）不會減少──簡言之，熱不能自發(fā)的從冷處轉到熱處烦绳，而不引起其他變化卿捎。任何高溫的物體在不受熱的情況下，都會逐漸冷卻径密。這條定律說明第二類永動機不可能制造成功午阵。熱力學第二定律也可表示為熵增原理：
  
• 熱力學第三定律：完整晶體于絕對溫度零度時（即攝氏-273.15度），熵增為零享扔。
• 總結：熱力學第零定律定義了溫度這一物理量趟庄，指出了相互接觸的兩個系統(tǒng)括细，熱流的方向伪很。熱力學第一定律指出內(nèi)能這一物理量的存在戚啥，并且與系統(tǒng)整體運動的動能和系統(tǒng)與環(huán)境相互作用的勢能是不同的，區(qū)分出熱與功的轉換锉试。熱力學第二定律涉及的物理量是溫度和熵猫十。熵是研究不可逆過程引入的物理量，表征系統(tǒng)通過熱力學過程向外界最多可以做多少熱力學功呆盖。熱力學第三定律認為拖云，不可能透過有限過程使系統(tǒng)冷卻到絕對零度。
• 了解基本定律時应又，要注意前提條件宙项，針對什么“系統(tǒng)”，要明白“封閉系統(tǒng)”“孤立系統(tǒng)”“開放系統(tǒng)”的區(qū)別株扛。在“封閉系統(tǒng)”尤筐，第一定律就是能力守恒，第二定律就是熵總是不斷增加直至最大洞就。
• 參考：維基百科

熵

• 化學及熱力學中所指的熵（英語：Entropy）盆繁，是一種測量在動力學方面不能做功的能量總數(shù)。（對不能轉化成功的能量的度量）旬蟋。也就是當總體的熵增加油昂，其做功能力也下降，熵的量度正是能量退化的指標倾贰。熵亦被用于計算一個系統(tǒng)中的失序現(xiàn)象冕碟，也就是計算該系統(tǒng)混亂的程度。熵是一個描述系統(tǒng)狀態(tài)的函數(shù)匆浙，但是經(jīng)常用熵的參考值和變化量進行分析比較安寺，它在控制論、概率論吞彤、數(shù)論我衬、天體物理、生命科學等領域都有重要應用饰恕，在不同的學科中也有引申出的更為具體的定義挠羔，是各領域十分重要的參量。
• 這個熵的概念最初是由克勞修斯（Rudolph Clausius）于1865年定義埋嵌。
• 1877年破加，玻爾茲曼發(fā)現(xiàn)單一系統(tǒng)中的熵跟構成熱力學性質的微觀狀態(tài)數(shù)量相關。在宏觀尺度上的屬性（例如熱）是由微觀屬性產(chǎn)生（例如無數(shù)分子的運動雹嗦。）可以考慮情況如：一個容器內(nèi)的理想氣體范舀。微觀狀態(tài)可以以每個組成的原子的位置及動量予以表達合是。為了一致性起見，我們只需考慮包含以下條件的微觀狀態(tài)：（i）所有粒子的位置皆在容器的體積范圍內(nèi)锭环；（ii）所有原子的動能總和等于該氣體的總能量值聪全。玻爾茲曼并假設：S=klogW, S是熵，W是對應給定宏觀態(tài)的可能的微觀態(tài)的數(shù)量（這個被稱為玻爾茲曼原理的假定是統(tǒng)計力學的基礎辅辩。統(tǒng)計力學則以構成部分的統(tǒng)計行為來描述熱力學系統(tǒng)难礼。），k是“玻爾茲曼常數(shù)”玫锋，這個數(shù)用來將熵變成標準單位蛾茉。玻爾茲曼原理指出系統(tǒng)中的微觀特性（W）與其熱力學特性（S）的關系。
  根據(jù)玻爾茲曼的定義撩鹿，熵是一則關于狀態(tài)的函數(shù)谦炬。并且因為 W是一個自然數(shù)（1,2,3,...），熵必定是個非負數(shù)（這是對數(shù)的性質）节沦。
• 參考：《復雜》2011 P52-64 中舉例键思。維基百科熵

香農(nóng)信息

• 香農(nóng)的信息定義中有一個發(fā)送者向接收者發(fā)送信息，忽略信息的意義散劫，只考慮發(fā)送者向接收者發(fā)送信息的速度稚机。將宏觀狀態(tài)（發(fā)送者）的信息定義為可以由發(fā)送者發(fā)送的可能微觀狀態(tài)（可能信息的集合）的數(shù)量的函數(shù)。
• 香農(nóng)用信息源的熵定義信息量（這個熵的概念通常被稱為香農(nóng)熵获搏，以區(qū)別于玻爾茲曼給出的熵的定義）
• 信息量的定義為接收者在接收信息時體驗到的“平均驚奇度”赖条，其中“驚奇”意指接收者對于發(fā)送源將要傳送的信息的“不確定度”。
• 信息可以是通信的任何單位常熙，一個字母纬乍，一個詞，一句話裸卫，甚至是一個比特（0或1）仿贬，發(fā)送源的熵（信息量）用信息的可能性定義，而與信息的“意義”無關墓贿。

希爾伯特問題

• 德國數(shù)學大師希爾伯特(David Hilbert)于1900年在巴黎的國際數(shù)學家大會上提出來的茧泪，一共23個數(shù)學問題。1-6是數(shù)學基礎問題聋袋，7-12是數(shù)論問題队伟，13-18屬于代數(shù)和幾何問題，19-23屬于數(shù)學分析幽勒。
• 其中第2個（算術公理之相容性）和第10個問題（不定方程可解性）后來影響最大嗜侮。
• 這些問題可以分為三個部分
  • 數(shù)學是不是完備的？也就是說，是不是所有數(shù)學命題都可以用一組有限的公理證明或者證否锈颗。（被哥德爾解決）
  • 數(shù)學是不是一致的顷霹？是不是可以證明的都是真命題？（被哥德爾解決）
  • 是不是所有命題都是數(shù)學可判定的击吱？是不是對所有命題都有明確程序（definite procedure）可以在有限時間內(nèi)告訴我們命題是真是假淋淀？（被圖靈解決）

哥德爾不完備性定理

• 從算術著手，他證明姨拥，如果算術是一致的的绅喉，那么在算術中就必然存在無法被證明的真命題，也就是說叫乌，算術是不完備的。而如果算術是不一致的徽缚，那么就會存在能被證明的假命題憨奸。
• 舉例：命題A: 這個命題A是不可證的。假設命題A可證凿试，即它說它不可證排宰，即命題命題A為假。意味著證明了假命題那婉，從而算術上不一致（類似1+1=3）板甘。假設命題A不可證，就意味著命題A為真（因為它說它不可證）详炬，那就存在不可證的真命題盐类，從而算術上不完備。
• 延伸：說謊者悖論：“我正在說謊”或者“我所說的皆為假”呛谜。如果他確實在說謊在跳，那么他所說的就是真的，但如果他所說的就是真的隐岛，那么他就是在說謊猫妙。

圖靈機和不可計算性

• 圖靈機是英國數(shù)學家艾倫·圖靈于1936年提出的一種抽象計算模型，其更抽象的意義為一種數(shù)學邏輯機
• 圖靈機由三部分組成
  • 兩頭無限長的帶子聚凹，被分成許多方格（或地址）割坠，符號可以被寫入其中或從中讀出。
  • 可移動的讀寫頭妒牙，能從帶子上讀取符號或將符號寫到帶子上（改寫）彼哼。在任何時候，讀寫頭都處于一組狀態(tài)中的一個单旁』Ω幔可以左右移動，
  • 指示讀寫頭下一步如何做的一組規(guī)則，進入新狀態(tài)蔫饰。

進化論起源與發(fā)展

• 在西方琅豆，直到18世紀，都是神創(chuàng)造萬物的思想篓吁。在古希臘和印度曾有些哲學家認為人類可能是從其他物種變化而來茫因。
• 在18世紀中葉，法國動物學家布馮（George Louis Leclerc de buffon）出版了《自然歷史學》(Historie Naturelle),書中描述了各種物種之間的相似之處杖剪。
• 查爾斯·達爾文的祖父厄拉斯莫斯·達爾文（Erasmus Darwin）認為所有物種都是由同一祖先進化而來冻押。
• 法國貴族，也是植物學家拉馬克在1809年出版的《動物哲學》（Philosophie Zoologique）提出：新的物種從非生命物質中自發(fā)產(chǎn)生盛嘿，然后物種會通過“獲得性狀的遺傳”不斷進化洛巢。生物在生命過程中適應環(huán)境，而這種獲得的適應性會直接遺傳給后代次兆。（20世紀初稿茉，拉馬克的理論已沒有影響）
• 1858年，達爾文收到英國另一位自然學家華萊士（Alfred Russell Wallace）的手稿芥炭，《論變種無限地偏離原始類型的傾向》（On the Tendency of Varieties to Depart Indefinitely from the Original Type）漓库。
• 1858年夏在，達爾文和華萊士的合作成果在林奈學會宣讀园蝠。
• 1859年底渺蒿，達爾文出版了400多頁的《物種起源》。
• 1865年孟德爾關于遺傳率的豌豆實驗論文《植物雜交實驗》彪薛，直到1900年才被承認茂装，推翻了當時盛行的“混合遺傳”的觀念-認為子代的性狀會是父母性狀的平均。
• 直到20世紀20年代陪汽，人們認識到達爾文與孟德爾的理論并不矛盾训唱，而是互補的。
• 費希爾（Ronald Fisher）挚冤、霍爾丹(J.B.S.Haldane)和賴特(Sewall Wright)證明了達爾文與孟德爾的理論實際上是一致的况增，還提供了數(shù)學框架--群體遺傳學（population genetics）。他們?nèi)槐徽J為是現(xiàn)代綜合的奠基者训挡。群體遺傳學與達爾文理論和孟德爾遺傳學共同形成了“現(xiàn)代綜合The Modern Synthesis
• 20世紀60年和70年代澳骤，古生物學家古爾德（Stephen Jay Gould）和埃爾德雷奇（Niles Eldredge）對現(xiàn)代綜合提出質疑和批評。認為現(xiàn)代綜合的生物形態(tài)漸進論不符合實際的化石記錄澜薄；認為歷史偶然和生物約束的作用很重要为肮；大尺度的進化現(xiàn)象無法用微觀的基因變異過程和自然選擇解釋。
• 參考：《復雜》2011 P88-110

達爾文理論主要思想：

• 存在進化肤京，所有物種都來自共同的祖先颊艳。生命的歷史就是物種呈樹狀分化茅特。
• 一旦生物的數(shù)量超過了資源的承載能力，生物個體就會為資源競爭棋枕，從而導致自然選擇白修。
• 生物性狀會遺傳變異，變異在某種意義上是隨機的-變異并不必然會增加適應性。能夠適應當前環(huán)境的變異更有可能被選擇，即更有可能存貨苦丁，并將這新的性狀遺傳給后代，從而讓后代中具有這種性狀的個體增加祖很。
• 進化是通過細微的有利變異不斷累積逐漸形成的。

關于圖靈機與判定問題的理解

• 前提漾脂，信息有雙重屬性假颇，既能作為指令，又能作為數(shù)據(jù)（字符串）符相。
• 判定問題：是否有明確程序可以判定任意命題是否為真 （圖靈證明這個假設有矛盾）
• 基于判定問題拆融，給出圖靈命題：圖靈機M對于給定輸入I會在有限步后停機。
• 設定存在一個有判定作用的圖靈機H啊终，對于任何給定的圖靈機M（M是指令，它的表現(xiàn)形式也是字符串）和輸入I（字符串）傲须，都能在有限時間內(nèi)判斷M對于輸入I是會停機還是進入死循環(huán)蓝牲，停不了機。字符串是0/1字集泰讽。判定器本身必須總是能停機的例衍，無論無論M對于I會停機，還是不會停機已卸，即輸出字符串0就停機佛玄，或輸出1就停機，記為H（M累澡，I）梦抢。（只有第三種情況，停不了機愧哟，即無法判定奥吩，可以用來檢查圖靈機的死循環(huán)。）
• 以判定器為基礎蕊梧，把圖靈機M也作為輸入I霞赫，記為H' （M，M）肥矢，就是說M又作為描述指令端衰，又作為字符串（這個描述指令就是字符串）。類似于，一個統(tǒng)計字符數(shù)字的程序來統(tǒng)計該程序本身的字符數(shù)字旅东。H'的含義就是判定M處理它自身的編碼M時會不會停機灭抑。H'則只有當“M對于編碼M不會停機”時才會停機，當“M對于編碼M會停機”--H’就進入死循環(huán)玉锌，永不停機名挥，即無法判定。
• 假設H'對于輸入H‘不會停機主守。上一條說H'(M, M)時禀倔，當“M對于編碼M會停機”--H’就進入死循環(huán)，永不停機参淫；則H'對于輸入M不能停機救湖，意味著M對于輸入M不會停機。則H'對于輸入H'不會停機意味著H'對于輸入H'會停機涎才。（只是把M替換成H'的程序字符）只有在M對于M不會停機時H‘才會停機鞋既。又意味著H'對于H'不會停機，H'對于H’就會停機耍铜。前后產(chǎn)生悖論邑闺。
• 總結：如果存在一個算法可以判斷任意一個圖靈機在任意一個輸入上是否停機，那么就可以設計這樣一臺圖靈機：讓它首先執(zhí)行該算法判斷自己在輸入上是否停機棕兼。如果得出結論是停機陡舅，則讓它進入一個死循環(huán)永不停機；如果結論是不停機伴挚，則讓它立即停機靶衍。這樣這臺圖靈機就在它停機的輸入上不停機；在它不停機的輸入上停機茎芋，產(chǎn)生悖論颅眶。結論只能是：不存在這樣的算法。

金句卡
一切偉大的真理開始時都是大逆不道---蕭伯納（George Bernard Shaw）《安納揚斯卡田弥，布爾什維克女皇》