HPM&S 计算学科中的经典问题 ( 三 ) Great Ideas in Computer Science （ 3 ） 李波 weibo.com/bobbleee 计算机教学实验中心 高效能建模与仿真研究小组 西安交通大学 2012 年 11 月

HPM&S 1. 尺规作图 - 三等分角 2. 希尔伯特的第十个问题 3. 考拉兹猜想 4. 王氏铺砖问题 5. Bare Bones 语言 6. Godel 编码 7. 通用图灵机 8. 停机问题 9. 冯. 诺伊曼结构

HPM&S Edsger Dijkstra “ 我们所使用的工具深刻地影响 我们的思考习惯，从而也影响了我 们的思考能力 ” Edsger Dijkstra “ 我们所使用的工具深刻地影响 我们的思考习惯，从而也影响了我 们的思考能力 ” 不可解问题 ，算法，停机问题

HPM&S 尺规作图 - 三等分角 三等分角是古希腊几何尺规作图当中的名题，和化圆为方、 倍立方问题被并列为古代数学的三大难题之一。化圆为方 倍立方 在只用圆规及一把没有刻度的直尺将一个给定角三等分 现在已经证明，这个问题是没有办法在给定的条件之下完成的。 如果放宽限制，使用有刻度的直尺，则三等分角是可能的。 用有刻度的直尺（二刻尺）

HPM&S 希尔伯特的第十个问题 不定方程 ( 又称为丢番图方程 ) 的可解性。这是希尔伯特于 1900 年在巴黎 的国际数学家大会演说中，所提出的 23 个重要数学问题的第十题。这 个问题是 “ 对于任意多个未知数的整系数不定方程，要求给出一个可行 的方法 (verfahren) ，使得借助于它，通过有限次运算，可以判定该方程 有无整数解 ” 。 在整数域求解以下方程 2x-2y=1 3x=6 7x-17y=1 一般而言，上述的 “ 整数域上的代数方程 ” 定义为， P=0 ，其中 P 是系统 为整数的多项式，包含一个，两个或多个未知数。例如 7x 2 - 5xy- 3y 2 + 2x + 4y- 11 = 0 和 x 3 + y 3 = z 3 。需要解决的问题是：给定方程 P(x, y,...) = 0 ，如何判定方程在整数域内是否有解，如果有，如何高效找到所有解？ 这类问题称为丢番图方程求解问题。

HPM&S Verfahren- algorithm 希尔伯特在定义第十问题时用的德语 verfahren （方法），就是英文所 谓的算法 algorithm 。 对于算法的概念人们是不陌生的，例如远在古希腊时代，人们就知道 可以使用辗转相除法，求两个自然数的最大公约数。还有，任给一个 自然数，也存在着一个方法，在有限步骤内，可以判定这个数是不是 质数。 虽然人们很早就有了算法的朴素概念，但对于到底什么是可行的计算， 仍没有精确的概念。 一个问题的可解与不可解究竟是什么含意，当时的人们还不得而知。 为了研究第十问题，必须给予算法精确化的观念。 这点还有赖于数理逻辑学对可计算性理论的发展，才得以实现。

HPM&S 任何一个正整数，如果它是奇数，则对它乘 3 再加 1 ，如果它是偶数，则对它除以 2 ，如此循 环，最终都能够得到 1 。 取一个数字如 n = 6 ，根据上述数式，得出 6→3→10→5→16→8→4→2→1 步骤中最高的数是 16 ，共有 8 个步骤 取一个数字如 n = 6 ，根据上述数式，得出 6→3→10→5→16→8→4→2→1 步骤中最高的数是 16 ，共有 8 个步骤 如 n = 27 ，根据上述数式，得出 : 27→82→41→124→62→31→94→47→142→71→214→107→322→161→484→242→121→364→182 →91→274→137→412→206→103→310→155→466→233 →700→350→175→526→263→790→395→1186→593→1780→890→445→1336→668→334→167→ 502→251→754→377→1132→566→283→850→425→1276 →638→319→958→479→1438→719→2158→1079→3238→1619→4858→2429→7288→3644→1822 →911→2734→1367→4102→2051→6154→3077→9232 →4616→2308→1154→577→1732→866→433→1300→650→325→976→488→244→122→61→184 →92→46→23→70→35→106→53→160→80→40→20→10 →5→16→8→4→2→1 。 ( 步骤中最高的数是 9232 ，共有 111 个步骤 ) 如 n = 11 ，根据上述数式，得出 11→34→17→52→26→13→40→20→10→5→16→8→4→2→1 步骤中最高的数是 52 ，共有 14 个步骤 如 n = 11 ，根据上述数式，得出 11→34→17→52→26→13→40→20→10→5→16→8→4→2→1 步骤中最高的数是 52 ，共有 14 个步骤 考拉兹猜想 - Collatz conjecture

