新未名空间

forecasting 写了： 2025年 2月 17日 16:36 图灵机带子的格子还无限多呢，工程怎么实现？你受的教育都是工科？工科也得懂极限，可数无限，不可数无穷这些吧？没当场指着老师鼻子反驳？

我这个回复没看版面跑军事版去了

图灵格子无限多没问题。注意图灵机里的格子都没有地址。图灵机只是加1和减1移动当前格子位置。这就是可数（无穷）的精妙。

工程上也没有问题。因为图灵机从不需要无穷的格子。所有图灵机ACCEPT的输入（能干的活）都只需要有限的格子。给图灵机无限（unlimited）的资源，但图灵机其实只（能）使用了有穷（finite）的资源。对某一输入使用无穷（infinite）资源的图灵机永不停机，因此也不会ACCEPT这个输入。

想不明白不要紧。大多数，如果不是全部，现在的CS千老考题都没想明白。知道就好。

BTW：这是证明P = NP的一个关键所在。

牛河梁 写了： 2025年 2月 17日 17:18 图灵格子无限多没问题。注意图灵机里的格子都没有地址。图灵机只是加1和减1移动当前格子位置。这就是可数（无穷）的精妙。

工程上也没有问题。因为图灵机从不需要无穷的格子。所有图灵机ACCEPT的输入（能干的活）都只需要有限的格子。给图灵机无限（unlimited）的资源，但图灵机其实只（能）使用了有穷（finite）的资源。对某一输入使用无穷（infinite）资源的图灵机永不停机，因此也不会ACCEPT这个输入。

想不明白不要紧。大多数，如果不是全部，现在的CS千老考题都没想明白。知道就好。

BTW：这是证明P = NP的一个关键所在。

尼玛P=NP你就宣称了？

大部分CS科学家认为P!=NP。但是现在没人能证明而已。

tfusion 写了： 2025年 2月 17日 18:12 尼玛P=NP你就宣称了？

大部分CS科学家认为P!=NP。但是现在没人能证明而已。

对你不知道的事情最好说你不知道。老牛相信不少人知道。Viewed好几千Download也近千了。

别像另一版版大那样，他不知道的就断定没有。

科研里除了Established也有Deep State。

老牛选择相信。

牛河梁 写了： 2025年 2月 17日 18:19 对你不知道的事情最好说你不知道。老牛相信不少人知道。Viewed好几千Download也近千了。

别像另一版版大那样，他不知道的就断定没有。

科研里除了Established也有Deep State。

老牛选择相信。

牛大妈CS半路出家的吧？都是一知半解不懂装懂

老牛

Can you please be formal with your theories?
我不大相信你理科或工科背景，直觉
这个你在企业里白话保证管理层有机会就会干掉你，因为你令他们很尴尬。
你也帮我复习一下图灵机，你怎么严格定义status tape

我觉得唯一严谨的就是真值表。后来高级语言就偏离了严谨。符号表达脱离工程的有限性和完备性。进而，模拟被演绎成了预言家。

tfusion 写了： 2025年 2月 17日 18:24 牛大妈CS半路出家的吧？都是一知半解不懂装懂

嗯。老牛也想知道有多少比老牛出家更早的。代表简中最高科学水平的买提那么多屁挨着地那么多大肠科学家，就没几个能比老牛能吹。

老牛没打算要谁信。就像你也没必要相信老牛有多少米，每年收入高得足以对克雷奖金、炸药奖金没兴趣。

你的问题是想不明白，不存在，一个个体能编码“无穷多种”可能状态放在一个格子里是吧。你能不能放一个变量进去。或者物理地，放一个量子（态）进去。

不要你只知道有锤子（真值表），世界上所有的问题都只能是钉子。如果老牛创过业有自己公司产品客户呢？

老牛当然令周围的人尴尬。老牛在研究生院的时候就开顶级豪车。院士们还在走路骑自行车上班。教授开个宝马3。老牛的老板开日产。

heteroclinic 写了： 2025年 2月 17日 18:32 老牛

Can you please be formal with your theories?
我不大相信你理科或工科背景，直觉
这个你在企业里白话保证管理层有机会就会干掉你，因为你令他们很尴尬。
你也帮我复习一下图灵机，你怎么严格定义status tape

