图灵机磁带
图灵机有一条半无限长的带子。磁带中的每个单元格包含磁带字母表中的一个符号。空单元格包含空格字符。
图灵机有一个磁带头，每次可以查看一个细胞。
图灵机控制
除了纸带之外，图灵机还有一个由状态和转换组成的控制器。
每个转换都有三个部分：读、写和移动。读取指定磁带头应该在当前单元中查找什么。如果当前单元格包含列出的字符，则机器可以进行转换。当机器进行转换时，它将读取的符号替换为新符号，然后将磁带头沿指示的方向移动一个空格。
通过简单地读写相同的符号，转换可以使单元格保持不变。
这种类型的转换经常发生，所以作者使用了一种更方便的替代符号来表示保持单元格不变的转换：
标记字符
图灵机程序中广泛使用的策略是用替代符号替换纸带上的符号。这种策略用于标记磁带上的特殊位置。最常见的例子是标记磁带的开始。
这有助于将磁带头倒回磁带的开头。机器只需向左移动经过常规符号，直到遇到一个特殊的标记符号：
试图将磁带头向左移动到磁带的起始位置会导致磁带头停留在原来的位置。因此，状态4将使磁带磁头位于磁带的开头。
第一个例子
对于我们的第一个示例，我们将考虑一种简单的语言，其字符串使用输入字母Σ ={0,1}。我们第一个例子语言是
L1 = {w | w是偶数长度}
这是识别这种语言的机器控制的初稿。
显然，这里状态1是机器在看到偶数个字符后的状态，状态2是机器在看到奇数个字符后的状态。
机器还没有完成，因为我们还没有添加逻辑来处理磁带头跑过输入终点的情况，而且我们也没有办法让机器接受它的输入。
图灵机有最终状态，就像dfa和pda一样。与早期的机器不同，图灵机既接受最终状态，也拒绝最终状态。当图灵机进入最终状态时，它将停止工作。如果它进入的最终状态是接受状态，机器将接受它的原始输入。如果最终状态是拒绝状态，则机器拒绝其输入。
使用一台机器作为另一台机器的子程序
一旦我们发现如何通过图灵机程序解决问题，我们通常会发现我们可以在更大的图灵机程序的上下文中重用该图灵机来完成相同的任务。
这里有一个典型的例子。假设我们想做一个图灵机来识别语言
L2 = {ww | w∈Σ*}
有用的第一步是确认输入字符串的长度是偶数并且长度至少为2。如果我们确定它是奇数，我们可以立即停止并拒绝。这是一个图灵机，它可以扫描它的输入，以确定输入是否是偶数长度，并拒绝任何奇数长度的输入。为了便于在程序的后面阶段倒回开始，我们使用了一种常用的策略，即用标记字符替换输入中的第一个字符。
我们现在可以把这个初始机器用作更大机器的第一阶段。机器不会以接受状态结束，而是继续进入下一阶段。完成第一阶段后，我们知道磁带头位于输入中最右边的字符上方。
在下一阶段，我们在磁带上进行一系列的传递。在每一次传递中，我们替换左边的一个字符和右边的一个字符。左边用cs代替0，用ds代替1。在右边我们把0换成es，把1换成fs。每次从左到右通过后，我们倒回，直到我们遇到a， b， c或d。当我们到达es和fs与cs和ds相遇的点时，我们知道我们已经替换了原始中的赢博体育0和1，然后可以倒回到开始。这是机器的第二阶段。
这里我介绍了一些简明的符号。符号（0|1）→（e|f），L表示“如果看到0，将其替换为e并向左移动”。如果你看到1，就把它换成f，然后向左移动。”
在第二阶段之后，输入的左半部分的赢博体育0都被替换为cs，而15被替换为ds。在右边，赢博体育的0都被替换为es，赢博体育的15都被替换为fs。
最后一个阶段将左边的字符与右边的字符进行匹配。同样，我们将此作为一系列的传递来完成。在每一次循环中，我们都在左侧寻找c或d，并向右移动，直到找到匹配的e或f。每次我们找到匹配对时，我们都将两个匹配的字符替换为x，以表明我们已经完成了这些字符。
跟踪运行
图灵机非常复杂，所以在设置机器的时候很有可能出错。为了增加我们的信心，我们建立的机器是正确的，我们应该在机器上做一些运行。下面是一个完整的运行示例。
在本例中，我们将在输入s = 110110的情况下运行机器。这是机器应该接受的输入。
这是机器的启动配置。我们从磁带上的输入开始，磁带头在输入的第一个符号上，状态1的控件。(这一系列步骤最好以幻灯片的形式呈现。要开始幻灯片放映，请从“幻灯片”菜单中选择“开始幻灯片放映”。要从一张幻灯片移动到下一张，请按右箭头键。要退出幻灯片放映，请按escape键。)
高级描述
如果在上面的例子中构造图灵机的练习教会了你什么，那就是构造这样的机器是一个乏味且容易出错的过程。最后一个例子的一个好消息是，几乎赢博体育的图灵机都可以分解成不同的阶段。如果我们清楚地知道每个阶段必须完成什么，这将使我们的工作更容易。
构建完整机器的另一种方法是确定我们需要的阶段，并用文字详细描述每个阶段的功能。这可以作为构建阶段的路线图。
例如，上面的机器可以这样描述：
输入x：
- 标记磁带的开始，用a代替0，用b代替1。
- 在磁带上进行初始扫描，每次移动两个字符。
- 倒带到磁带的开头。
- 在纸带的前面和后面来回弹跳，用cs代替前半部分的0，用ds代替15。后半段的0替换为es， 1替换为fs。
- 倒回磁带的开头，把首字母a换成c，把首字母b换成d。
- 在磁带上做一系列的动作。在每一次遍历中找到出现在磁带上的第一个c或d，然后向右扫描寻找与该字符匹配的e或f。在匹配这些字符时，用x替换它们来标记它们。
- 一旦没有字符需要匹配，就停止并接受。
在这个最初的描述中，我只写下了当一切顺利时发生的事情。这是我们在语言中输入x时的典型序列。为了完成我们的描述，我们必须预测赢博体育可能出错的地方。处理这些情况的一个好方法是在我们的要点上添加子点，这些子点描述了在各个阶段可能出现的问题。下面是添加了错误案例的更完整的描述：
输入x：
- 标记磁带的开始，用a代替0，用b代替1。
- 如果磁带是空的，停止并接受。
- 在磁带上进行初始扫描，每次移动两个字符。
- 如果遇到奇数个字符，请停止并拒绝。
- 倒带到磁带的开头。
- 在纸带的前面和后面来回弹跳，用cs代替前半部分的0，用ds代替15。后半段的0替换为es， 1替换为fs。
- 倒回磁带的开头，把首字母a换成c，把首字母b换成d。
- 在磁带上做一系列的动作。在每一次遍历中找到出现在磁带上的第一个c或d，然后向右扫描寻找与该字符匹配的e或f。在匹配这些字符时，用x替换它们来标记它们。
- 如果您在给定的传递中没有找到匹配的字符，请停止并拒绝。
- 一旦没有字符需要匹配，就停止并接受。
展望未来，我们很少会制造完整的图灵机。在几乎赢博体育情况下，我们都将满足于用语言进行高级描述，将机器分成几个阶段，并仔细描述每个阶段的功能。如果描述足够清晰和简单，我们就可以在必要时回头为每个阶段构建子机器。
一个有用的技巧
在我们制造的许多机器中，我们需要在磁带上进行多次传递。在这种情况下出现的一个恼人的技术问题是将磁带头倒回磁带的开始。这是很难做到的，因为可能很难判断我们已经到达了磁带的左端。我们可以用某种特殊的方法在纸带上标记第一个第一个符号，但这通常会给机器带来额外的复杂性。
另一种策略是首先运行一个子例程，该子例程将磁带上的每个字符向右移动一个空格，并在磁带的开头放置一个空格。这样做之后，倒回磁带的开始很容易，因为我们只需要向左移动，直到我们看到空间。
这是图灵机的一个片段，它将纸带上的每个符号向右移动一个空格，并在第一个单元格上留下空白。在移动赢博体育内容之后，片段将磁带磁头倒回，使其结束于磁带中的第一个非空白字符。
状态4上的循环演示了如何倒带到磁带的开始。