新未名空间

TheMatrix 写了： 2022年 12月 24日 13:01 这是超级大坑，可能会扩散出很多小坑。

图灵机有三个部分：
1. 读写头。
2. 可擦写可左右移动的“无穷长”纸带。
3. 内部状态和状态转换规则。

纸带相当于计算机的内存 - 这里不考虑硬盘，内存无穷大，不需要硬盘。

读写头这个东西，单独提出来，相当于IO - 内存到CPU之间的。

内部状态不是存在任何地方的，而是蕴含于状态转换规则之中的。状态转换规则相当于程序。所以这个部分也可以说是CPU。前面两项1和2都是固定的，两个图灵机如果说有什么不同，就在这个第3项 - 也就是程序不同。图灵机可以编号，也就是状态转换规则，或者程序，可以编号：1号图灵机，2号图灵机，。。。。程序不同。

还有通用程序：叫universal图灵机。这个图灵机读入纸带上的输入，把数据解释为程序，执行。通用图灵机相当于操纵系统，或者编译执行器。

这是基本理解 - 可能有对的有不对的。大家可以讨论。

verdelite 写了： 2022年 12月 24日 13:27 你这属于东打一榔头西打一棒槌。你的目标是啥，这个问题和你的终极目标的联系是啥？我看你昨天还研究群论、代数，以为你想去搞量子力学问题呢。今天又改为AI了。

Damocles 写了： 2022年 12月 24日 22:59 我觉得UTM应该不能类比成操作系统。操作系统只是load program，但execution还是在cpu上。UTM的输入是另一个TM和这个TM的input。UTM会simulate这个TM的指令。所以UTM更恰当的类比应该是一个emulator。

FGH 写了： 2022年 12月 25日 11:07 现代计算机用的逻辑门不是传统图灵机，但是和图灵机等价，至少是在极限情况下。
量子计算机好像和图灵机不等价。

TheMatrix 写了： 2022年 12月 25日 11:17 量子计算机可以相当于并行计算机。也许可以用多头多纸带图灵机model。

FGH 写了： 2022年 12月 25日 11:07 量子计算机好像和图灵机不等价。

NowWhat2012 写了： 2022年 12月 26日 17:03 上面这个说法好像有争议。

图灵机， 机率图灵机， 和量子计算机之间是否有gap, 好像有不同的说法。 有几个例子显示它们之间有某种间隔，