HPM&S n 小于 1 万，步骤中最高的数是 6171 n 小于 1 亿，步骤中最高的数是 ，共有 949 个步骤； n 小于 10 亿，步骤中最高的数是 ，共有 986 个步骤。 def collatz(n) print n if n.odd? and n > 1 collatz(3n + 1) else if n.even? collatz(n / 2) 目前已经有分布式计算在进行验证。到 2009 年 1 月 18 日，已验证正整数到 20 × 2 58 = 5,764,607,523,034,234,880 ，也仍未有找到例外的情况。 但是这并不能够证明对于任何大小的数，这猜想都能成立。

HPM&S 考拉兹猜想 - 与停机问题 在程序中使用 Loop 语句不当，可能导致程序不能结束（停机），例如 下面程序永远是不会终止的。 X = 1; while X ; 例如考虑以下程序，请问当 n>= 1, 程序是否会终止。 while ( n > 1) if even(n) n = n/ 2; else n = n * 3 + 1; 可以简单地给出几个测试用例，当 n=1 、 2 、 3 、 4 、 5 、 6 、 8 、 10 时终止 停机问题（ Halting problem ）是图灵巧妙构思出来的一个问题。问题 具体表示为： “ 你能写出一个程序吗？该程序可以测试任意一个由哥德 尔数表达的程序是否会终止 ” 。停机问题是不可解的（ Halting problem is not solvable ）。该结论可采用反证法得证。

HPM&S 王氏铺砖问题

HPM&S Wang Tiles 或 Wang dominoes 王氏铺砖问题是美籍华人逻辑学家王浩（ Hao Wang ）在 1961 年提出来 的。有 13 种彩色地砖如图所示，铺设规则是地砖不能旋转或镜像，并 且共享边的两块地砖颜色相同。 王氏铺砖问题是能否将一个平面用上述 13 种地砖按照铺设规则铺满 （ Can you tile the entire plane with copies of the following? ）。 1966 年 Robert Berger 证明了这个算法是不存在的，故这个问题是不可 判定的。

HPM&S Statements in simple language Increment statement: incr X Decrement statement: decr X Loop statement: while X { Actions } 通用 Bare Bones 语言

HPM&S Power of the Simple Language The simple language with only three statements is as powerful as any sophisticated language in use today, such as C. Here we show how we can simulate several statements found in some popular languages. We call each simulation a macro and use it in other simulations without the need to repeat code.

HPM&S Macros in the Simple Language First Macro: X  0 Second Macro: X  n while X { decr X } X  0 incr X … incr X

HPM&S Macros in the Simple Language Third Macro: Y  X Y  0 TEMP  0 while X { incr Y decr X incr TEMP } while TEMP { decr TEMP incr X }

HPM&S Macros in the Simple Language Fourth Macro: Z  X + Y Z  X TEMP  Y while TEMP { incr Z decr TEMP }

HPM&S Macros in the Simple Language Fifth Macro: Z  X * Y Z  0 TEMP  Y while TEMP { Z  Z + X decr TEMP }

HPM&S Macros in the Simple Language Sixth Macro: Z  X ** Y Z  1 TEMP  Y while TEMP { Z  Z * X decr TEMP }

HPM&S Macros in the Simple Language Seventh Macro: comp ( X ) complements If the value of X is 0, change it to 1. If it is not 0, change it to 0. TEMP  1 while X { X  0 TEMP  0 } while TEMP { incr X decr TEMP }

HPM&S Macros in the Simple Language Eighth Macro: if X then A1 else A2 TEMP  X while TEMP { A1 TEMP  0 } TEMP  X comp (TEMP) while TEMP { A2 TEMP  0 }

HPM&S Simulation of Simple Language Write programs (create transition tables) that implement the statements of the Simple Language. Increment statement Decrement statement Loop statement

HPM&S Figure 17-4 Transition state Four states : A, B, C, D.

HPM&S Increment statement Transition diagram for incr X

HPM&S Transitional table for incr X statement Current State StartIncr Forward Added Backward Write # 1 1 & same as read # New State Forward Added Backward StopIncr Read # 1 & any not # # Move  

HPM&S Steps in incr X statement

HPM&S Decrement statement Transition diagram for decr X

HPM&S Transitional table for decr X statement Current State Current State StartDecr Forward Delete Backward Write Write # 1 blank & same as read # New State New State Forward Delete Backward StopDecr Read Read # 1 & 1 not # # Move Move  

HPM&S Transition diagram for the loop statement

HPM&S Transitional table for the loop statement Current State Current State StartLoop Check Forward … EndProcess Backward Read Read # not 1 1 not & & … any not # # Move Move    none …  none New State New State Check StopLoop Forward StartProcess … Backward Check Write Write # same as read 1 same as read & … same as read #

HPM&S Conclusion Any problem that can be solved by the Simple Language can also be solved by the Turing machine. Is there a problem solvable by the Turing machine that is not solvable by the Simple Language? We can not prove it now. Church thesis: the Simple Language and the Turing machine are equivalent. We believe it.

