科学网

 找回密码
  注册
搜索
热搜: 科学 论文
搜索
数学基础的危机与计算机理论的诞生 - 图灵的壮举
柳渝 2021-6-14 03:18
图灵的论著和工作为计算机理论的诞生奠定了基础,为了理解这一壮举的背景,需要回顾 20 世纪初那场著名的数学基础危机。 一, 数学基础危机 【 1 】 对于数学基础的关注和研究,可追溯至古代,但在较长的历史阶段中,基本上只限于对单科数学基础的讨论,至于作为整个数学基础的探索,乃是 20 ...
个人分类: 不确定性问题和算法讨论|3111 次阅读|没有评论
√2是什么?- 希帕索斯悖论
柳渝 2021-4-11 21:26
古希腊的毕达哥拉斯( Pythagoras ,约公元前 500 年)学派信奉 “ 万物皆数 ” ,认为宇宙间各种不同的关系都可以用整数或整数之比(有理数)来表示。但是毕达哥拉斯的学生希帕索斯( Hippasus )却发现,二个边长为 1 的直角三角形的斜边,根据 “ 勾股定理 ” 等于 √ 2 ,而 √ 2 是 “ ...
个人分类: 不确定性问题和算法讨论|1827 次阅读|没有评论
“NP问题是可计算的吗?” - 从“可计算性”的角度审视NP
柳渝 2020-12-31 16:53
P vs NP 世纪难题显示出在现有的计算机理论中存在着令人不安的困惑:一方面,书本中的 NP 问题理论部份无论是学习或教学都感到困难,以至于人们不得不一次又一次回头去重新学习或思考,但或者失望而返,或者强迫自己服从这些权威论述;另一方面,现有的 NP 问题理论与实际工作几乎完全脱节,甚至有人说完全可 ...
个人分类: 不确定性问题和算法讨论|1833 次阅读|没有评论
关于David Deutsch提出的“数学家的误解(mathematicians’ misconception)”的讨论
柳渝 2020-11-27 19:55
FOM( https://cs.nyu.edu/mailman/listinfo/fom )是一个讨论数学基础的论坛,汇聚了国际上计算机和数学领域的理论工作者,由 Martin Davis( https://fr.wikipedia.org/wiki/Martin_Davis )主持。 最近在讨论英国学者 David Deutsch 在文章 “The Philosophy of Constructor Theory”( https:/ ...
个人分类: 不确定性问题和算法讨论|1631 次阅读|没有评论
波菲利之树(Porphyrian tree)- 定义
柳渝 2020-10-18 00:46
波菲利( Porphyry 234 - 305 )是古罗马哲学家,在他撰写的《亚里士多德〈范畴篇〉导论》中,将 “ 定义 ” 形式化为:种类+属差,以此把亚里士多德之知识分类论见表达为二叉树状图,称为 “ 波菲利之树( Porphyrian tree ) ” ,对西方哲学及后来的科学发展产生了很大的影响。 在 “ 波 ...
个人分类: 不确定性问题和算法讨论|2543 次阅读|没有评论
图灵与维特根斯坦关于矛盾和悖论的对话 - 第21讲(1939年)
柳渝 2020-8-31 12:01
维特根斯坦曾与波普尔对谈半个小时,就有人八卦了一本书;而维特根斯坦和图灵智力交锋了一学期,却很少有人评论,。。。 这是因为人们对 “ 思想 ” (在与 “ 内容 ” 本身的相对的意义上)比对(人的) “ 思想形式 ” (与 “ 内容 ” 的实体相对应)上更不容易看到事物的深层本质。 ...
个人分类: 不确定性问题和算法讨论|1576 次阅读|没有评论
Cook的文章“定理证明过程的复杂性”(部分译文)
柳渝 2020-8-3 14:40
P vs NP 问题的提出缘起于 “ 定理证明过程的复杂性( The Complexity of Theorem-Proving Procedures ) ” ( 1971 年)。分享此文的部分译文。 定理证明过程的复杂性 摘要 文章指出,不确定性图灵机在多项式时间内解决的任何识别问题都可以 “ 归约 ” 为判定给定命题公式是否为重言 ...
个人分类: 不确定性问题和算法讨论|1114 次阅读|没有评论
关于图灵机与人工智能的关系的对话 - 奇点O论坛(2020/6/6)
柳渝 2020-6-21 15:40
奇点O论坛(2020/6/6)后( 图灵机的“非计算”思考 - 图灵机与人工智能的关系(奇点O论坛,2020/6/6) ),我和王培老师关于图灵机与人工智能的关系展开了对话。 柳渝: 怎么看 “ 判定问题 ” 与 “ ⼈工智能 ” 的关系? 王培: 智能系统每时每刻都在做 “ 判断 ” ,但这和计 ...
个人分类: 不确定性问题和算法讨论|3585 次阅读|没有评论
与法国朋友漫谈P vs NP(7)
柳渝 2020-5-28 14:13
柳渝: P vs NP 问题问 “NP=P ? ” ,实际上是问 “ NP-complete =P ? ” ,所以 P vs NP 问题指向 NP-complete 。 由于人们未能确定 NP-complete 的特有属性,所以把焦点从 NP-complete 转移到 NP , NP 被定义为: - 定义 1: NP 是不确定性图灵机多项式时间可判定的问题。 ...
个人分类: 不确定性问题和算法讨论|1607 次阅读|没有评论
与法国朋友漫谈P vs NP(6)
柳渝 2020-5-24 05:01
柳渝: 同意! “ 如果我们有不同 P 的 NP ,那么 P 和 NP-Complete 之间是分离的 ” 。 问题是,对象是由概念来指称和认知的,概念由定义形成,其内涵是反映对象的本质的属性。所以一个概念指称的对象和对对象的认知,取决于概念的内涵。 定义 1 或定义 2 的 “ 可验证 ” 或 ...
个人分类: 不确定性问题和算法讨论|1226 次阅读|没有评论

Archiver|手机版|科学网 ( 京ICP备07017567号-12 )

GMT+8, 2021-10-16 23:53

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部