c*******v
发帖数: 2599 | 1 我翻了下老王的PvsNP贴。这点我和wdong看法可能不同。老王的blog讲的是有严重错误
的。
这里分享一下。欢迎批评指正。其实我的观点都是老的。在本版早就讲过。也许是x年
前？
P这个概念，是在universal Turing machine基础上的。
世上所有图灵机都是upto 多项式等价的。所以P才有正当性。
假如世上所有图灵机，都是upto另一种操作等价的。
那P就会换成别的。简而言之，没有universal Turing Machine，
P这个概念无法诞生。这是理论考虑。
实践考虑更重要，我查考过很久，没有发现实用的universal lambda calculus。
最接近的是这个http://tromp.github.io/cl/cl.html
（这个代码得了c 语言obfustcated奖。印象里perl作者，python作者也拿过这个奖）
我对此感兴趣，是因为我早年考虑如下问题：
永远不停的zip一个文件，最后会导致什么结果。我推导出了不可压缩数。
然后因为知道图灵机之间只差一个常数，自己推导出了描述复杂性。
（这种概念制造办法，和温度从绝对零度算起是一样的）。
所以，老王讲：
“计算理论如此晦涩难懂，我认为图灵机是祸首。如果你能理解 lambda calculus，
将会大大简化理解计算理论的过程。”
我认为是一个根本性的错误。不理解图灵机，
就无法理解universal turing machine。不懂universal turing machine，无法展开P理
论。
lambda calculs = Turing Machine
但是lambda calculs没有对应于universal turing machine的理论工具。
简而言之，我未见过合适的以lambda calculs为基础的计算理论。
如果有人知道，请推荐一下。
最后，老王的视野，我认为缺的是C语言字符串这块。
每次提到C，他都会讲内存手调，是负担。实际上有经验的人都知道。
字符串那个forward dash 0，造成的各种buff越界，以及各种和其他编程系统不兼容，
是最多的问题。 |
x****u
发帖数: 44466 | 2 数理逻辑是最近50年才兴起的，基本上是天坑
PNP研究里最见鬼的东西是，为什么会有这么多NPC问题，这些问题看似完全不相关却有
本质上等价的复杂度，意味着什么
如果能把PNP关系严格证明，其思路会对可计算理论有巨大的推动作用。毕竟现代已经
有够多---1.可计算，2.算出来有巨大不可估量的学术工业价值，3.但你就是算不出来-
--的问题了
【在 c*******v 的大作中提到】
: 我翻了下老王的PvsNP贴。这点我和wdong看法可能不同。老王的blog讲的是有严重错误
: 的。
: 这里分享一下。欢迎批评指正。其实我的观点都是老的。在本版早就讲过。也许是x年
: 前？
: P这个概念，是在universal Turing machine基础上的。
: 世上所有图灵机都是upto 多项式等价的。所以P才有正当性。
: 假如世上所有图灵机，都是upto另一种操作等价的。
: 那P就会换成别的。简而言之，没有universal Turing Machine，
: P这个概念无法诞生。这是理论考虑。
: 实践考虑更重要，我查考过很久，没有发现实用的universal lambda calculus。
|
c*******v
发帖数: 2599 | 3 我只管自己的事。假如有universal lambda calculus的软件，我有用处。
来-
【在 x****u 的大作中提到】
: 数理逻辑是最近50年才兴起的，基本上是天坑
: PNP研究里最见鬼的东西是，为什么会有这么多NPC问题，这些问题看似完全不相关却有
: 本质上等价的复杂度，意味着什么
: 如果能把PNP关系严格证明，其思路会对可计算理论有巨大的推动作用。毕竟现代已经
: 有够多---1.可计算，2.算出来有巨大不可估量的学术工业价值，3.但你就是算不出来-
: --的问题了
|
x****u
发帖数: 44466 | 4 从小学开始就躲不过这个
你做数学题，验证答案是P，而根据已学知识点穷举答案则是NP，为了小学毕业，你必
须采取非逻辑性的策略把这个NP优化到接近P才能考及格
【在 c*******v 的大作中提到】
: 我只管自己的事。假如有universal lambda calculus的软件，我有用处。
:
: 来-
|
c*******v
发帖数: 2599 | 5 我再举个例子：
要是有个人跟你讲，你之所以理解不了P vs NP，是因為
图灵机是障碍。细胞自动机才是真传。
你会怎么想？现有的计算复杂度文本，是和图灵机深度耦合的。那么发这种高论，至少
要有几个论文给看下吧。
不然，那不是科研没入门么。 |
l**o
发帖数: 131 | 6 “计算理论如此晦涩难懂，我认为图灵机是祸首。如果你能理解 lambda calculus，将
会大大简化理解计算理论的过程。” - 这里的计算理论，多半是可计算理论. P vs NP
是计算复杂性理论，他似乎有点搞混了。 |
c*******v
发帖数: 2599 | 7 可计算理论也和图灵机分不开关系。本身可计算的定义，合理性就在这几种模型的等价
性证明。以及后来的邱奇论题。
图灵最早包含图灵机的论文，几乎被拒稿。因为他用图灵机证明的一个问题，早一点点
被邱奇证明过了。后来图灵模型优越性的建立，是学术界发展的结果。
一开始被看低的其实是图灵模型。
: “计算理论如此晦涩难懂，我认为图灵机是祸首。如果你能理解 lambda
calculus，将
: 会大大简化理解计算理论的过程。” - 这里的计算理论，多半是可计算理论. P
vs NP
: 是计算复杂性理论，他似乎有点搞混了。
【在 l**o 的大作中提到】
: “计算理论如此晦涩难懂，我认为图灵机是祸首。如果你能理解 lambda calculus，将
: 会大大简化理解计算理论的过程。” - 这里的计算理论，多半是可计算理论. P vs NP
: 是计算复杂性理论，他似乎有点搞混了。
|
l**o
发帖数: 131 | 8 可计算理论，首先研究的就是啥是不可计算的。这一点上Lambda Calculs确实理解起来
容易点。现在计算机系教科书，为了好和计算复杂性理论接轨，直接用图灵机来从可计
算理论一直玩到计算复杂性理论，基本不讲Lambda Calculus了。另外图灵机和有限自
动机的相似性，也是计算机理论教科书独爱图灵机的原因之一。
王喜欢Lambda Calculus则多半是因为他Programming Language Theory出身, type
theory更加熟悉，那儿的理论基础之一是Typed Lambda Calculus
数理逻辑的直接用recursive function, 对上面两个都不大待见。
P
【在 c*******v 的大作中提到】
: 可计算理论也和图灵机分不开关系。本身可计算的定义，合理性就在这几种模型的等价
: 性证明。以及后来的邱奇论题。
: 图灵最早包含图灵机的论文，几乎被拒稿。因为他用图灵机证明的一个问题，早一点点
: 被邱奇证明过了。后来图灵模型优越性的建立，是学术界发展的结果。
: 一开始被看低的其实是图灵模型。
:
:
: “计算理论如此晦涩难懂，我认为图灵机是祸首。如果你能理解 lambda
: calculus，将
:
: 会大大简化理解计算理论的过程。” - 这里的计算理论，多半是可计算理论. P
: vs NP
|
l**o
发帖数: 131 | 9 "数理逻辑是最近50年才兴起的" - 纯几把扯淡
来-
【在 x****u 的大作中提到】
: 数理逻辑是最近50年才兴起的，基本上是天坑
: PNP研究里最见鬼的东西是，为什么会有这么多NPC问题，这些问题看似完全不相关却有
: 本质上等价的复杂度，意味着什么
: 如果能把PNP关系严格证明，其思路会对可计算理论有巨大的推动作用。毕竟现代已经
: 有够多---1.可计算，2.算出来有巨大不可估量的学术工业价值，3.但你就是算不出来-
: --的问题了
|
c*******v
发帖数: 2599 | 10 老王是被goog一个经理弄去干苦力，在一个假大空的项目里做一块。干的不错,被吹捧
了一番，上了贼船。我觉得他就是学了stave yega的一些说法。此人在emacs里用lisp
写了个javascript解释器。还有jython也是他们组相关的部分。
这些类似的项目都挺有意思。难度也不低。但是拔高上去就是胡说八到了。
老王详细解释了教科书的P NP的定义。不可能是和可计算性弄混了。
我倒是觉得，从
头到尾他就没弄明白可计算性。后者可比P麻烦的多。因为要说明为何计算可以有数学
定义。就是要弄明白邱奇论题。
: 可计算理论，首先研究的就是啥是不可计算的。这一点上Lambda Calculs
确实理
解起来
: 容易点。现在计算机系教科书，为了好和计算复杂性理论接轨，直接用图
灵机来
从可计
: 算理论一直玩到计算复杂性理论，基本不讲Lambda Calculus了。另外图
灵机和
有限自
: 动机的相似性，也是计算机理论教科书独爱图灵机的原因之一。
: 王喜欢Lambda Calculus则多半是因为他Programming Language Theory出
身,
type
: theory更加熟悉，那儿的理论基础之一是Typed Lambda Calculus
: 数理逻辑的直接用recursive function, 对上面两个都不大待见。
: P
【在 l**o 的大作中提到】
: "数理逻辑是最近50年才兴起的" - 纯几把扯淡
:
: 来-
|
|
|
x****u
发帖数: 44466 | 11 看好，我没说数理逻辑是最近50年诞生的
计算机的诞生一个很重要因素就是当时数学家认为只要逻辑推理速度够快就是全知全能
了，到70年代末才发现数理逻辑也有极限。
【在 l**o 的大作中提到】
: "数理逻辑是最近50年才兴起的" - 纯几把扯淡
:
: 来-
|
x****u
发帖数: 44466 | 12 王垠一个主要观点是0.0000001的指数函数增长可能很长时间都慢于N^10000000，这个
想法本事没错，但毫无意义。
大家平时研究的问题里的系数都不是特别大或者特别小的，学过群论的应知道突破圈子
的可能性不是特别大。
lisp
【在 c*******v 的大作中提到】
: 老王是被goog一个经理弄去干苦力，在一个假大空的项目里做一块。干的不错,被吹捧
: 了一番，上了贼船。我觉得他就是学了stave yega的一些说法。此人在emacs里用lisp
: 写了个javascript解释器。还有jython也是他们组相关的部分。
: 这些类似的项目都挺有意思。难度也不低。但是拔高上去就是胡说八到了。
: 老王详细解释了教科书的P NP的定义。不可能是和可计算性弄混了。
: 我倒是觉得，从
: 头到尾他就没弄明白可计算性。后者可比P麻烦的多。因为要说明为何计算可以有数学
: 定义。就是要弄明白邱奇论题。
:
:
: 可计算理论，首先研究的就是啥是不可计算的。这一点上Lambda Calculs
|
l**o
发帖数: 131 | 13 “70年代末才发现数理逻辑也有极限” - 你是说Cook-Levin Theorem？那是70年代初
。而且在此之前，可以证明的高时间复杂度的问题60年代早期已经被发现了。
数理逻辑是最近50年兴起，- 也还是扯几把淡
【在 x****u 的大作中提到】
: 看好，我没说数理逻辑是最近50年诞生的
: 计算机的诞生一个很重要因素就是当时数学家认为只要逻辑推理速度够快就是全知全能
: 了，到70年代末才发现数理逻辑也有极限。
|
l**o
发帖数: 131 | 14 那是王垠没有数理逻辑的训练，对递归没有感觉。事实上P是有其直觉的意义的，并非
先有NP再硬套出来。很简单，直觉告诉我们O(n)这种线性复杂度是可以有效计算的。那
么一个线性复杂度的函数中间调用一个线性复杂度函数，那也应该是可以有效计算的。
只要我们保持常数次递归，其复杂度就是P。
这种东西60年代就研究过了。Cobham的“The intrinsic computational difficulty
of functions"就是讲的这个，你可以看到完全是recursive function那一套。
【在 x****u 的大作中提到】
: 王垠一个主要观点是0.0000001的指数函数增长可能很长时间都慢于N^10000000，这个
: 想法本事没错，但毫无意义。
: 大家平时研究的问题里的系数都不是特别大或者特别小的，学过群论的应知道突破圈子
: 的可能性不是特别大。
:
: lisp
|
w***g
发帖数: 5958 | 15 王垠的问题就是不管对还是错, 他那个文章都只是在解释教科书里的概念,
而且只是解释本科生教科书里的概念. 也没有解释出任何新意.
所以逼格并不高. 写了那篇文章,反而让人看出来关于这个问题
他知道的也就是本科生水平.
整篇文章,价值不如xiaoju的一句话:
"
你做数学题，验证答案是P，而根据已学知识点穷举答案则是NP，为了小学毕业，你必
须采取非逻辑性的策略把这个NP优化到接近P才能考及格
"
lisp
Calculs
【在 c*******v 的大作中提到】
: 老王是被goog一个经理弄去干苦力，在一个假大空的项目里做一块。干的不错,被吹捧
: 了一番，上了贼船。我觉得他就是学了stave yega的一些说法。此人在emacs里用lisp
: 写了个javascript解释器。还有jython也是他们组相关的部分。
: 这些类似的项目都挺有意思。难度也不低。但是拔高上去就是胡说八到了。
: 老王详细解释了教科书的P NP的定义。不可能是和可计算性弄混了。
: 我倒是觉得，从
: 头到尾他就没弄明白可计算性。后者可比P麻烦的多。因为要说明为何计算可以有数学
: 定义。就是要弄明白邱奇论题。
:
:
: 可计算理论，首先研究的就是啥是不可计算的。这一点上Lambda Calculs
|
c*******v
发帖数: 2599 | 16 老王倒是企图讲新东西:
“计算理论如此晦涩难懂，我认为图灵机是祸首。如果你能理解 lambda calculus，
将会大大简化理解计算理论的过程。”
这话说出来，说实话我觉得他不理解p np。不诚实。
他话给计算理论课当过助教，也未必就是真话。
【在 w***g 的大作中提到】
: 王垠的问题就是不管对还是错, 他那个文章都只是在解释教科书里的概念,
: 而且只是解释本科生教科书里的概念. 也没有解释出任何新意.
: 所以逼格并不高. 写了那篇文章,反而让人看出来关于这个问题
: 他知道的也就是本科生水平.
: 整篇文章,价值不如xiaoju的一句话:
: "
: 你做数学题，验证答案是P，而根据已学知识点穷举答案则是NP，为了小学毕业，你必
: 须采取非逻辑性的策略把这个NP优化到接近P才能考及格
: "
:
|
n*********2
发帖数: 357 | 17 > 王垠一个主要观点是0.0000001的指数函数增长可能很长时间都慢于N^10000000，这
个想法本事没错，但毫无意义。
> 大家平时研究的问题里的系数都不是特别大或者特别小的，
给一个反例 (against your above statement)： 那个2002年发现的第一个确定型的素
性检测的算法AKS，是多项式的【开始是^12，后来被改善到^6】。尽管是多项式的，
但是实践上是非常慢的。 你找个实现测试一下1536 比特的数字跑一跑就知道了。
（所以实际运用上大家还是用概率素性检测算法。）
【在 x****u 的大作中提到】
: 王垠一个主要观点是0.0000001的指数函数增长可能很长时间都慢于N^10000000，这个
: 想法本事没错，但毫无意义。
: 大家平时研究的问题里的系数都不是特别大或者特别小的，学过群论的应知道突破圈子
: 的可能性不是特别大。
:
: lisp
|
x****u
发帖数: 44466 | 18 PNP，NPC是和图灵机紧密相关的问题，代表了机械计算能实现的极限
这个
圈子
【在 l**o 的大作中提到】
: 那是王垠没有数理逻辑的训练，对递归没有感觉。事实上P是有其直觉的意义的，并非
: 先有NP再硬套出来。很简单，直觉告诉我们O(n)这种线性复杂度是可以有效计算的。那
: 么一个线性复杂度的函数中间调用一个线性复杂度函数，那也应该是可以有效计算的。
: 只要我们保持常数次递归，其复杂度就是P。
: 这种东西60年代就研究过了。Cobham的“The intrinsic computational difficulty
: of functions"就是讲的这个，你可以看到完全是recursive function那一套。
|
x****u
发帖数: 44466 | 19 你这个例子系数才12啊，而且确定性和概率性的意义不同吧
【在 n*********2 的大作中提到】
: > 王垠一个主要观点是0.0000001的指数函数增长可能很长时间都慢于N^10000000，这
: 个想法本事没错，但毫无意义。
: > 大家平时研究的问题里的系数都不是特别大或者特别小的，
: 给一个反例 (against your above statement)： 那个2002年发现的第一个确定型的素
: 性检测的算法AKS，是多项式的【开始是^12，后来被改善到^6】。尽管是多项式的，
: 但是实践上是非常慢的。 你找个实现测试一下1536 比特的数字跑一跑就知道了。
: （所以实际运用上大家还是用概率素性检测算法。）
|
n*********2
发帖数: 357 | 20 你把多项式的“系数”和“指数”术语混用了吧？ 12是这个多项式时间算法的常指数
，不是系数。
即使这个常指数不大（远远没有到达你所说的N^10000000），这个多项式时间的算法在
一些较大的场合里就已经不很有效了； 所以笼统地用P来描述， 并不合适。在这种意
义上老王说asymptotic analysis是一个意义被夸大了和滥用的工具， 这个并没错(当
然也不新鲜)
【在 x****u 的大作中提到】
: 你这个例子系数才12啊，而且确定性和概率性的意义不同吧
|
|
|
c*******v
发帖数: 2599 | 21 理论指标和实际使用的thumb rule之间的差距，很常见的。
当新大陆发现一样来赞叹，没什么必要吧。
例如温度高你还不一定更热----气压也影响感觉的。
【在 n*********2 的大作中提到】
: 你把多项式的“系数”和“指数”术语混用了吧？ 12是这个多项式时间算法的常指数
: ，不是系数。
: 即使这个常指数不大（远远没有到达你所说的N^10000000），这个多项式时间的算法在
: 一些较大的场合里就已经不很有效了； 所以笼统地用P来描述， 并不合适。在这种意
: 义上老王说asymptotic analysis是一个意义被夸大了和滥用的工具， 这个并没错(当
: 然也不新鲜)
|
l**o
发帖数: 131 | 22 扯淡，N是Nondeterministic, 本质是用关系取代函数，完全是个数学概念，和机械计
算关系极小。机械现在也许可以模拟Nondeterministic，直接实现的没有。
【在 x****u 的大作中提到】
: PNP，NPC是和图灵机紧密相关的问题，代表了机械计算能实现的极限
:
: 这个
: 圈子
|
n*********2
发帖数: 357 | 23 》理论指标和实际使用的thumb rule之间的差距，很常见的。
这个差距远远不是“理论指标和实际使用的”差别。 这个是一个理论的滥用的问题，
是一个理论和另外一个理论的差别了。这个差别其实在80年代就开始显示出来了。那时
人们试图应用计算复杂度理论来构造公钥密码。猛一看这两者应当是同一类东西， 应
当很容易地就照猫画虎的。 不停地试和失败过之后才后来发现两者不是一回事。从这
中就可以开始看出计算复杂度理论和NPC的局限性了。
这种理论和理论的差别在200x/201x年代重新冒出来了：这一次是显示在关于“可证明
性安全系统”的争辩中。在这里，基于polynomial-time reduction的途径的缺陷暴露
得更加明显。
如果只是单独从计算机科学的角度来学习“计算复杂度理论，” 很容易把它学成一个
大榔头，然后把世界万物都看成钉子，都要用那个榔头来砸一砸的。只有砸到一个硬的
铁板，砸不动了，人才死心的。
【在 c*******v 的大作中提到】
: 理论指标和实际使用的thumb rule之间的差距，很常见的。
: 当新大陆发现一样来赞叹，没什么必要吧。
: 例如温度高你还不一定更热----气压也影响感觉的。
|
x****u
发帖数: 44466 | 24 NPC,PNP都是和图灵机一起出来的概念
【在 l**o 的大作中提到】
: 扯淡，N是Nondeterministic, 本质是用关系取代函数，完全是个数学概念，和机械计
: 算关系极小。机械现在也许可以模拟Nondeterministic，直接实现的没有。
|
x****u
发帖数: 44466 | 25 计算复杂度理论研究主要靠计算机科学界养活，你拿了人家钱就得替人家办事
【在 n*********2 的大作中提到】
: 》理论指标和实际使用的thumb rule之间的差距，很常见的。
: 这个差距远远不是“理论指标和实际使用的”差别。 这个是一个理论的滥用的问题，
: 是一个理论和另外一个理论的差别了。这个差别其实在80年代就开始显示出来了。那时
: 人们试图应用计算复杂度理论来构造公钥密码。猛一看这两者应当是同一类东西， 应
: 当很容易地就照猫画虎的。 不停地试和失败过之后才后来发现两者不是一回事。从这
: 中就可以开始看出计算复杂度理论和NPC的局限性了。
: 这种理论和理论的差别在200x/201x年代重新冒出来了：这一次是显示在关于“可证明
: 性安全系统”的争辩中。在这里，基于polynomial-time reduction的途径的缺陷暴露
: 得更加明显。
: 如果只是单独从计算机科学的角度来学习“计算复杂度理论，” 很容易把它学成一个
|
l**o
发帖数: 131 | 26 扯几把淡，图灵机是30年代出来的；计算复杂度正式开始要等到50年代末60年代初 （
虽然1956年Godel写给Neumann的信里畅想了SAT如果是O(n^2)会怎么样）；P的重要性在
1965年Cobham那篇文章里面提出,主要用recursive function，没图灵机多少事；
Nondeterministic首先是50年代末在自动机研究中提出来的，要等到1971年Cook的文章
才把P, TM和Nondeterministic结合起来。
你这个帖子里的发言，错的不少，对的不多，光看科普是不够的，骚年。
【在 x****u 的大作中提到】
: NPC,PNP都是和图灵机一起出来的概念
|
c*******v
发帖数: 2599 | 27 很有意思。展开说说加密这块的复杂性？有入门文献吗？
【在 n*********2 的大作中提到】
: 》理论指标和实际使用的thumb rule之间的差距，很常见的。
: 这个差距远远不是“理论指标和实际使用的”差别。 这个是一个理论的滥用的问题，
: 是一个理论和另外一个理论的差别了。这个差别其实在80年代就开始显示出来了。那时
: 人们试图应用计算复杂度理论来构造公钥密码。猛一看这两者应当是同一类东西， 应
: 当很容易地就照猫画虎的。 不停地试和失败过之后才后来发现两者不是一回事。从这
: 中就可以开始看出计算复杂度理论和NPC的局限性了。
: 这种理论和理论的差别在200x/201x年代重新冒出来了：这一次是显示在关于“可证明
: 性安全系统”的争辩中。在这里，基于polynomial-time reduction的途径的缺陷暴露
: 得更加明显。
: 如果只是单独从计算机科学的角度来学习“计算复杂度理论，” 很容易把它学成一个
|
x****u
发帖数: 44466 | 28 你就是为了抬杠而抬杠，没有图灵机哪里有P和NP？
你想贴历史年表开个新帖来
【在 l**o 的大作中提到】
: 扯几把淡，图灵机是30年代出来的；计算复杂度正式开始要等到50年代末60年代初 （
: 虽然1956年Godel写给Neumann的信里畅想了SAT如果是O(n^2)会怎么样）；P的重要性在
: 1965年Cobham那篇文章里面提出,主要用recursive function，没图灵机多少事；
: Nondeterministic首先是50年代末在自动机研究中提出来的，要等到1971年Cook的文章
: 才把P, TM和Nondeterministic结合起来。
: 你这个帖子里的发言，错的不少，对的不多，光看科普是不够的，骚年。
|
x****u
发帖数: 44466 | 29 好吧，参数
王垠和你的设想的致命问题是，无理由假设了本来是极难存在的极小常指数的可能性
和其他所有世纪数学难题的研究一样，P/NP的研究从来不是为了用此结论，而是为了理
解深层次的结构。所以说P/NP无意义本事是恒真的废话，类似于说画圆为方也无意义，
就算被证否了你一样能量出圆的面积。而正十七边形就算能尺规作图，按步骤做出来误
差也比量角器搞出来的大多了。
【在 n*********2 的大作中提到】
: 你把多项式的“系数”和“指数”术语混用了吧？ 12是这个多项式时间算法的常指数
: ，不是系数。
: 即使这个常指数不大（远远没有到达你所说的N^10000000），这个多项式时间的算法在
: 一些较大的场合里就已经不很有效了； 所以笼统地用P来描述， 并不合适。在这种意
: 义上老王说asymptotic analysis是一个意义被夸大了和滥用的工具， 这个并没错(当
: 然也不新鲜)
|
l**o
发帖数: 131 | 30 "NPC,PNP都是和图灵机一起出来的概念" - 一起出来？开历史年表就是告诉你不是一起
出来的。
【在 x****u 的大作中提到】
: 你就是为了抬杠而抬杠，没有图灵机哪里有P和NP？
: 你想贴历史年表开个新帖来
|
|
|
x****u
发帖数: 44466 | 31 你是缺常识，地球上第一台符合定义的图灵机是什么时候做出来的？没有真机的出现谁
给你研究纯假设问题。
【在 l**o 的大作中提到】
: "NPC,PNP都是和图灵机一起出来的概念" - 一起出来？开历史年表就是告诉你不是一起
: 出来的。
|
l**o
发帖数: 131 | 32 "无理由假设了本来是极难存在的极小常指数的可能性" - 这啥意思？
【在 x****u 的大作中提到】
: 好吧，参数
: 王垠和你的设想的致命问题是，无理由假设了本来是极难存在的极小常指数的可能性
: 和其他所有世纪数学难题的研究一样，P/NP的研究从来不是为了用此结论，而是为了理
: 解深层次的结构。所以说P/NP无意义本事是恒真的废话，类似于说画圆为方也无意义，
: 就算被证否了你一样能量出圆的面积。而正十七边形就算能尺规作图，按步骤做出来误
: 差也比量角器搞出来的大多了。
|
l**o
发帖数: 131 | 33 上面的列的计算复杂性理论历史就是我的常识，根据这个常识 - NPC,PNP不是和图灵机
一起出来的， 图灵机出来的时候，大家考虑的是可计算性，计算复杂度的研究要到很
久以后。
“地球上第一台符合定义的图灵机是什么时候做出来的”， 你是说物理的机器还是理
论模型？理论模型当然是图灵写他论文的时候出来的。
【在 x****u 的大作中提到】
: 你是缺常识，地球上第一台符合定义的图灵机是什么时候做出来的？没有真机的出现谁
: 给你研究纯假设问题。
|
x****u
发帖数: 44466 | 34 王垠说研究PNP无意义时举了个例子，指数为0.0000001的时候，这个东西最好不要凭空
相信存在比较好
【在 l**o 的大作中提到】
: "无理由假设了本来是极难存在的极小常指数的可能性" - 这啥意思？
|
c*******v
发帖数: 2599 | 35 渐进分析里的多项式计算次数，中国古代说不定就有了。我书架上就有一渐进分析的书
。但是这个，以及recursion function提及的多项式计算啥的。
和图灵的概念之间差一个universal turing machine。
没有UTM，计算复杂度就只能一个计算模型几个计算模型.
【在 l**o 的大作中提到】
: 上面的列的计算复杂性理论历史就是我的常识，根据这个常识 - NPC,PNP不是和图灵机
: 一起出来的， 图灵机出来的时候，大家考虑的是可计算性，计算复杂度的研究要到很
: 久以后。
: “地球上第一台符合定义的图灵机是什么时候做出来的”， 你是说物理的机器还是理
: 论模型？理论模型当然是图灵写他论文的时候出来的。
|
x****u
发帖数: 44466 | 36 图灵机被广泛接受是二战以后了
图灵提出图灵理论后不久，设计了一台计算机破密码，这计算机不是图灵机
【在 l**o 的大作中提到】
: 上面的列的计算复杂性理论历史就是我的常识，根据这个常识 - NPC,PNP不是和图灵机
: 一起出来的， 图灵机出来的时候，大家考虑的是可计算性，计算复杂度的研究要到很
: 久以后。
: “地球上第一台符合定义的图灵机是什么时候做出来的”， 你是说物理的机器还是理
: 论模型？理论模型当然是图灵写他论文的时候出来的。
|
c*******v
发帖数: 2599 | 37 Turing Machine is a concept, it is bullet proof...
【在 x****u 的大作中提到】
: 图灵机被广泛接受是二战以后了
: 图灵提出图灵理论后不久，设计了一台计算机破密码，这计算机不是图灵机
|
x****u
发帖数: 44466 | 38 图灵完全的概念是要花代价的，条件有限时人们会有别的选择
【在 c*******v 的大作中提到】
: Turing Machine is a concept, it is bullet proof...
|
c*******v
发帖数: 2599 | 39 我是说你分不清什么叫概念，什么叫具体的计算机。
这世上有人吗？都是张三李四。人就是一个概念。
【在 x****u 的大作中提到】
: 图灵完全的概念是要花代价的，条件有限时人们会有别的选择
|
l**o
发帖数: 131 | 40 秦九韶算法？对于一个具体问题设计更快的算法，很早就有。然而系统研究函数的内在
计算复杂性并把它们归类，则是现代的事情了。
【在 c*******v 的大作中提到】
: 渐进分析里的多项式计算次数，中国古代说不定就有了。我书架上就有一渐进分析的书
: 。但是这个，以及recursion function提及的多项式计算啥的。
: 和图灵的概念之间差一个universal turing machine。
: 没有UTM，计算复杂度就只能一个计算模型几个计算模型.
|
|
|
c*******v
发帖数: 2599 | 41 As I said many times, to my best knowledge, there is no
"universal lambda calculus/recursion function...".
Nobody had the idea of simulating a computation model on
another computation model.
Nobody knew the cost of the simulation is constant.
【在 l**o 的大作中提到】
: 秦九韶算法？对于一个具体问题设计更快的算法，很早就有。然而系统研究函数的内在
: 计算复杂性并把它们归类，则是现代的事情了。
|
x****u
发帖数: 44466 | 42 我说的是为什么图灵自己造的计算机不是图灵机。
概念归概念，能造出来还不知道什么时候。第一台图灵完全的机械计算机是牛顿诞生前
被设计的。
【在 c*******v 的大作中提到】
: 我是说你分不清什么叫概念，什么叫具体的计算机。
: 这世上有人吗？都是张三李四。人就是一个概念。
|
l**o
发帖数: 131 | 43 不可能，他要说PNP无意义，只有可能是说什么O(n^1000000)比O(2^{0.0000001 * n})
要糟糕之类的，0.0000001 * n又不是常指数。
【在 x****u 的大作中提到】
: 王垠说研究PNP无意义时举了个例子，指数为0.0000001的时候，这个东西最好不要凭空
: 相信存在比较好
|
c*******v
发帖数: 2599 | 44 你的基本概念错误太多。毫无纠正的必要。我最后给你指出一次。
第一，图灵机是无限纸带的理论模型。你去哪造个出来？这是个概念，不是实体。你造
个三角形我看看。
第二，算盘，罗马算盘，都是图灵完备的。中国算盘到了建国时期，自然数计算的速度
还是胜过机械计算机。
因为我国有很多算法口诀，就是各种子程序。
【在 x****u 的大作中提到】
: 我说的是为什么图灵自己造的计算机不是图灵机。
: 概念归概念，能造出来还不知道什么时候。第一台图灵完全的机械计算机是牛顿诞生前
: 被设计的。
|
l**o
发帖数: 131 | 45 universal lambda calculus/recursive function, 都有啊。用它们来搞计算复杂性分
析倒确实不大趁手, 不过说不定下一个计算复杂性分析突破就是用它们换个思路搞出来
的，我看好你哟！哈哈。
【在 c*******v 的大作中提到】
: As I said many times, to my best knowledge, there is no
: "universal lambda calculus/recursion function...".
: Nobody had the idea of simulating a computation model on
: another computation model.
: Nobody knew the cost of the simulation is constant.
|
l**o
发帖数: 131 | 46 "第一台图灵完全的机械计算机是牛顿诞生前被设计的。" - 那是什么？东方神秘力量？
【在 x****u 的大作中提到】
: 我说的是为什么图灵自己造的计算机不是图灵机。
: 概念归概念，能造出来还不知道什么时候。第一台图灵完全的机械计算机是牛顿诞生前
: 被设计的。
|
x****u
发帖数: 44466 | 47 这么抬杠有意思么？
现在一般说的图灵机指的是理想状态下等价于无限纸带，什么东西算图灵机不是我定义
的，学术界有公认。
人类计算机都是有限状态，所以必然存在确定算法解出来能否停机，你要学王垠接着说
停机问题无意义么？
【在 c*******v 的大作中提到】
: 你的基本概念错误太多。毫无纠正的必要。我最后给你指出一次。
: 第一，图灵机是无限纸带的理论模型。你去哪造个出来？这是个概念，不是实体。你造
: 个三角形我看看。
: 第二，算盘，罗马算盘，都是图灵完备的。中国算盘到了建国时期，自然数计算的速度
: 还是胜过机械计算机。
: 因为我国有很多算法口诀，就是各种子程序。
|
x****u
发帖数: 44466 | 48 就是pascal语言的那个pascal设计的，所以才纪念。
量？
【在 l**o 的大作中提到】
: "第一台图灵完全的机械计算机是牛顿诞生前被设计的。" - 那是什么？东方神秘力量？
|
c*******v
发帖数: 2599 | 49 你压根啥都不懂。别扯啥学术界了。
找本图灵essential看看很难吗
【在 x****u 的大作中提到】
: 这么抬杠有意思么？
: 现在一般说的图灵机指的是理想状态下等价于无限纸带，什么东西算图灵机不是我定义
: 的，学术界有公认。
: 人类计算机都是有限状态，所以必然存在确定算法解出来能否停机，你要学王垠接着说
: 停机问题无意义么？
|
x****u
发帖数: 44466 | 50 我的意思是，凭空相信一般问题里的数字元素能折腾出极端数字太牵强。
而且这里本身用O就不合适，大部分NP问题的算法都是DP解法，精确解的O一直未变过，
也没什么可比的。
【在 l**o 的大作中提到】
: 不可能，他要说PNP无意义，只有可能是说什么O(n^1000000)比O(2^{0.0000001 * n})
: 要糟糕之类的，0.0000001 * n又不是常指数。
|
|
|
x****u
发帖数: 44466 | 51 民科词典第一篇：“你不懂”。。。。
【在 c*******v 的大作中提到】
: 你压根啥都不懂。别扯啥学术界了。
: 找本图灵essential看看很难吗
|
c*******v
发帖数: 2599 | 52 你说有universal lambda calculus，你找个比图灵早的文献我学习下。
【在 l**o 的大作中提到】
: universal lambda calculus/recursive function, 都有啊。用它们来搞计算复杂性分
: 析倒确实不大趁手, 不过说不定下一个计算复杂性分析突破就是用它们换个思路搞出来
: 的，我看好你哟！哈哈。
|
c*******v
发帖数: 2599 | 53 你证明下emacs的skelton mode是图灵完备的，就算你懂好不好。
写个程序就可以证明。废话不讲，程序说话，好不好。
【在 x****u 的大作中提到】
: 民科词典第一篇：“你不懂”。。。。
|
x****u
发帖数: 44466 | 54 “你帮我把作业了就算你毕业”的意思么
【在 c*******v 的大作中提到】
: 你证明下emacs的skelton mode是图灵完备的，就算你懂好不好。
: 写个程序就可以证明。废话不讲，程序说话，好不好。
|
l**o
发帖数: 131 | 55 Lambda Calculus本身就是universal的啊, fx.f(x) - f 可以是任何你想表示的
computable函数的Lambda Calculus， x 是其输入。
【在 c*******v 的大作中提到】
: 你说有universal lambda calculus，你找个比图灵早的文献我学习下。
|
l**o
发帖数: 131 | 56 Pascal calculator, by itself，应该不是图灵完备的，顶多primitive recursive。
加上一个人，那就图灵完备了。不过那是科比和我合砍81分。
【在 x****u 的大作中提到】
: 就是pascal语言的那个pascal设计的，所以才纪念。
:
: 量？
|
l**o
发帖数: 131 | 57 你这段话里面有很多玄妙的和错误的地方，错误固然错误，玄妙的也很有可能走在错误
的路上，LOL。
【在 x****u 的大作中提到】
: 我的意思是，凭空相信一般问题里的数字元素能折腾出极端数字太牵强。
: 而且这里本身用O就不合适，大部分NP问题的算法都是DP解法，精确解的O一直未变过，
: 也没什么可比的。
|
c*******v
发帖数: 2599 | 58 universal turing machine对应的lambda是Lisp那个eval。一页纸的代码。
王垠还有好多Lisp fans觉得恍然大悟的就是那个部分。
【在 l**o 的大作中提到】
: Lambda Calculus本身就是universal的啊, fx.f(x) - f 可以是任何你想表示的
: computable函数的Lambda Calculus， x 是其输入。
|
T********i
发帖数: 2416 | 59 图灵机是内存无限大的计算机，谁能造出来？
同理，图灵完备也只能近似。你造不来，也不可能造出来等价的。
我见过一些搞数学疯疯癫癫的，一会儿说朋友证明了P==NP然后疯了，留下一堆手稿。
一会儿又在研究破解密码的oracle机，还只能是个黑盒子，里面是神经网。反正一笔写
不出俩神经出来。
我的IoT中控是图灵完备的(除了内存不能无限大)。目前除我外，别人的都不是。 |
c*******v
发帖数: 2599 | 60 设计个简单的图灵完备的语言是很容易的。能模拟110细胞自动机的语言，就都是图灵
完备的。
但是在你的特殊的语言之上写个universal turing machine就没那么容易了。相当于写
个eval或者编译器。
Lisp多少人赞叹不已的，其实就是麦卡锡写的那个eval。
再例如新版的css是图灵完备的。但是css写个自己的解释器就不容易。
基础概念不清楚的无法做到。
科学的好处就是脱离现实。如果不能脱离现实，哪可能有那么多人沉迷。
古代搞数论的，有人做表格，一做就是几十年，图什么？
【在 T********i 的大作中提到】
: 图灵机是内存无限大的计算机，谁能造出来？
: 同理，图灵完备也只能近似。你造不来，也不可能造出来等价的。
: 我见过一些搞数学疯疯癫癫的，一会儿说朋友证明了P==NP然后疯了，留下一堆手稿。
: 一会儿又在研究破解密码的oracle机，还只能是个黑盒子，里面是神经网。反正一笔写
: 不出俩神经出来。
: 我的IoT中控是图灵完备的(除了内存不能无限大)。目前除我外，别人的都不是。
|
|
|
l**o
发帖数: 131 | 61 哦，那是解释器。Lambda Calculus出来的时候不是很在乎如何eval, 当然是alpha,
beta转换，但如何实现不重要，重要的是表达能力强，如此才能着手解决可计算性。
【在 c*******v 的大作中提到】
: universal turing machine对应的lambda是Lisp那个eval。一页纸的代码。
: 王垠还有好多Lisp fans觉得恍然大悟的就是那个部分。
|
x****u
发帖数: 44466 | 62 我对科技史不是特别感兴趣，不过有人复制了19世纪的图灵完备计算机，而19世纪那东
西的原始设计是pascal的
【在 l**o 的大作中提到】
: Pascal calculator, by itself，应该不是图灵完备的，顶多primitive recursive。
: 加上一个人，那就图灵完备了。不过那是科比和我合砍81分。
|
x****u
发帖数: 44466 | 63 这就好比地球绕太阳转符合万有引力定律一样
要是抬杠说，广义相对论下大尺度时间下发射引力波，这个二体问题也不是稳定的
【在 T********i 的大作中提到】
: 图灵机是内存无限大的计算机，谁能造出来？
: 同理，图灵完备也只能近似。你造不来，也不可能造出来等价的。
: 我见过一些搞数学疯疯癫癫的，一会儿说朋友证明了P==NP然后疯了，留下一堆手稿。
: 一会儿又在研究破解密码的oracle机，还只能是个黑盒子，里面是神经网。反正一笔写
: 不出俩神经出来。
: 我的IoT中控是图灵完备的(除了内存不能无限大)。目前除我外，别人的都不是。
|
T********i
发帖数: 2416 | 64 你好歹也是个屁吃第，受过基本的数学训练。怎么说话这么不严谨？
语言可以是图灵完备的。机器就不能那样说。道理不是很简单么？
【在 x****u 的大作中提到】
: 这就好比地球绕太阳转符合万有引力定律一样
: 要是抬杠说，广义相对论下大尺度时间下发射引力波，这个二体问题也不是稳定的
|
g****t
发帖数: 31659 | 65 你查书去吧。纠正都纠正不过来。
: 哦，那是解释器。Lambda Calculus出来的时候不是很在乎如何eval, 当
然是
alpha,
: beta转换，但如何实现不重要，重要的是表达能力强，如此才能着手解决
可计算
性。
【在 l**o 的大作中提到】
: 哦，那是解释器。Lambda Calculus出来的时候不是很在乎如何eval, 当然是alpha,
: beta转换，但如何实现不重要，重要的是表达能力强，如此才能着手解决可计算性。
|
g****t
发帖数: 31659 | 66 他基础知识约等于零。你一问技术细节，他就抓瞎。只能开口乱说。
: 你好歹也是个屁吃第，受过基本的数学训练。怎么说话这么不严谨？
: 语言可以是图灵完备的。机器就不能那样说。道理不是很简单么？
【在 T********i 的大作中提到】
: 你好歹也是个屁吃第，受过基本的数学训练。怎么说话这么不严谨？
: 语言可以是图灵完备的。机器就不能那样说。道理不是很简单么？
|
l**o
发帖数: 131 | 67 Faint, 我要查什么书，我就是数理逻辑出身，虽然不搞Lambda Calculs, 而且最后也
换了方向。 还是读过Church的第一篇和第二篇Lambda Calculus的论文的。实际可(自
动）运作的Lambda Calculs实现是很后面的事情了。
【在 g****t 的大作中提到】
: 你查书去吧。纠正都纠正不过来。
:
:
: 哦，那是解释器。Lambda Calculus出来的时候不是很在乎如何eval, 当
: 然是
: alpha,
:
: beta转换，但如何实现不重要，重要的是表达能力强，如此才能着手解决
: 可计算
: 性。
:
|
x****u
发帖数: 44466 | 68 你这就是少见多怪，说机器是图灵完备的非常常见，比如ENIAC的介绍：
ENIAC (/ˈɛniæk/; Electronic Numerical Integrator and Computer
)[1][2] was the first electronic general-purpose computer.[3] It was Turing-
complete, digital and able to solve "a large class of numerical problems"
through reprogramming.
其实这货只是歪打正着才具有完备性的，本质上还是个高级计算器。
【在 T********i 的大作中提到】
: 你好歹也是个屁吃第，受过基本的数学训练。怎么说话这么不严谨？
: 语言可以是图灵完备的。机器就不能那样说。道理不是很简单么？
|
x****u
发帖数: 44466 | 69 你自己搜一下ENIAC的wiki简介，理工农商医本科第一节计算机课要讲
【在 g****t 的大作中提到】
: 他基础知识约等于零。你一问技术细节，他就抓瞎。只能开口乱说。
:
:
: 你好歹也是个屁吃第，受过基本的数学训练。怎么说话这么不严谨？
:
: 语言可以是图灵完备的。机器就不能那样说。道理不是很简单么？
:
|
T********i
发帖数: 2416 | 70 就那个wiki，你往下看：
ENIAC combined full, Turing-complete programmability with electronic speed...
为啥还要费劲说“Turing-complete programmability”？有些话，专业人士说起来要
啰嗦。民科就不用。
【在 x****u 的大作中提到】
: 你自己搜一下ENIAC的wiki简介，理工农商医本科第一节计算机课要讲
|
|
|
g****t
发帖数: 31659 | 71 这跟你自称是什么出身没有关系。不懂就是不懂。你看个谭浩强的书，一行程序都没写
，那有什么意思呢？
你讲有比图灵universal Turing machine更早的在lambda 模型下的对应结构。那你拿
文献出来。
再者，lambda calculs 算有符号8位整数加法，你写个程序我看看。咱们程序说话好不
好。
: Faint, 我要查什么书，我就是数理逻辑出身，虽然不搞Lambda Calculs,
而且
最后也
: 换了方向。 还是读过Church的第一篇和第二篇Lambda Calculus的论文的
。实际
可(自
: 动）运作的Lambda Calculs实现是很后面的事情了。
【在 l**o 的大作中提到】
: Faint, 我要查什么书，我就是数理逻辑出身，虽然不搞Lambda Calculs, 而且最后也
: 换了方向。 还是读过Church的第一篇和第二篇Lambda Calculus的论文的。实际可(自
: 动）运作的Lambda Calculs实现是很后面的事情了。
|
n******t
发帖数: 4406 | 72 信息時代的最大問題就是造成了你這種一知半解的人，到處search。然後抓到點關鍵詞
就以爲可以當論據。
這里指的ENIAC，也包括了可以在上面跑的程序，（那個年代也沒有現在意義上的軟件
，所以把硬件和相應的程序看成一起也是很自然的）。
Turing-complete都是針對抽象機器而言的，而大部分程序語言背後都有一個機器抽象
，所以常常也說某語言是 Turing-complete.
但是最重要的是，自然語言不可能達到100%精確，但是真正理解了概念的人，會保證自
己的偏差在一個可控範圍內，這就類似數值分析裏面穩定度的概念。但是遇到你這種一
知半解的人，還特別喜歡網上瞎搜的，誤差很快就是爆表。
當然這些話主要是爲了防止你誤人子弟，和你沒什麼關係。
Computer
Turing-
【在 x****u 的大作中提到】
: 你这就是少见多怪，说机器是图灵完备的非常常见，比如ENIAC的介绍：
: ENIAC (/ˈɛniæk/; Electronic Numerical Integrator and Computer
: )[1][2] was the first electronic general-purpose computer.[3] It was Turing-
: complete, digital and able to solve "a large class of numerical problems"
: through reprogramming.
: 其实这货只是歪打正着才具有完备性的，本质上还是个高级计算器。
|
l**o
发帖数: 131 | 73 定义n = Lfx.f(f...fx) , f出现n次。 那么 Add = Lmnfx.(mf)((nf)x)
二元computable function f 的 Universal Machine: Lfmn.fmn , 你用这个作用于
Add, m, n; 经过变换， 出来的结果就会是Lfx.f(f...fx) , f出现m+n次. 但正如我所
说，Lambda Calculus 才提出来的时候，根本不care你如何执行变换，那是实现如LISP
等的问题。 他强调的是你可以用Lambda Calculus表示极多的函数 - computable ones
? 然后着手证明存在一个函数无法计算。
【在 g****t 的大作中提到】
: 这跟你自称是什么出身没有关系。不懂就是不懂。你看个谭浩强的书，一行程序都没写
: ，那有什么意思呢？
: 你讲有比图灵universal Turing machine更早的在lambda 模型下的对应结构。那你拿
: 文献出来。
: 再者，lambda calculs 算有符号8位整数加法，你写个程序我看看。咱们程序说话好不
: 好。
:
:
: Faint, 我要查什么书，我就是数理逻辑出身，虽然不搞Lambda Calculs,
: 而且
: 最后也
|
c*******v
发帖数: 2599 | 74 我说的是有符号数。对有符号数和无符号数不敏感。
entry level程序员你都不合格。
原始的church encode是无符号数。
你从wiki查个church encode是没用的。
你这个答案是0分。
而且我说的是8位，就是要二进制。
没刷过题你搞不定的。
C code把ASCII字符串转成有符号2进制你都不会搞。
不然不可能题目都看不对。
LISP
ones
【在 l**o 的大作中提到】
: 定义n = Lfx.f(f...fx) , f出现n次。 那么 Add = Lmnfx.(mf)((nf)x)
: 二元computable function f 的 Universal Machine: Lfmn.fmn , 你用这个作用于
: Add, m, n; 经过变换， 出来的结果就会是Lfx.f(f...fx) , f出现m+n次. 但正如我所
: 说，Lambda Calculus 才提出来的时候，根本不care你如何执行变换，那是实现如LISP
: 等的问题。 他强调的是你可以用Lambda Calculus表示极多的函数 - computable ones
: ? 然后着手证明存在一个函数无法计算。
|
l**o
发帖数: 131 | 75 我Faint。你说的是8位啊， 你搞个1's complement定义不就行了。
【在 c*******v 的大作中提到】
: 我说的是有符号数。对有符号数和无符号数不敏感。
: entry level程序员你都不合格。
: 原始的church encode是无符号数。
: 你从wiki查个church encode是没用的。
: 你这个答案是0分。
: 而且我说的是8位，就是要二进制。
: 没刷过题你搞不定的。
: C code把ASCII字符串转成有符号2进制你都不会搞。
: 不然不可能题目都看不对。
:
|
g****t
发帖数: 31659 | 76 从与或非开始搞到10进制有符号数只有更难。不然你以为为什么用2进制。
与或非交并补你都分不清，跟有符号加法差一段逻辑呢。刷题去吧。
: 我Faint。你说的是8位啊， 你搞个1's complement定义不就行了。
【在 l**o 的大作中提到】
: 我Faint。你说的是8位啊， 你搞个1's complement定义不就行了。
|
l**o
发帖数: 131 | 77 扯淡，这跟刷题没有多大联系。你现在问的都是，给定一个具体函数，给出他的Lambda
Calculus。这里当然有技巧。但是我说的是第一，church的文章里面已经解决了一大
批函数的表示，这使得他可以声称Lambda Calculus就是computable的代名词。第二，
当然存在一个函数，给不出Lambda Calculus，但你所有刷题中的题目，都不属于这种
函数。除非你蓄意出uncomputable的函数，不过除了那些经典例子，出一个make sense
然而又uncomputable的函数，也不那么容易。
另外，根本不用技巧，TM和Lambada Calculus的等价性是构造证明，你按照那个证明一
步步来就可以将一个TM转换成Lambada Calculus, 我当然不会吃饱饭没事做去转换，然
而存在性可以用那个来旁证。
【在 g****t 的大作中提到】
: 从与或非开始搞到10进制有符号数只有更难。不然你以为为什么用2进制。
: 与或非交并补你都分不清，跟有符号加法差一段逻辑呢。刷题去吧。
:
:
: 我Faint。你说的是8位啊， 你搞个1's complement定义不就行了。
:
|
c*******v
发帖数: 2599 | 78 扯理论你也是胡说八道。你不是说有吗。那你找个比universal Turing Machine更早的
， lambda模型里的，模拟其他机器的lambda函数我看下。
与或非交并补你都不熟悉。怎么数理逻辑出身的。
哪个可计算函数，没有lambda，你给个例子我看看。
不可计算函数，之前我不是贴了吗。除了停机函数.
求所有函数在一个语言下最短编码的函数就是不可
计算的函数。
Lambda
sense
【在 l**o 的大作中提到】
: 扯淡，这跟刷题没有多大联系。你现在问的都是，给定一个具体函数，给出他的Lambda
: Calculus。这里当然有技巧。但是我说的是第一，church的文章里面已经解决了一大
: 批函数的表示，这使得他可以声称Lambda Calculus就是computable的代名词。第二，
: 当然存在一个函数，给不出Lambda Calculus，但你所有刷题中的题目，都不属于这种
: 函数。除非你蓄意出uncomputable的函数，不过除了那些经典例子，出一个make sense
: 然而又uncomputable的函数，也不那么容易。
: 另外，根本不用技巧，TM和Lambada Calculus的等价性是构造证明，你按照那个证明一
: 步步来就可以将一个TM转换成Lambada Calculus, 我当然不会吃饱饭没事做去转换，然
: 而存在性可以用那个来旁证。
|
l**o
发帖数: 131 | 79 为啥要模拟其他机器？ computable function就是有Lambda Calculus的，你把它和输
入放到Lfx.fx里面去就是模拟其执行，执行过程自己是LISP等的事情。
“可计算函数，没有lambda” - 怎么可能，我什么会说这种话。
"所有函数在一个语言下最短编码的函数" - diagonal lemma啊，这就是经典。
【在 c*******v 的大作中提到】
: 扯理论你也是胡说八道。你不是说有吗。那你找个比universal Turing Machine更早的
: ， lambda模型里的，模拟其他机器的lambda函数我看下。
: 与或非交并补你都不熟悉。怎么数理逻辑出身的。
: 哪个可计算函数，没有lambda，你给个例子我看看。
: 不可计算函数，之前我不是贴了吗。除了停机函数.
: 求所有函数在一个语言下最短编码的函数就是不可
: 计算的函数。
:
: Lambda
: sense
|
c*******v
发帖数: 2599 | 80 所以我说你查的那些wiki，拼接一下，根本就纠正不过来。
【在 l**o 的大作中提到】
: 为啥要模拟其他机器？ computable function就是有Lambda Calculus的，你把它和输
: 入放到Lfx.fx里面去就是模拟其执行，执行过程自己是LISP等的事情。
: “可计算函数，没有lambda” - 怎么可能，我什么会说这种话。
: "所有函数在一个语言下最短编码的函数" - diagonal lemma啊，这就是经典。
|
|
|
l**o
发帖数: 131 | 81 LOL， 你说说我那句说错了。你这种“chebyshev停止出错了吗？”的说法，毫无新意。
【在 c*******v 的大作中提到】
: 所以我说你查的那些wiki，拼接一下，根本就纠正不过来。
|
c*******v
发帖数: 2599 | 82 从第一个地方讲起。我早就讲了，你找个和universal Turing Machine对应的lambda里
面的，比图灵UTM早的概念。
你避而不谈。
第二个，你说"你说的是8位啊， 你搞个1's complement定义不就行了。"
嘴说无用。你搞个我看看，或者给个文献也可以。
第三个：
"所有函数在一个语言下最短编码的函数" - diagonal lemma啊，这就是经典。
你上面这话就是胡扯八道。我前面讲过什么叫描述复杂性了。那是个单独的学问。
很明显。你分不清有符号和无符号数。连entry level developer都不能做。
无论谁的话，放一点布尔代数，你就晕了。
不刷题，你自称啥数理逻辑出身，毫无意义。
意。
【在 l**o 的大作中提到】
: LOL， 你说说我那句说错了。你这种“chebyshev停止出错了吗？”的说法，毫无新意。
|
l**o
发帖数: 131 | 83 “从第一个地方讲起。我早就讲了，你找个和universal Turing Machine对应的lambda
里面的，比图灵UTM早的概念。你避而不谈。" - 一直在说，UTM无非就是把一个TM的编
码(可以看成是一个函数）和TM的输入从输入上读出，然后得到TM的结果。Lambda
Calculus Lfx.fx就可以做同样的事，此处f就是你要执行的函数的Lambda Calculus -
(Lfx.fx)fx = fx，说过很多遍了,执行过程不重要。
"你说的是8位啊， 你搞个1's complement定义不就行了。" - 这要什么文献，根本不
用pair来encode， 你就把正负数全编码成正数，加完后的结果，用另外一个编码变成
数。不涉及无限的时候这样做就够了。
第三，""所有函数在一个语言下最短编码的函数" - diagonal lemma啊，这就是经典。
" - 不是在讲uncomputable function吗, 这个function take 一个 function (其编码
）作为input, 输出最短编码。这个函数uncomputable. - 这个证明得用diagonal
lemma
【在 c*******v 的大作中提到】
: 从第一个地方讲起。我早就讲了，你找个和universal Turing Machine对应的lambda里
: 面的，比图灵UTM早的概念。
: 你避而不谈。
: 第二个，你说"你说的是8位啊， 你搞个1's complement定义不就行了。"
: 嘴说无用。你搞个我看看，或者给个文献也可以。
: 第三个：
: "所有函数在一个语言下最短编码的函数" - diagonal lemma啊，这就是经典。
: 你上面这话就是胡扯八道。我前面讲过什么叫描述复杂性了。那是个单独的学问。
: 很明显。你分不清有符号和无符号数。连entry level developer都不能做。
: 无论谁的话，放一点布尔代数，你就晕了。
|
c*******v
发帖数: 2599 | 84 我说算八位符号数加法。
你抄一下wiki里的church coding。答案零分.
还问我哪里错了。话多无补于事。
其他几条压根无从谈起，not even wrong。
到现在一条都改不对。
lambda
-
【在 l**o 的大作中提到】
: “从第一个地方讲起。我早就讲了，你找个和universal Turing Machine对应的lambda
: 里面的，比图灵UTM早的概念。你避而不谈。" - 一直在说，UTM无非就是把一个TM的编
: 码(可以看成是一个函数）和TM的输入从输入上读出，然后得到TM的结果。Lambda
: Calculus Lfx.fx就可以做同样的事，此处f就是你要执行的函数的Lambda Calculus -
: (Lfx.fx)fx = fx，说过很多遍了,执行过程不重要。
: "你说的是8位啊， 你搞个1's complement定义不就行了。" - 这要什么文献，根本不
: 用pair来encode， 你就把正负数全编码成正数，加完后的结果，用另外一个编码变成
: 数。不涉及无限的时候这样做就够了。
: 第三，""所有函数在一个语言下最短编码的函数" - diagonal lemma啊，这就是经典。
: " - 不是在讲uncomputable function吗, 这个function take 一个 function (其编码
|
l**o
发帖数: 131 | 85 LOL, ok, take it easy.
【在 c*******v 的大作中提到】
: 我说算八位符号数加法。
: 你抄一下wiki里的church coding。答案零分.
: 还问我哪里错了。话多无补于事。
: 其他几条压根无从谈起，not even wrong。
: 到现在一条都改不对。
:
: lambda
: -
|
c*******v
发帖数: 2599 | 86 到现在一条都改不对。
有这功夫，你装个emacs，写两行lisp什么都明白了。
【在 l**o 的大作中提到】
: LOL, ok, take it easy.
|
x****u
发帖数: 44466 | 87 你这就是民科声称有了相对论不需要学力学的逻辑
什么机械计算机算Turing-complete是有统一标准的，这不是我定的，你有本事干翻全
世界
...
【在 T********i 的大作中提到】
: 就那个wiki，你往下看：
: ENIAC combined full, Turing-complete programmability with electronic speed...
: 为啥还要费劲说“Turing-complete programmability”？有些话，专业人士说起来要
: 啰嗦。民科就不用。
|
x****u
发帖数: 44466 | 88 你这货就是不懂还要嘴硬满地打滚
地球上所有的人类设计的编程语言都不是严格的Turing complete，你打开指南肯定要
限定递归最大层数，指针字节数等等硬性限制。
小字，最后一页仔细看。不要把儿童编程那一套当成严格定义。
【在 n******t 的大作中提到】
: 信息時代的最大問題就是造成了你這種一知半解的人，到處search。然後抓到點關鍵詞
: 就以爲可以當論據。
: 這里指的ENIAC，也包括了可以在上面跑的程序，（那個年代也沒有現在意義上的軟件
: ，所以把硬件和相應的程序看成一起也是很自然的）。
: Turing-complete都是針對抽象機器而言的，而大部分程序語言背後都有一個機器抽象
: ，所以常常也說某語言是 Turing-complete.
: 但是最重要的是，自然語言不可能達到100%精確，但是真正理解了概念的人，會保證自
: 己的偏差在一個可控範圍內，這就類似數值分析裏面穩定度的概念。但是遇到你這種一
: 知半解的人，還特別喜歡網上瞎搜的，誤差很快就是爆表。
: 當然這些話主要是爲了防止你誤人子弟，和你沒什麼關係。
|
R******e
发帖数: 623 | 89 可怜罗素，希尔伯特，丝口论，艾尔勃朗，哥德尔，塔尔斯基等人生得早，都该拖到他
们成名的时候出生才好。
来-
【在 x****u 的大作中提到】
: 数理逻辑是最近50年才兴起的，基本上是天坑
: PNP研究里最见鬼的东西是，为什么会有这么多NPC问题，这些问题看似完全不相关却有
: 本质上等价的复杂度，意味着什么
: 如果能把PNP关系严格证明，其思路会对可计算理论有巨大的推动作用。毕竟现代已经
: 有够多---1.可计算，2.算出来有巨大不可估量的学术工业价值，3.但你就是算不出来-
: --的问题了
|
R******e
发帖数: 623 | 90 有限状态自动机难道就不是图灵机？咋学自动机理论的？
【在 l**o 的大作中提到】
: 可计算理论，首先研究的就是啥是不可计算的。这一点上Lambda Calculs确实理解起来
: 容易点。现在计算机系教科书，为了好和计算复杂性理论接轨，直接用图灵机来从可计
: 算理论一直玩到计算复杂性理论，基本不讲Lambda Calculus了。另外图灵机和有限自
: 动机的相似性，也是计算机理论教科书独爱图灵机的原因之一。
: 王喜欢Lambda Calculus则多半是因为他Programming Language Theory出身, type
: theory更加熟悉，那儿的理论基础之一是Typed Lambda Calculus
: 数理逻辑的直接用recursive function, 对上面两个都不大待见。
:
: P
|
|
|
R******e
发帖数: 623 | 91 噗通，噗通，青蛙跳下河。
Blum的讲法和教科书的定义都能看出那个n是输入字符串的长度，不长的话，p-space乃
至更高的复杂度也能实现，小鱼儿你就去游泳吧。
【在 x****u 的大作中提到】
: PNP，NPC是和图灵机紧密相关的问题，代表了机械计算能实现的极限
:
: 这个
: 圈子
|
R******e
发帖数: 623 | 92 没多久，看Godel's lost paper，他很快就提到证明长度，证明长度即计算复杂度。
【在 l**o 的大作中提到】
: 上面的列的计算复杂性理论历史就是我的常识，根据这个常识 - NPC,PNP不是和图灵机
: 一起出来的， 图灵机出来的时候，大家考虑的是可计算性，计算复杂度的研究要到很
: 久以后。
: “地球上第一台符合定义的图灵机是什么时候做出来的”， 你是说物理的机器还是理
: 论模型？理论模型当然是图灵写他论文的时候出来的。
|
R******e
发帖数: 623 | 93 第一句话错了。
【在 c*******v 的大作中提到】
: As I said many times, to my best knowledge, there is no
: "universal lambda calculus/recursion function...".
: Nobody had the idea of simulating a computation model on
: another computation model.
: Nobody knew the cost of the simulation is constant.
|
