闲说Chomsky Hierarchy和马尔可夫链

[forecasting]

乔姆斯基分层（Chomsky Hierarchy）是可计算的另一种形式化，最内层是Regular language，对应的语法为 regular grammar，等价于（就生成的语言相同而言）有限状态自动机（finite state automata，FSA），等价于有限状态马尔科夫链（finite state Markov chain，FSM）。稍外一层是上下文无关的语言（context free language，CFL），对应的语法是CFG，对应的自动机是PDA，再外一层是上下文有关的语言（context sensitive language，CSL），语法是CSG，对应的自动机是LBA，最外一层是c. e. language(computably enumerable language),对应的语法是c. e. G，或者RE。这是人可以写出语法的语言，对应于图灵机。只有regular language, regular grammar, FSA, 对应于有限状态马尔可夫链。是有限状态的。接触过随机过程的都知道马尔科夫链有无限状态，有限状态。无限状态对应于什么语法或自动机，好像没人注意到，猜测是不是超出了c.e. language或者图灵机

[牛河梁]

接触过随机过程的都知道马尔科夫链有无限状态，有限状态。无限状态对应于什么语法或自动机，好像没人注意到，猜测是不是超出了c.e. language或者图灵机

老牛以前也没想过这个问题。所以以下纯属几秒钟之内拍脑袋：

假设：定义有限状态对应countable finite；无限状态对应countable infinite。

1/ 那么无限状态机器的下界是图灵机，上界直觉上对应实数；但是

2/ (Countable) infinite（无穷）的特性很奇妙。不要直接套直觉。
2a/ 要看具体模型能不能一级一级reduction及是否“closed”（用词可能不准确）
2b/ 举例说，确定图灵机和不确定图灵机的能力等价，虽然不确定图灵机可以countable infinite次“guess”。类似的，P和NP能力等价。

所以，不能排除（可数无穷）无限可能状态马尔可夫链仍然等价于有限可能状态。

[wdong]

每个实数对应一系列等价的程序吧。比如pi，所有计算pi的程序算出来都是pi，所以pi就和这一系列程序等价。pi本身作为一个数不可穷尽，表示成程序，想算几位就算几位，但是不可能算完。然后可以考察其性质。 显然任何一个对应计算pi的程序的自动机都是无限状态的。

有理数里面有无限循环小数，虽然无限但是循环，所以可以用有限状态机计算。

所以：

整数和有限小数：停机的有限状态自动机
无限循环小数：不停机的有限状态自动机
无限不循环小数：不停机的无限状态自动机

我昨天还想发帖说这个事。就是我觉得费曼图不可normalize和pi不可计算穷尽是一回事，但是两者都可以想算多少就算多少。你输进去能量有多大，费曼图就展开到第几级。如果输进去创世的能量，费曼图就能展开到整个宇宙。且不说质能方程早就有了，至少到对撞机撞出新粒子时就应该想到了，观察结果的细节和输入的能量有关。假设有一个可以有限求和的费曼图，反而倒出问题了。

[TheMatrix]

乔姆斯基分层（Chomsky Hierarchy）是可计算的另一种形式化，最内层是Regular language，对应的语法为 regular grammar，等价于（就生成的语言相同而言）有限状态自动机（finite state automata，FSA），等价于有限状态马尔科夫链（finite state Markov chain，FSM）。稍外一层是上下文无关的语言（context free language，CFL），对应的语法是CFG，对应的自动机是PDA，再外一层是上下文有关的语言（context sensitive language，CSL），语法是CSG，对应的自动机是LBA，最外一层是c. e. language(computably enumerable language),对应的语法是c. e. G，或者RE。这是人可以写出语法的语言，对应于图灵机。只有regular language, regular grammar, FSA, 对应于有限状态马尔可夫链。是有限状态的。接触过随机过程的都知道马尔科夫链有无限状态，有限状态。无限状态对应于什么语法或自动机，好像没人注意到，猜测是不是超出了c.e. language或者图灵机

[forecasting]

你又不是不知道chatGPT和DS经常一本正经地胡说八道。这等价是就其生成的语言而言的，就是它们生成的语言彼此相同

[TheMatrix]

你又不是不知道chatGPT和DS经常一本正经地胡说八道。这等价是就其生成的语言而言的，就是它们生成的语言彼此相同

