概览

图灵奖模型发明出来是为了形式化“计算”，是为了明确地定义“算法”。图灵通过图灵奖模型例举了“不可判定”问题的存在。

模型描述

图灵奖模型可看作是由一条“无限长”的纸带、一个磁头、一组状态转换规则（规则表）、一套字母表和一个状态集合组成的。

• 纸带被分割成一个又一个的单元 (cell)，可以看作是纸带上的格子，这些单元一个连着一个，每个单元上可以记录符合；一个单元只能记录一个符合，符合的范围由一个字母表描述，字母表必须有一个“空”符号；纸带带初始符号（也叫输入符号）需要定义；
• 在任一时刻，磁头 (head) 指向纸带上的一个单元，磁头每一步只能移动一格（或者不移动），在每一步计算中，磁头读取纸带上的符号，根据读取到的符号、自身的“状态” (state) 以及规则表来决定该向这个单元写入哪个符号，向左、向右移动还是不移动；磁头的状态由一个有限的状态集定义，状态集里面至少有一个“停机” (halt) 状态，磁头切到停机状态后，图灵奖停机；

下列是一个示例图灵机的描述：

• 字母表：0, 1，规定 0 是空符号；
• 状态集：{A, B, C, 停机} 这4 个状态；
• 初始状态：A；
• 纸带的输入符号：{0}；

状态转移表：

格式 (当前状态, 读取到的符号) → (写入符号, 移动方向, 下一个状态)

• (A, 0) → (1, 右, B);
• (A, 1) → (1, 左, C);
• (B, 0) → (1, 左, A);
• (B, 1) → (1, 右, B);
• (C, 0) → (1, 左, B);
• (C, 1) → (1, 右, 停机);

现在，我们从初始纸带 {1} 开始演算，下划线表示磁头位置：