图灵机 写在带子上的符号为一个有穷字母表: 可以认为这个有穷字母表仅有S、S两个字 其中S可以看作是“0”,S1可以看作是 由“0”和“1”组成的字母表可以表示任何 个数。 第16页
第16页 图灵机 • 写在带子上的符号为一个有穷字母表： {S0，S1，S2，…，Sp }。 – 可以认为这个有穷字母表仅有S0、S1两个字 符， – 其中S0可以看作是“0”，S1可以看作是 “1”， – 由 “0”和“1”组成的字母表可以表示任何 一个数
由于“0”和“1”只有形式的意义,因此, 也可以将S0改称为“白”,S改称为 “黑”,甚至,还可以改称为“桌子”和 老虎”,这样改称的目的在于割断与直 觉的联系,并加深对布尔域中的值{真, 假},以及二进制机器本质的理解。机器 的控制状态表为:{(q1,q2,…,qn 将一个图灵机的初始状态设为q1,在每一个具 体的图灵机中还要确定一个结更状态4°第页
第17页 • 由于“0”和“1”只有形式的意义，因此， 也可以将S0改称为“白”，S1改称为 “黑”，甚至，还可以改称为“桌子”和 “老虎”，这样改称的目的在于割断与直 觉的联系，并加深对布尔域中的值{真， 假}，以及二进制机器本质的理解。机器 的控制状态表为：{q1，q2，…，qm }。 – 将一个图灵机的初始状态设为q1，在每一个具 体的图灵机中还要确定一个结束状态qw
多一个给定机器的“程序” 机器内的五元组(qSSR(或L或N)q) 形式的指令集,五元组定义了机器在 个特定状态下读入一个特定字符时所采 取的动作。5个元素的含义如下: q表示机器目前所处的状态; S表示机器从方格中读入的符号; S表示机器用来代替S写入方格中的符号; R、L、N分别表示向右移一格、向左移 格、不移动; q表示下一步机器的状态。 第18页
第18页 一个给定机器的“程序” • 机器内的五元组（qi Sj SkR（或L或N）ql） 形式的指令集，五元组定义了机器在一 个特定状态下读入一个特定字符时所采 取的动作。5个元素的含义如下： – qi表示机器目前所处的状态； – Sj表示机器从方格中读入的符号； – Sk表示机器用来代替Sj写入方格中的符号； – R、L、N分别表示向右移一格、向左移一 格、不移动； – ql表示下一步机器的状态