Philip Wadler 的“命题即类型”
"Propositions as Types" by Philip Wadler
频道:Strange Loop Conference · 时长:42:43 · 发布:2015-09-26 · 播放:143868
简介
Philip Wadler 在 Strange Loop 上关于命题即类型的演讲,探讨逻辑与计算之间的联系(柯里-霍华德对应)。他追溯了 Church、Godel 和 Turing 的历史,并展示了它如何塑造了定理证明器和编程语言。
HN 为什么推荐
HN 认为这是对逻辑与函数式编程为何相关联的有趣且令人大开眼界的介绍,并且经常在最喜欢的科技演讲帖子中被选中。
我度过的最棒的约40分钟。 — HN, 2017
编程语言设计 · 可计算性与复杂性理论 · 逻辑与形式化方法
中文字幕节选
你们准备好了解可计算性这个滑稽的主题了吗 [掌声] 理论 算法是计算机遵循的一系列指令,现在你们都认为 计算机是机器,但在很长一段时间里,计算机指的是人 执行算法的人,算法可以追溯到ID的 古典希腊时期的元素,以及同名的Alaris 在9世纪的波斯,但正式的数学定义直到 20世纪才出现,当时有Alonzo Church Kurt Gödel和Alan Turing的提议,都在一年之内 相继出现,就像公交车一样,你等了2000 年才等到有效可计算性的定义,然后三个同时 出现 为什么这会发生,所以在20世纪初 形式逻辑的最主要支持者之一是David Hilbert,在哥廷根 他想做的是让所有数学家失业,他 想要的是一个算法,给定形式逻辑中的一个陈述, 就能确定该陈述是真还是假,这被称为 判定问题,因为用德语听起来好多了,它只是意味着决策 问题 Hilbert所依赖的是逻辑是 完备的,意味着每个可证明的陈述都是真的,每个真的陈述 都是可证明的,听起来合理吧,当然除了1930年在 维也纳,Kurt Gödel发表了他的不完备定理证明,这意味着 他,用一个专业术语来说, 完蛋了,所以Gödel展示的是,任何强大到足以表示 算术的逻辑都可以编码以下陈述:这个陈述不可证明, 他这样做的方式是使用一种称为Gödel编号的巧妙技术,将 陈述和证明编码为数字,这就是为什么他依赖算术,所以不要 担心他是如何做到的细节,尽管它是世界上 最早的功能程序之一,嗯,但想想这个陈述:这个陈述 不可证明,对吧,一旦你写下这个陈述, 你就麻烦了,为什么,嗯,对吧,所以这很像我们听到的 说谎者悖论,只是现在它变成了可证明性,那么会发生什么,如果它是假的,那么它 就是可证明的,你就证明了一个假的东西,这真是坏消息, 你不想那样做,所以另一种选择是它是真的,但现在你必须有一个 真的但不可证明的陈述,所以这没那么糟糕,但仍然很 烦人,尤其是如果你是Hilbert,现在只要 人们认为判定问题会有解决方案,你就不需要 算法的正式定义,你只需写下那个 解决方案的算法,就像Potter法官对色情的定义:我 看到就知道,但如果你的目标是展示判定问题是 不可判定的,那么你需要算法的正式定义,这样你才能展示没有 算法会起作用,所以竞赛开始了,第一个解决方案是由 普林斯顿的Alonzo Church提出的,他想出了这个叫做Lambda演算的东西,在 1932年,到1936年他已经用它来展示,是的,如果算法是你能在 Lambda演算中表达的东西,那么判定问题就是不可判定的, 他实际上是通过另一个不可判定的东西来做到这一点的,我们现在 称之为停机问题,这就是Lambda演算的完整 定义,比你们那些使用像 C或Java语言的人要简洁得多,它只有三个构造:变量、函数定义和函数 应用,对吧,它是世界上最酷的编程语言,因为它是在 有计算机之前十年定义的,多年来我和我的
HN 上的讨论
Philip Wadler 教授有一个非常精彩的演讲,题为《Propositions as Types》,介绍了 Curry-Howard 对应、其背后的一些历史以及后续的思想。事实上,这是我最喜欢的演讲之一。如果你还没看过,非常值得一看:[VIDEO] — jgautsch, 2018-08
Curry-Howard对应和瓦德勒在StrangeLoop*上的“命题即类型”演讲很早就让我大开眼界,认识到逻辑在我日常编程中的甜蜜、甜蜜的实用性。一开始听起来很奇怪,但在看这个演讲之前,我从未意识到为什么这些事情重要。为瓦德勒点赞。我度过的最好的约40分钟。* [VIDEO] — imode, 2017-01
命题即类型:[VIDEO] 我认为这真的真的能改变我们看待日常编程任务的方式,从我们选择的工具类型到我们解决问题的方法,无处不在。 — runT1ME, 2016-10
+1 可能是我今年在Strange Loop上最喜欢的演讲。光是看从这里开始的一分钟左右就值得:[VIDEO] — jcox92, 2015-11
这很好,而且确实很有趣 [VIDEO](Philip Wadler 的命题即类型)。它真正的焦点是类型系统和逻辑系统之间的一一对应,但非常值得一看。这是很好的阅读材料——它揭开了数学形式中那些有趣的类型规则的神秘面纱。[LINK](不过这些都没有告诉你如何自己实现检查器) — mrkeen, 2024-06
相关视频
- “Uncle” Bob Martin · Program on Entrepreneurship · 1:23:35
- Robert C Martin - 整洁架构与设计 · gnbitcom · 58:39
- Evan Czaplicki 谈“编程语言的经济学”(Strange Loop 2023) · Strange Loop Conference · 43:57
- 四十年前的四门语言 - Scott Wlaschin · NDC Conferences · 1:01:45
- OCaml Workshop 2020 - 2020年OCaml平台现状 · OCamlWorkshops · 1:00:00
- Macintosh 工厂 · MacGeneration · 15:00
- 太平洋西北 Scala 2013 我们全都做错了 作者 Paul Phillips · Confreaks · 50:43
- 用科学方法调试 - Stuart Halloway · ClojureTV · 49:09
- Ruby Conf 12 - Y Not- 函数式编程历险记 by Jim Weirich · Confreaks · 53:21
- Python如何被泄漏的内部机制塑造,Armin Ronacher,Flask框架 · Видео с мероприятий {speach! · 49:55
- 为什么函数式编程没有成为主流?—— Richard Feldman · Metosin · 46:09
- 也许不 - Rich Hickey · ClojureTV · 1:03:28
- APL中的康威生命游戏 · Dyalog · 7:47
- 讲座 1A | MIT 6.001 计算机程序的构造和解释,1986 · MIT OpenCourseWare · 1:12:55
- Crockford 谈 JavaScript - 第一卷:早年 · YUI Library · 1:42:08
- 培育语言,作者:Guy Steele · Bill Pugh · 53:31