图灵与停机问题 - Computerphile
Turing & The Halting Problem - Computerphile
频道:Computerphile · 时长:6:14 · 发布:2014-08-21 · 播放:921555
简介
Computerphile 的一期视频,诺丁汉大学的 Mark Jago 讲解图灵的停机问题,以及它如何催生了现代计算机的蓝图。
HN 为什么推荐
被推荐为对停机问题及其与可判定性关联的简短、清晰解释。
这里有一个关于它的短视频 — HN, 2021
中文字幕节选
今天我们要讨论一个逻辑学中的问题 以及在解决这个问题的过程中, 阿兰·图灵几乎在不经意间发明了现代数字计算机。 让我们回到20世纪初,当时数学家们 提出了这个问题——在逻辑学中,我们感兴趣的是找出“这些前提 是否蕴含这个结论?”前提是你在论证中一开始就有的东西 它们是你——你一开始就知道的东西,或者你的假设,而 结论是你想要确立的东西,是你通过论证 推理得出的东西,我们想知道是否存在一种检验方法能告诉我们 是的,这些前提确实蕴含或不蕴含 这个结论。是否存在一种自动的方法来找出 它们是否蕴含这个结论? 这就是那个问题,它被称为判定问题。 数学家们想弄清楚“判定问题是否有答案 对于一阶逻辑而言?” 那是你在大学哲学或数学课程中学到的那种逻辑 所以很多数学家都在试图弄清楚一阶逻辑是否可判定 也就是说我们能否自动检验前提是否蕴含结论 阿兰·图灵是最早发现一阶逻辑不可判定的人之一。 要证明这一点 在概念上真的很难,因为你必须能够证明没有任何 可能的程序能给出答案,但你怎么做到呢?你如何证明 关于每一个可能程序的某种性质?你不可能一个一个地运行每个程序 但图灵想出了一个绝妙的解决方案,他的想法大致是这样的 假设我们有一个程序,让我们把它画成一个黑箱 它会接收一些输入,并给我们一些输出 我们的程序要解决某个问题,比如“这些前提 是否蕴含这个结论?”我们问它一个问题,它会给我们一个答案 是或否 现在我们可以问另一个问题,让我们看看所有那些可能的 程序,我们目前只是把它们当作黑箱来看待,我们可能 想知道这个程序在给定某个输入时是否会给我们一个答案 还是会永远运转下去,永远不给我们答案,也就是说它 是会停机还是不会停机 最终。所以想想你的电脑在运行,你想让它给你一个 答案,不管这个答案是好是坏 总比没有答案好。没有答案意味着电脑会一直 永远永远地循环运转,你永远不知道它是会 今天完成、明天完成还是永远不会完成 所以停机是好事。那么我们可以问另一个问题:给定某个程序 和某个输入 它最终会停机吗?事实证明,我们的逻辑问题 “这些前提是否蕴含这个结论?”与这个停机问题非常相似 事实上,如果我们能解决逻辑问题,那么我们就能解决停机问题 这个程序在这个输入上会停机吗?所以图灵证明中巧妙的部分是 证明任何机器无论多么聪明都不可能解决 停机问题,也就是告诉我们一台给定的机器在给定 输入下是否会停机——下面就是他如何做到的 假设我们有一台机器或一个程序能为我们解决这个问题 它能解决停机问题,别担心它是怎么工作的,让我们就 把它当作一个黑箱,接收一台机器的描述和一个输入 然后给我们一个答案 是的,它会停机,或者不,它不会停机。就假设这是可能的 把那台机器叫做“h”,代表停机问题——如果你给我那台机器 我可以把它改造成一台不同的机器,像这样 我在上面加一些额外的部件,这样如果它给我一个“是”的答案 我就让它永远循环,永不停止
HN 上的讨论
>比如什么?停机问题(我认为?)是标准的例子。这里有一个关于它的短视频 [VIDEO] — gammalost, 2021-06
举一个实际的例子,哥德尔的不完备性与计算机科学中的可判定性问题直接相关。Computerphile讨论了这个光荣的说谎者悖论机器[0]。[0] [VIDEO] — mar77i, 2019-12
不,这完全是软件问题,因为你可以创建任何智能合约,并且它可以调用任何其他合约。在交易最终确认后知道和在事先预测之间存在区别,而后者正是你想要阻止交易的时候。[VIDEO] — verdverm, 2022-08
在我看来,这其实不是软件问题。不过你的计划方向是对的。我们已经知道,确保软件没有漏洞和缺陷几乎是不可能的。我们必须面对一个事实:安全的软件是可能的,但极其困难,且很难常规实现。由于停机问题[0]等众所周知的计算机科学问题,以及我完全不了解的更多问题,唯一的替代方案是像飞机[1]那样进行极其彻底的验证。问题在于,与航空航天和其他关键控制系统不同,我们无法像那些关键系统那样严格地定义软件安全问题。这样做会破坏我们通用技术解决方案的优势。我之所以说这仍然不是软件问题,是因为:在一个又一个令人不安的安全故障案例中,只有少数组织上的共性将它们联系在一起。一次又一次,出现令人震惊的错误配置、偷工减料、摒弃最佳实践、忽视警告、流程被无视或缺失并被掩盖。正如人们所指出的,高管们选择复选框式的银弹妙招,因为他们能理解“一个问题一个解决方案”的价值主张,并且容易向利益相关者传达。他们完全无视也不关心真正提供… — cartoonworld, 2021-07
相关视频
- Ruby Conf 12 - Y Not- 函数式编程历险记 by Jim Weirich · Confreaks · 53:21
- 28c3:不安全性的科学 · 28c3 · 59:23
- Philip Wadler 的“命题即类型” · Strange Loop Conference · 42:43
- Break Me00 The MoVfuscator 将mov变成令人崩溃的逆向工程噩梦 Christopher Domas · Adrian Crenshaw · 46:19
- 数学的根本缺陷 · Veritasium · 33:59
- 论PowerPoint的图灵完备性(SIGBOVIK) · Tom Wildenhain · 5:33
- 生命中的生命 · Phillip Bradbury · 1:30
- Lambda演算 - Lambda演算基础与JavaScript函数式编程 · Fullstack Academy · 1:02:15
- 所有的数 - Numberphile · Numberphile · 14:26
- P vs. NP 与计算复杂性动物园 · hackerdashery · 10:44
- Ruby Manor 3 - 用一无所有编程 by Tom Stuart · Confreaks · 40:49
- David Beazley - 从零开始构建Lambda演算 - PyCon 2019 · PyCon 2019 · 3:26:34
- 计算机科学中的伟大不实用想法:PowerPoint 编程 · Tom Wildenhain · 51:32
- Matt Might - 赢得错误之战:解决停机问题和治愈癌症 · Curry On! · 48:36
- Stephen Wolfram:元胞自动机、计算与物理 | Lex Fridman 播客 #89 · Lex Fridman · 3:11:08
- 让我们 #TalkConcurrency 小组讨论与 Tony Hoare 爵士、Joe Armstrong 和 Carl Hewitt · Erlang Solutions · 1:06:44