我觉得唯一严谨的就是真值表。后来高级语言就偏离了严谨。符号表达脱离工程的有限性和完备性。进而，模拟被演绎成了预言家。

牛河梁 写了： 2025年 2月 17日 18:40 老牛没打算要谁信。就像你也没必要相信老牛有多少米，每年收入高得足以对克雷奖金、炸药奖金没兴趣。

你的问题是想不明白，不存在，一个个体能编码“无穷多种”可能状态放在一个格子里是吧。你能不能放一个变量进去。或者物理地，放一个量子（态）进去。

不要你只知道有锤子（真值表），世界上所有的问题都只能是钉子。如果老牛创过业有自己公司产品客户呢？

老牛当然令周围的人尴尬。老牛在研究生院的时候就开顶级豪车。院士们还在走路骑自行车上班。教授开个宝马3。老牛的老板开日产。

我和总理吃过饭，一起吃饭的还有进秦城的
我还有同学被捅死的

后来书不知道发什么神经，觉得这些玩意儿比流行音乐高尚。
放弃你的原则，魔鬼可能收买你的灵魂，但也可能说不。

书再来高尚一下
不完备的认知只能让我们原地踏步

heteroclinic 写了： 2025年 2月 17日 18:44 我和总理吃过饭，一起吃饭的还有进秦城的
我还有同学被捅死的

后来书不知道发什么神经，觉得这些玩意儿比流行音乐高尚。
放弃你的原则，魔鬼可能收买你的灵魂，但也可能说不。

老牛没和总理吃过饭。不过不排除以后会有机会。自信一点，和总理吃饭和皇上握手没啥。DS那位不就做到了。

老牛就是闲的。路过看见有几位脑子迷糊转不出来说两句。不相信读不懂的老牛就笑笑走开。

智商不同没法交流。特别是智商不同还特别自信的。当然，包括你们也可以这样看老牛。

老牛活得够老了。知道很多山外的山楼外的楼。你们要喜欢沉浸在自己的多巴胺里老牛没意见。

heteroclinic 写了： 2025年 2月 17日 18:48 书再来高尚一下
不完备的认知只能让我们原地踏步

有些问题中学时代就因为西爱死上电视专访的半路出家老牛想了几十年了。老牛也没指望别人一下子能读懂。也不介意谁认为老牛是白痴。

牛河梁 写了： 2025年 2月 17日 18:55 有些问题中学时代就因为西爱死上电视专访的半路出家老牛想了几十年了。老牛也没指望别人一下子能读懂。也不介意谁认为老牛是白痴。

我个人在图灵机的认识上是这样成长
我很长时间没有精力去认真读书。主要在买买体获得信息的摘要。
现实工作的的一个主要问题是为什么高级语言写出来的程序为什么这么烂，一个小逼养程序，excuse my language. 十五分钟打印了上百万个异常。
书自己琢磨，那么，理论上我们认为图灵机可以解决任何计算问题。但实际上，图灵机一个不完备的地方就是，机器的状态和信息的尺码，相关还是不相关。据我所知，图灵没有认识到这个问题。

图灵机只是一个模型，用于解决一个指定的数学（逻辑）问题。图灵机和现代计算机没几毛钱关系。在现实生活/工作中遇不到涉及图灵机问题。

“任何”这种词是被用烂了。可以看作一种循环定义。举例说，定义图灵机不能解决的问题不是可计算问题。那么图灵机能解决所有可计算问题。

事实上，图灵机不能解决所有问题。这正是图灵的成名作及（通用）图灵机的（唯一）作用。

关于状态编码老牛再给一个方法。不要总想着必需用多少位二进制数字。那只是有限状态图灵机常用的表示。你可以用一个圆盘和一个转动指针表示不同状态。

BTW：老牛没读到过这种状态表示法。保留所有版权。

这是一个小的思维技巧。当你要处理0到无穷整数无从入手的时候，把问题转为0到1之间的小数。数学上一下子就把无限区段（但有限精度）问题转化为有限区段（无限精度）。

至于其它，不是数学，老牛很难评论。也许烂程序不因为烂语言，而是因为烂程序猿。特别是非CS科班程序猿。可以想象CS科班的会多招这些人多势众的劣币恨。

