图灵机
计算机导论课学的东西，记一下。
图灵机为可计算理论奠定了基础。
图灵可计算：给定符号序列A，用图灵机可以得出符号序列B，从A到B就是图灵可计算的。
组成部分：input（存储带输入），output（输出读写头移动），inner（内部机器状态），program（程序）
- 存储带：带子上划分格子，每个格子一个符号；有一个规定好的所有可能出现符号的字母表
- 读写头：每次可以从存储带上读出1个符号；可以擦除、改写这个符号；可以移动（左1，右1，不动）
- 控制器：存有指令序列程序；控制器每个时刻处于一定的机器状态；读写头先从带子上读出符号，再结合当时的机器状态，依据程序，进行书写或者移动，之后决定是否改动机器状态。