内容提要

什么是图灵机？

一个简单的例子

一个简单的程序

机器状态

有限状态机

什么是图灵机？

图灵机是一个虚拟的机器，由数学家阿兰·图灵1936年提出来的，尽管这个机器很简单，但它可以模拟计算机的任何算法，无论这个算法有多复杂。

上面是一个图灵机的简单示意图。假设有一个无穷的纸带，纸带就像一个存储器一样。纸带上面的每个格子是空白的，但是可以读写数据，在这个例子里，机器只能写0，1，或者什么也不写。这个机器就是包含3个信号的图灵机。

这个机器有一个探头，这个头可以移动到每一个空格上，用这个头，机器可以有3个基本操作。

1、读空格的数据

2、编辑数据，可以是写一个新的数据，可以是擦除数据

3、移动纸带向左或者向右，这样机器可以读或者编辑旁边的格子

一个简单的例子

首先，黑色加粗部分代表探头所指的部分，我们写一个1：

然后，我们把纸带向左移动一格：

写1到新的格子里面

然后把带子向左移动一格，并写一个0

一个简单的程序