图灵机

一种定义算法的理想机器，由*图灵于1936年定义。它对电子计算机的产生有一定影响。直观上，图灵机可以看成一个附有两端无穷的带子的黑箱，带子由联成串的方格组成，黑箱和带子由一指针相联。图灵机只有有穷多个状态和有穷多条指令。计算的每一步中，根据机器所处的状态和指针所指的方格上的符号，指令可决定机器干什么事并转入什么状态。开始计算时，机器处于开始状态，然后一步步地根据指令进行计算，直到无法继续时停止。带上信息即为计算的结果。1939年图灵把图灵机概念推广为带有外部信息源的图灵机。