也就是从图论的意义上是等价的。

其实马尔可夫链不能生成语言，因为它状态转移不是deterministic的。一定要说它能生成语言，那也是要先转一道弯，也就是先把它在图论上和finite state automata等价起来，然后再由FSA生成语言。

这是我觉得。

[forecasting]

也就是从图论的意义上是等价的。

其实马尔可夫链不能生成语言，因为它状态转移不是deterministic的。一定要说它能生成语言，那也是要先转一道弯，也就是先把它在图论上和finite state automata等价起来，然后再由FSA生成语言。

这是我觉得。

从FSA到Turing Machine，都有deterministic和non-deterministic两种，，deterministic和non-deterministic FSA和Turing Machine等价。这都是老掉牙的结果了。

[wdong]

也就是从图论的意义上是等价的。

其实马尔可夫链不能生成语言，因为它状态转移不是deterministic的。一定要说它能生成语言，那也是要先转一道弯，也就是先把它在图论上和finite state automata等价起来，然后再由FSA生成语言。

这是我觉得。

行内不叫生成语言，叫accept语言。就是下一个字在当前状态支出去的几个里面能找到。

[forecasting]

我不喜欢中英文夹杂，可还是避不开。有时候我就成了第一个翻译者。

[forecasting]

每个实数对应一系列等价的程序吧。比如pi，所有计算pi的程序算出来都是pi，所以pi就和这一系列程序等价。pi本身作为一个数不可穷尽，表示成程序，想算几位就算几位，但是不可能算完。然后可以考察其性质。 显然任何一个对应计算pi的程序的自动机都是无限状态的。

有理数里面有无限循环小数，虽然无限但是循环，所以可以用有限状态机计算。

所以：

整数和有限小数：停机的有限状态自动机
无限循环小数：不停机的有限状态自动机
无限不循环小数：不停机的无限状态自动机

我昨天还想发帖说这个事。就是我觉得费曼图不可normalize和pi不可计算穷尽是一回事，但是两者都可以想算多少就算多少。你输进去能量有多大，费曼图就展开到第几级。如果输进去创世的能量，费曼图就能展开到整个宇宙。且不说质能方程早就有了，至少到对撞机撞出新粒子时就应该想到了，观察结果的细节和输入的能量有关。假设有一个可以有限求和的费曼图，反而倒出问题了。

程序有可数无限个，实数有不可数无限个。每个实数怎么对应一系列等价的程序？不知道有不可计算实数吗？

[wdong]

程序有可数无限个，实数有不可数无限个。每个实数怎么对应一系列等价的程序？不知道有不可计算实数吗？

我还真不知道不可计算数

[heteroclinic]

[quote=forecasting post_id=5034739 time=1739788394 user_id=9349]
乔姆斯基分层（Chomsky Hierarchy）是可计算的另一种形式化，最内层是Regular language，对应的语法为 regular grammar，等价于（就生成的语言相同而言）有限状态自动机（finite state automata，FSA），等价于有限状态马尔科夫链（finite state Markov chain，FSM）。稍外一层是上下文无关的语言（context free language，CFL），对应的语法是CFG，对应的自动机是PDA，再外一层是上下文有关的语言（context sensitive language，CSL），语法是CSG，对应的自动机是LBA，最外一层是c. e. language(computably enumerable language),对应的语法是c. e. G，或者RE。这是人可以写出语法的语言，对应于图灵机。只有regular language, regular grammar, FSA, 对应于有限状态马尔可夫链。是有限状态的。接触过随机过程的都知道马尔科夫链有无限状态，有限状态。无限状态对应于什么语法或自动机，好像没人注意到，猜测是不是超出了c.e. language或者图灵机
[/quote]

无限状态就是书呆子在纸上爬拉爬拉，外行跟着瞎起哄
无限状态信息怎么编址
书很早就在老买卖提指出，你编址维护一个１G的路由表开销是多少，１T呢？
这个热力学早就指出这是开放边界问题。没有任何工程意义。

[tfusion]

每个实数对应一系列等价的程序吧。比如pi，所有计算pi的程序算出来都是pi，所以pi就和这一系列程序等价。pi本身作为一个数不可穷尽，表示成程序，想算几位就算几位，但是不可能算完。然后可以考察其性质。 显然任何一个对应计算pi的程序的自动机都是无限状态的。

