艾伦·图灵（Alan Turing）于 1936 年提出图灵机的概念[15]，图灵机是一种无限记忆自动机，如图3-1 所示。它由一条无限长的纸带、一个读写头、一个状态寄存器和一套控制规则组成。纸带上的格子可以记录“0”或“1”。在带子上方移动一个读写磁头，它是由有限记忆自动机 L 来控制的。自动机 L 按周期工作，关于符号(0 或 1)的信息，由磁头从带子上读出，而反馈给 L 的输入。磁头根据在每个周期中从自动机 L 得到的指令而工作，它可以停留不动或向左、向右移动一小格。与此同时，磁头从自动机 L 接收指令，执行收到的指令，它就可以更换记录在磁头下面方格中的符号。
图 3-1 图灵机
图灵机的工作唯一地决定于带子方格的初始存储和控制自动机的变换算子，这个算子可以表示为转移表的形式。我们用𝑆𝑆𝑖𝑖 (𝑆𝑆0＝0, 𝑆𝑆1
＝1)表示磁头读出的符号；用𝑅𝑅𝑗𝑗（𝑅𝑅0=停止，𝑅𝑅1=左移，𝑅𝑅2=右移）表示
移动磁头的指令；用𝑞𝑞𝑘𝑘（k＝1，2，...，n）表示控制自动机的状态，则表 3-1 给出了图灵机状态转移表。
表 3-1 图灵机状态转移表
输 入 | 状 态 | |
𝑆𝑆0 = 0 | 𝑆𝑆1 = 1 | |
𝑞𝑞1 | 𝑆𝑆0, 𝑅𝑅2, 𝑞𝑞𝑘𝑘 | 𝑆𝑆1, 𝑅𝑅1, 𝑞𝑞𝑚𝑚 |
𝑞𝑞2 | 𝑆𝑆1, 𝑅𝑅0, 𝑞𝑞𝑠𝑠 | 𝑆𝑆0, 𝑅𝑅2, 𝑞𝑞1 |
𝑞𝑞3 | 𝑆𝑆1, 𝑅𝑅1, 𝑞𝑞𝑝𝑝 | 𝑆𝑆0, 𝑅𝑅2, 𝑞𝑞2 |
从表 2-1 中看出，自动机 L 的动作依赖于输入 q 和它的状态 S。对于给定值 q 和 S，将有 q，R，S，这三个量的某一组值与之对应。这三个量分别指明，磁头应在磁带上记录什么符号q，移动磁头的指令 R 是什么，自动机 L 将变到什么新状态S。在自动机 L 的状态S 中至少应当有这样一个状态 S* ，对于这个状态来说，磁头不改变符号 q，指令R=𝑅𝑅0（停止），而自动机 L 仍处于停止位置 S*。
图灵机看似简单的结构，却可以在理论上模拟数字计算机的一切运算，成为了计算机信息加工的理论基础。1950 年，图灵设计了图灵测验，通过问答来测试计算机是否具有同人类相当的智力。