这是超级大坑,可能会扩散出很多小坑。
图灵机有三个部分:
1. 读写头。
2. 可擦写可左右移动的“无穷长”纸带。
3. 内部状态和状态转换规则。
纸带相当于计算机的内存 - 这里不考虑硬盘,内存无穷大,不需要硬盘。
读写头这个东西,单独提出来,相当于IO - 内存到CPU之间的。
内部状态不是存在任何地方的,而是蕴含于状态转换规则之中的。状态转换规则相当于程序。所以这个部分也可以说是CPU。前面两项1和2都是固定的,两个图灵机如果说有什么不同,就在这个第3项 - 也就是程序不同。图灵机可以编号,也就是状态转换规则,或者程序,可以编号:1号图灵机,2号图灵机,。。。。程序不同。
还有通用程序:叫universal图灵机。这个图灵机读入纸带上的输入,把数据解释为程序,执行。通用图灵机相当于操纵系统,或者编译执行器。
这是基本理解 - 可能有对的有不对的。大家可以讨论。