皇帝新脑 8.1分
读书笔记 第二章 算法与图灵机
不准拖延苏氨酸

欧几里德算法求最大公约数

我们让这两数中的一个被另一个除并取余数,在3654 中取出1365 的两倍, 其余数为924(=3654-2730)。我们现在用此余数即924 以及我们刚用的除数即1365 去取代原先的两个数。我们用这一对新的数重复上述步骤,用924 去除 1365,余数为441。这又得到新的一对441 和924,我们用441 除924,得 到余数42(=924-882),等等,直到能够被整除为止。我们把这一切如下 列出: 3654÷1365 给出余数924 1365÷924 给出余数441 924÷441 给出余数42 441÷42 给出余数21 42÷21 给出余数0。 我们最后用于做除数的21 即是所需要的最大公约数。
引自 第二章 算法与图灵机

---------------------

人们发现有些无理数 (非常引人注目地)根本不能由任何图灵机产生。能以这种方式产生的数 叫作可计算的(图灵1937)。那些不能的(实际上是绝大多数!)是叫作 不可计算的。
引自 第二章 算法与图灵机

---------------

希尔伯特问题:是否存在某种回答属于某一广泛的、但是定义得很好的集 合的所有数学问题的机械步骤?
引自 第二章 算法与图灵机

(我擦,这句话我都看不懂) ------------------ 费马最后定理:(x+1)^w+3+(y+1)^w+3=(z+1)^w+3

虽然费马以律师作为职业(并且是笛卡尔的同时代人),他却是那个时代最优秀的数学家。他宣称得到了这一断言的“真正美妙的证明”,但那里的空白太小写不下。 可惜迄今为止既没有人能够重新证明之,也没有人能找到任何和费马断言 相反的例子! “哥德巴赫猜想”即是这样的一个例子,它断言比2 大的任何偶数都 是两个质数之和。
引自 第二章 算法与图灵机

--------

不存在决定一台图灵机将来停止与否的普适算法。 一台特定的图灵机是否停止是一个定义完好的数学问题(反过来,我 们已经看到,各种有意义的数学问题可被重述成图灵机的停机问题)
引自 第二章 算法与图灵机
5
《皇帝新脑》的全部笔记 34篇
豆瓣
免费下载 iOS / Android 版客户端