（图8-1：图灵机）
1纸带
2读写头
读取当前单元格里的字符；
将一个字符写入当前单元格。
图中的控制器可分解为下面的逻辑部件：
字母表包括了输入纸带单元格上可以有的字符，读写头可以写入单元格的字符，比如字符集是{“1”“0”“+”“=”“︺”}。
图灵机在任意时刻都处于一种状态下，所有的状态构成状态集{s0、s1、s2、s3、s4、s5}，其中包括：
停机状态s5、当图灵机进入此状态时，机器就停止运行，此状态下纸带留下的字符为计算结果或者问题无解。
读写头读取当前单元格的字符，结合当前机器的状态，可决定：
二、图灵机的响应操作，包括：
写入：在当前单元格写入字符集中的一个字符；
图灵机的操作可抽象为：（（当前状态、当前读入）→（新状态、当前写入、移动方向））。一个图灵机可能的（当前状态、当前读入）组合称为其格局，它们对应的控制规则决定了图灵机的行为。我们构造个简单的例子，这个例子是二进制个位数的加法运算。设计七种状态：（整体可以有不同的设计）
s1：被加数=1；
s3：被加数、加数=1；
s5：被加数、加数=0；
字符表为{“1”“0”“+”}。
可制定的规则如下：
读取字符 |
移动方向 |
|||
s0 |
1 |
S1 |
||
0 |
右 |
|||
S1 |
+ |
S1 |
||
+ |
右 |
|||
S1 |
擦除 |
S3 |
||
0 |
左 |
|||
S2 |
1 |
S4 |
||
0 |
左 |
|||
S3 |
0 |
S6 |
||
+ |
无作用 |
|||
S5 |
擦除 |
S6 |
||
纸带上的输入是字符串“1+0=”，将进行的过程如下：
开始 |
状态 |
||
【1】+0 |
S0→s1 |
||
1【+】0 |
S1 |
||
1+【0】 |
S1→s4 |
||
1【+】 |
S6 |
这是个过于简单的例子。一般书上所能见到的例子都过于简单，人们不禁会问：图灵机能有什么用？现代计算机所处理的问题越来越复杂，比如宇宙演化的模拟、天气预报、自动驾驶等等，这些处理中也是应用同样的机制，区别在于字符集、状态集、规则集的数量级。
图灵研究的直接背景是希尔伯特第十问题。1900年新世纪开始时，德国数学家希尔伯特在巴黎第二届国际数学家大会上作了《数学问题》的著名讲演，提出了数学理论中23个最困难的问题，后来这个世纪的数学进展与这23个问题的解决密切相关。其中的第10个问题也称为判定性问题。原题目是：给定一个系数均为有理整数，包含任意多个未知数的丢番图方程，能否设计一个过程，通过有限步骤的计算，判定出该方程在有理数上是否可解。问题的一般形式是：是否存在对任何可定义的数学问题可解的判定方法？图灵研究论文的题目是“论数字计算在决断难题中的应用”，他从数的可计算去研究可判定问题，数的可计算是个技术细节更单纯的问题，同时图灵证明了数的可计算问题与逻辑上可判定问题等价。
回到原问题，希尔伯特的判定问题可归为一台通用图灵机不通过实际模拟另一台图灵机，能否预测另一台图灵机的行为，如预测这台图灵机是否会停机。图灵研究的结论是否定的，希尔伯特的判定问题无解。这是与哥德尔不完备定理同样影响深远的结论。图灵机的思想及得到的结论，自图灵以来一直刺激着更多的研究与讨论，其中三个持续的主题是：
宇宙是不是一台图灵机？
在不违背物理规律的情况下，能不能设计出超过通用图灵机的机器？