开个题讨论图灵机

[TheMatrix]

这是超级大坑，可能会扩散出很多小坑。

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

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

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

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

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

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

[verdelite]

这是超级大坑，可能会扩散出很多小坑。

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

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

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

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

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

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

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

[TheMatrix]

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

主要精力在AI。数学，物理，算业余爱好。

[Damocles]

我觉得UTM应该不能类比成操作系统。操作系统只是load program，但execution还是在cpu上。UTM的输入是另一个TM和这个TM的input。UTM会simulate这个TM的指令。所以UTM更恰当的类比应该是一个emulator。

[FGH]

现代计算机用的逻辑门不是传统图灵机，但是和图灵机等价，至少是在极限情况下。
量子计算机好像和图灵机不等价。

[TheMatrix]

我觉得UTM应该不能类比成操作系统。操作系统只是load program，但execution还是在cpu上。UTM的输入是另一个TM和这个TM的input。UTM会simulate这个TM的指令。所以UTM更恰当的类比应该是一个emulator。

这里的level关系我也不是很清晰。

[TheMatrix]

现代计算机用的逻辑门不是传统图灵机，但是和图灵机等价，至少是在极限情况下。
量子计算机好像和图灵机不等价。

量子计算机可以相当于并行计算机。也许可以用多头多纸带图灵机model。

[牛河梁]

量子计算机可以相当于并行计算机。也许可以用多头多纸带图灵机model。

你这想法是对的，如果量子过程是可数的。

[NowWhat2012]

量子计算机好像和图灵机不等价。

上面这个说法好像有争议。

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

[牛河梁]

上面这个说法好像有争议。

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

量子计算机还不存在。所以无法评论。取决于技术路线，量子计算机也可能是不确定图灵机。举例说光子过1/2分光镜。