有理数里面有无限循环小数，虽然无限但是循环，所以可以用有限状态机计算。

所以：

整数和有限小数：停机的有限状态自动机
无限循环小数：不停机的有限状态自动机
无限不循环小数：不停机的无限状态自动机

我昨天还想发帖说这个事。就是我觉得费曼图不可normalize和pi不可计算穷尽是一回事，但是两者都可以想算多少就算多少。你输进去能量有多大，费曼图就展开到第几级。如果输进去创世的能量，费曼图就能展开到整个宇宙。且不说质能方程早就有了，至少到对撞机撞出新粒子时就应该想到了，观察结果的细节和输入的能量有关。假设有一个可以有限求和的费曼图，反而倒出问题了。

有无数无理数是不可计算的，也就是说完全超出图灵机能力

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

[forecasting]

无限状态就是书呆子在纸上爬拉爬拉，外行跟着瞎起哄
无限状态信息怎么编址
书很早就在老买卖提指出，你编址维护一个１G的路由表开销是多少，１T呢？
这个热力学早就指出这是开放边界问题。没有任何工程意义。

图灵机带子的格子还无限多呢，工程怎么实现？你受的教育都是工科？工科也得懂极限，可数无限，不可数无穷这些吧？没当场指着老师鼻子反驳？

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

[heteroclinic]

图灵机带子的格子还无限多呢，工程怎么实现？你受的教育都是工科？工科也得懂极限，可数无限，不可数无穷这些吧？没当场指着老师鼻子反驳？

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

what i am saying : 开放边界问题 = infinite status . So don't over-hype. Focus on observations, focus on concrete questions.

[heteroclinic]

带子的格子 can be infinite, but status, if information bandwith doubles,
I think the assumption is if statuses are independent from the volume of information (Turing never said that).

[heteroclinic]

军版的内容处理了

[牛河梁]

程序有可数无限个，实数有不可数无限个。每个实数怎么对应一系列等价的程序？不知道有不可计算实数吗？

考虑到不少版上有不少“文科”生/发考题，甚至自称CS科班的99%以上可能也不懂。老牛再说具体一点。

这要到（图灵的）祖师爷哥德尔那里去找灵感。对，就是娶了脱衣舞娘和爱因斯坦散步那一位。也是发现美国宪法允许美国公民成为独裁者（哥德尔漏洞）那一位。

如果你的马尔可夫链只有有限不同状态。那么显然是可数的。每一个状态可以用一个可数（整）数表示。这个状态集（因为有限）也是可数的，可以对应一个（很大的）整数。这是哥德尔发明的，被图灵用于其通用图灵机。这个大整数（code）就是通用图灵机用于模拟任意图灵机的代码。

但在无限（可数无穷）不同状态下，虽然每一个状态仍然对应一个整数（可数），但状态集未必可数。但可以用一个实数表示。这需要一点编码技巧。举例说，每个状态是一个N进制整数，可以引入一个N+1符号作为分隔符，将（可数）无限个状态串起来跟在0.后面（写成小数），这个串（集）对应一个N+1进制（0到1之间）的实数。因此直觉上，无限状态的上限是实数。

但是，即使无穷位的实数也有可能对应可数数。举例说，0.999... = 1。我们知道的是实空间比可数空间“大”。但要确认问题的域真的是实空间而不仅仅是实空间的一个可数子集，只是上界是实空间（这也是老牛批评弃婴糊涂的地方）。对涉及无穷的问题，需要具体问题具体研究。千万不能拍脑袋。

[牛河梁]

无限状态就是书呆子在纸上爬拉爬拉，外行跟着瞎起哄
无限状态信息怎么编址
书很早就在老买卖提指出，你编址维护一个１G的路由表开销是多少，１T呢？
这个热力学早就指出这是开放边界问题。没有任何工程意义。

涉及无穷的问题想不清楚最好承认自己不明白。老牛也曾经早上打晚上的嘴巴，第二天又反转过来。

（可数）无限状态信息每一种状态都可以用一个整数表示。

希望你能想明白。你要还是想不明白，老牛再科普。

[TheMatrix]

行内不叫生成语言，叫accept语言。就是下一个字在当前状态支出去的几个里面能找到。

嗯。你这么说我就清楚了。