heteroclinic 写了： 2025年 2月 17日 19:08 我个人在图灵机的认识上是这样成长
我很长时间没有精力去认真读书。主要在买买体获得信息的摘要。
现实工作的的一个主要问题是为什么高级语言写出来的程序为什么这么烂，一个小逼养程序，excuse my language. 十五分钟打印了上百万个异常。
书自己琢磨，那么，理论上我们认为图灵机可以解决任何计算问题。但实际上，图灵机一个不完备的地方就是，机器的状态和信息的尺码，相关还是不相关。据我所知，图灵没有认识到这个问题。

跑题了很明显学理工争辩的是试图解决下一个问题
另外一个流派是试图找到下一个傻子

图灵机不能解决所有计算问题，只能解决教科书上能画下来的问题
无限没有意义，我们实现不了它。
讨论来去有要回到数学，得是希尔伯特空间，我真的不懂。说是距离可以测量。

有时间再来跟跟，谢谢开帖以及积极参与

heteroclinic 写了： 2025年 2月 17日 19:55 无限没有意义，我们实现不了它。

这一点是误解。不过老牛也不准备在这里展开。

只是让你有空可以试想一下，如果你发现你可以实现/解决无穷问题，你的文明会有多大的不同。

举例说，微积分。

heteroclinic 写了： 2025年 2月 17日 19:55 图灵机不能解决所有计算问题，只能解决教科书上能画下来的问题
无限没有意义，我们实现不了它。
讨论来去有要回到数学，得是希尔伯特空间，我真的不懂。说是距离可以测量。

有时间再来跟跟，谢谢开帖以及积极参与

图灵机是很general的一个论断，就好比说你有美国出生公民权，就有肯能当总统，实际上差了十万八千里。

Grok的回答
乔姆斯基层次（Chomsky Hierarchy）是一种对形式语言进行分类的系统，它将语言分为四个层次，每个层次对应一种不同的自动机模型。以下是这些层次与相应自动机之间的对应关系概述：

0型：无限制文法（Unrestricted Grammar）
语言类别：递归可枚举语言（Recursively Enumerable Languages）
自动机：图灵机（Turing Machine）
能够识别或生成任何形式的语言，无限制的内存和计算能力，可以处理任何可计算的问题。
1型：上下文相关文法（Context-Sensitive Grammar）
语言类别：上下文相关语言（Context-Sensitive Languages）
自动机：线性有界自动机（Linear Bounded Automaton, LBA）
内存使用受到输入长度的线性限制，只能识别或生成那些规则左侧和右侧上下文相关的语言，比图灵机限制更多，但仍然可以处理非常复杂的语言。
2型：上下文无关文法（Context-Free Grammar）
语言类别：上下文无关语言（Context-Free Languages）
自动机：下推自动机（Pushdown Automaton, PDA）
使用一个栈来提供额外的内存，允许识别或生成那些规则不依赖于上下文的语言，比如编程语言的语法结构。
3型：正则文法（Regular Grammar）
语言类别：正则语言（Regular Languages）
自动机：
有限状态自动机（Finite State Machine, FSM），或称为有限自动机（Finite Automaton, FA）
只能使用有限的内存状态，不需要额外的存储结构（如栈），适用于识别或生成模式简单、重复性的语言，如简单的字符串匹配。
对应关系总结：
0型（图灵机）包含并扩展了所有其他类型的语言能力。
1型（线性有界自动机）可以识别所有2型和3型语言，但不能识别所有0型语言。
2型（下推自动机）可以识别所有3型语言，但不能识别所有1型语言。
3型（有限状态自动机）是最基本的，只能处理最简单的语言结构。
这种层次结构展示了语言复杂度的递增，同时也反映了计算能力的增加。每个层次的自动机模型都是在前一层次的基础上增加了某种形式的计算或存储能力，从而能够处理更复杂的语言结构。

诸位的讨论里有不准确或不恰当的地方。我比较随性，没兴趣，就不多说了。有经典著作。

tfusion 写了： 2025年 2月 17日 16:17 有无数无理数是不可计算的，也就是说完全超出图灵机能力

另外，程序等价性也是图灵不可计算问题。

实数集的测度为1的话，可计算数或半可计算数的集合测度为0，不可计算实数集合的测度为1。更直观地说，半可计算数有可数无限个，不可计算数有不可数无限个。其实可以描述几个不可计算实数，甚至写出这几个实数的前几位。

程序等价性不可判定，是另外一个问题，他只用了这术语，没牵涉是否可判定/可计算的问题