图灵机（TM)的特点：
1：在带子上既能读又能写
2：读写头既能左移又能右移
3：带子是无限长的（可以无限存储）
4：在进入接受或者拒绝时候便会停机（TM有一个内部状态存储器）
图灵机的形式定义：
图灵机是一个七元组：(
)，其中
是有穷集合。
Q:是状态集，
是Q三个特别的状态，即：一个初始状态，两个停机状态。
要求：接收状态不等于初始状态。
两个字母表：
是输入字母表，一般由确定的语言给出。不能包含空格B.
是带字母表，由于TM的写功能，可以引入更多的字母，所以：
转移函数：
:
即：TM在读入带字母表当前符号后，确定状态是否改变，并确定读写头的左移或右移。（这里讨论的图灵机不包含读写头不动的情况）
图灵机的格局：
格局用来描述某一瞬时图灵机的所有信息状态。
形式：串U状态Q串V(简记：UQV),串u+串v构成了带上字母，q指向当前v的第一个字母。
格局之间的产生：
如果：
，则说：格局1 uabv产生 格局2 u
acv
,则说：格局1 uabv产生 格局2 uac
v
特别地，在左端点时，状态位于最前面，不允许左移了；在右端点时，假设没有符号的为空格，则： ua等价于 ua
B.
(用格局来定义图灵机可接受的语言）
一个例子：
一个图灵机可识别所有由0组成，长度为2的方幂的字符串
即：TM可识别语言A=
解：M2="对于输入的字符串w:
1: 从左往右扫描带子，隔一个消去一个0（相当于对0的长度减半操作）。
2：如果第一步之后，带子上剩余唯一1个0则接受。
3: 如果在第一步之后剩余不止一个0，当0的个数为奇数个，则拒绝。（2k+1不可能是2的幂次）
4：让读写头回到带子最左端（要有标记带头最左端的操作）。
5：转到第一步
"结束
分步画出状态转移图：
合在一起就是：
下面画出对于字符串“0000”的格局：
例子2：让图灵机识别下列语言：
分析：
这里每消去一个a，就让c去掉b个，也就是将b与c一一消去，然后再读写头返回a是，恢复b.
M3="对于输入字符串w:
1:从左往右扫描字符串，确认输入形式为：a_b_c_.如不然拒绝。
2：让读写头回到左端点。（故读第一个a后可标记为#）
（1，2步保证了先出现a,然后读b后不能出现a，读c后不能出现a，b）
3：消去一个a,向右扫描直到b出现，然后读写头在b与c来回移动，成对地消去b和c,直至把所有的b消去。
4：如果还有a没消去，则在读写头移动a前，恢复所有已消去的b,重复3，当所有的a都消去后，检查是否有c，c都被消去了则接受，反之，拒绝。
"
最后区分：图灵可判断和图灵可识别
一个TM,最后只有三种状态，两种停机状态，接受或拒绝；一种循环状态，这里是永不停机的意思。
即：
两者都能接受语言，但对于不能接受的语言，判定一定会拒绝，判定（yes or no）
而识别的话，一般要么停机要么永不停机
图灵可识别=递归可枚举（数学角度）=计算可枚举=半可判定
图灵可判定=递归=可解=可计算=可判定