HPM&S Godel numbers In theoretical computer science, an unsigned number is assigned to every program that can be written in a specific language. Programs can be used as a single data item as input to another program. Programs can be referred to by just their integer representations. The numbering can be used to prove that some problems can not be solved by a computer.

HPM&S Code for symbols used in the Simple Language Symbol Hex Code Hex Code Hex Code Hex Code Symbol incr decr while { } x Hex Code Hex Code A B C D E F

HPM&S Representing a program Example 1 What is the Godel number for the program incr X? Solution incr X A F 175 (in decimal)

HPM&S Interpreting a number Example 1 Interpret 3058 as a program. Solution 3058 B F 2 decr X 2

HPM&S Universal Turing machine - Wikipedia In computer science, a universal Turing machine (UTM) is a Turing machine that can simulate an arbitrary Turing machine on arbitrary input. The universal machine essentially achieves this by reading both the description of the machine to be simulated as well as the input thereof from its own tape. Alan Turing introduced this machine in 1936–1937. This model is considered by some (for example, Martin Davis (2000)) to be the origin of the stored program computer—used by John von Neumann (1946) for the "Electronic Computing Instrument" that now bears von Neumann's name: the von Neumann architecture. It is also known as universal computing machine, universal machine (UM), machine U, U.

HPM&S Halting problem In programs, a repetition construct may never terminate (halt). For example, the following program never terminates. X  1 while X { }

HPM&S Can you write a program that tests whether or not any program, represented by its Godel number, will terminate? No. A Classical Programming Question: Halting problem

HPM&S Halting problem is not solvable Proof by contradiction ( 矛盾証法 ) Step 1: Assume that a program, called Test, exists.

HPM&S Step 2: Create another program called Strange that is made of two parts: a copy of Test at the beginning an empty loop at the end

HPM&S Step3:Now having made the program Strange, we test this program with itself as input. If we assume that Test exists, we have the following contradictions: This proves that the Test program cannot exist. The halting problem is unsolvable. This proves that the Test program cannot exist. The halting problem is unsolvable. 停机问题本质是一阶逻辑的不自恰性和 不完备性。 类似的命题有理发师悖论、全能悖论等。 停机问题本质是一阶逻辑的不自恰性和 不完备性。 类似的命题有理发师悖论、全能悖论等。

HPM&S Complexity of solvable problems One way to measure the complexity of a solvable problem is to find the number of operations executed by the computer when it runs the program. Big-O notation For example: n : the number of input data Polynomial problems: O(1), O(logn), O(n), O(nlogn), O(n 2 ),…, O(n k ),… Non-polynomial problems: O(2 n ), O(n!),…

HPM&S Key terms Controller Decrement statement Godel number Hexadecimal digit Increment statement Loop statement macro Non-polynomial problem Polynomial problem Solvable problem Tape Turing machine Unsolvable problem

HPM&S 几十年来，计算机的制造技术都是基于科学家冯 · 诺依曼 1946 年 提出的 “ 存储程序 ” 概念（ 1946 年发表论文 “ 电子计算机装置逻辑结 构初探 ” ）。这样的计算机称为冯 · 诺依曼体系结构计算机。 冯 · 诺依曼体系结构的思想可以概括为以下几点： 几十年来，计算机的制造技术都是基于科学家冯 · 诺依曼 1946 年 提出的 “ 存储程序 ” 概念（ 1946 年发表论文 “ 电子计算机装置逻辑结 构初探 ” ）。这样的计算机称为冯 · 诺依曼体系结构计算机。 冯 · 诺依曼体系结构的思想可以概括为以下几点： 冯 · 诺依曼体系结构 （ 1 ）由运算器、存储器、控制器、输入设备和输出设备等五 大基本部分组成计算机系统，并规定了这五部分的基本功能。 （ 2 ）计算机内部采用二进制来表示数据和指令。 （ 3 ）将程序数据存入内部存储器中，计算机在 工作时可以自动逐条取出指令并加以执行。

HPM&S 计算机的基本工作原理为存储程序和执行指 令。示意如下： 运算器运算器 运算器运算器 控制器控制器 控制器控制器 存储器 输入设备 输出设备 CPU 控制指令 取数据取数据 取数据取数据 存数据存数据 存数据存数据

HPM&S 讨论 - 冯. 诺伊曼的伟大之处 认识 基于通用图灵机建造的计算机都是在存储器中存储数据。 在 年期间，冯. 诺伊曼指出：鉴于程序和数据 在逻辑上是相同的，因此程序也能存储在计算机的存储 器中。 工程 简化：指令的顺序执行。指令一条接一条按顺序执行。 即使跳转指令可以请求控制器跳转之前或之后的指令， 这并不意味着指令没有按照顺序执行。 Data as code, Code as data

HPM&S 谢谢，请批评 祝您 一切顺利