图灵机

1 定义：

2 动作

解释一下：当前状态为q，读头符合为X，现将读头符号从X替换为Y，向左移动一格，状态转换为p。下面来看一个例子：

上面是状态转移图的形式，下面用七元组和状态转移表来等价展示例一：

3 瞬时描述

背景

为了描述图灵机的总体的格局，我们需要先给出瞬时描述的概念和定义。

定义

图灵机虽有无穷长的带, 但经过有限步, 带上非空内容总是有限的.。因此用全部非空符号、当前状态及带头位置，定义图灵机的瞬时描述(ID) 为

X1 X2···Xi−1 q Xi Xi+1···Xn

1. 图灵机的当前状态 q;
2. 带头在左起第 i 个非空格符 Xi 上;
3. X1X2···Xn 是最左到最右非空格内容.

4 转移符号

稍微解释一下(q,Xi) = (p,Y,L)，ID初始为X1X2…Xi-1 q Xi… 经过(q,Xi)(p,Y,L)的转移后，将Xi 替换为Y，往左移动一格，且从状态q变为状态p。

5 图灵机的语言

因此，我们无法判断是因为时间不够还没有算到结尾而不停机，还是说陷入了死循环而不停机。因此我们给出下面的定义。

一个例子