在一个图灵机的动作中图灵机根据带头读写头所扫描的符号和有限控制器的状态可能作在一个图灵机的动作中图灵机根据带头读写头所扫描的符号和有限控制器的状态可能作?改变状态?在被扫描的带单元上重新写一个符号以代替图灵机的工作机制4schoolofcomputerscienceamp
• TM的基本定义 • TM的格局 • TM接受的语言 • TM的构造技术 • TM的变形;
• 改变状态 • 在被扫描的带单元上重新写一个符号,以代替原来写在该单元上的符号. • 将带头向左或者右移一个单元。 * 图灵机和双向有限自动机的区别:图灵机能改变它带上的符号。
3
第3页/共31页
图灵机的形式化描述
形式定义 一个图灵机 TM (Turing machine) 是一个七元组
M = (Q, T, , , q0 , B , F ).
├M X0Yq31Z2 ├*M q3X0Y1Z2 ├M Xq00Y1Z2 ├*M XXYYZq22
├M XXYYq3ZZ├*M Xq3XYYZZ├M XXq0YYZZ├*M XXYYq4ZZ
11
├M XXYYZq5Z ├M XXYYZZq5B ├M XXYYZZBq6B
第11页/共31页
Y/Y
Z/Z
Z/Z
转移图与转移表
0/0
1/1
1/1
Y/Y
Start
q0 0 / X
q1 1 / Y
q2 2 / Z
q3
0/0
Y/Y q4 Z / Z
X/X
q5 B / B
q6
Y/Y
Z/Z
State 0
1
Symbol
2
X
Y
Z
B
q0 (q1 ,X, R) q1 (q1 ,0, R) q2 q3 (q3 ,0, L) q4