ITOC chapter3 丘奇-图灵问题

 3 The Church-Turing Thesis 丘奇-图灵问题

前两章,NFA只能有限存储,PDA能无限存储,但是只能先进后出(栈),它们很多问题都不能完成计算,所以需要图灵机–

3.1 Turing Machines 图灵机

图灵机:多一个纸带,有读写头~

图灵机与NFA的区别:

  1. 图灵机在纸带上能读也能写
  2. 读写头能左移也能右移
  3. 带子无限长
  4. 进入拒绝或接受状态之后立刻停机
Definition 定义

一台图灵机是一个7元组(Q,Σ,Γ,δ,q0,qaccept,qreject), 其中Q,Σ,Γ都是由穷集合:

  1. Q 是状态集
  2.  Σ是输入字母表,不包括空白符号⊔
  3.  Γ是纸带, 其中⊔∈F并且Σ⊆Γ
  4.  δ: Q×Γ⟶Q×Γ×{L,R} 转移函数δ,
  5.  q0∈Q 是起始状态,
  6.  qaccept∈Q是接受状态
  7.  qreject∈Q是拒绝状态,满足qreject≠qaccept

图灵机在计算时,当前状态、当前纸带内容和读写头的位置会发生变化,这三项构成的整体叫做图灵机的configuration(构造、格局)。

Recognize and Decide 识别与判定

图灵机M接受输入w,如果存在格局序列C1,C2,,,,Cn使得:

  1. C1是M在输入w上的起始格局
  2. 每一个Ci产生Ci+1
  3. Ck是接受格局

那么M接受的字符串的全体称为M的语言L(M)

起始格局,起始状态,接受格局,拒绝格局。接受和拒绝都属于停机状态,因为它们不再产生新的格局。

一台TM运行一个输入时,可能出现三种结果,接受,拒绝,循环(循环指不停机,可能循环可能不循环一直运行,类似无限小数,可以是无限循环小数,也可以是不循环小数。)

如果永不循环,那么这种TM就叫Deciders判定器

recognizers可能会被某些输入弄得进入循环,永远都无法accept或reject,而deciders则不会
那么怎么判断一台机器是不是在死循环呢?

可能下一秒它就停机了,也可能永远都不停,这就是大名鼎鼎的停机问题。

Compared with Finite Automata TM与NFA的不同:
  1. 无限内存,无限制的访问
  2. TM可以从纸带上读取信息
  3. 读写头可以左右移动
  4. 纸带是无限长的
  5. 特殊状态–接受/拒绝状态立刻生效

3.2 Multitape Turing Machines 多带图灵机

转移函数:δ: Q×Γ^k⟶Q×Γ^k×{L,R,S}k. k是纸带的个数。

δ(qi,a1,…,ak)=(qj,b1,…,bk,L,R,…,L)意思是:若机器处于状态qi,读写头1到k所读的符号分别是a1,….,ak,则转移到状态qj,写下符号bi到bk;且按此式所指示那样移动每个读写头。

看上去多带图灵机比单带的能力强,但:
定理:每个多带图灵机都有一个于其等价的单带图灵机。

证明思路:使用单带模拟多带:

Nondeterministic Turing Machines 非确定型图灵机

转移函数:δ: Q×Γ⟶P(Q×Γ×{L,R})

定理:每一台非确定型图灵机都对应着一台确定型图灵机

证明思路:非确定性图灵机会生成一个决策树,不同的分支对应不同的选择。要找到对应的,就是找到一台TM能把决策树跑一遍,每种决策都试一下。但是非确定性图灵机有可能会在某些分支陷入死循环,如果用DFS的方法,那么可能会在某个分支直接陷入死循环,而把其他分支忽略了,另外,我们要的仅仅是能让确定性图灵机在有限步内把非确定性图灵机 accept 的结点跑一遍,所以我们可以用BFS的方法,层次遍历,先跑计算次数少的结点,再跑计算次数多的结点。

Enumerators 枚举器

枚举器,可以理解为一台带有连接打印机的图灵机。

枚举器可以使用该打印机作为输出设备随时打印字符串。
E枚举的语言是它最终打印出来的所有字符串的集合。

定理:一个语言是图灵可识别的,当且仅当有枚举器枚举它。

先证明⟶ 如果有枚举器E枚举语言A,则有TM M识别A:

M:对于输入w:

  1. 运行E,每当E输出一个串时,将其与w比较;
  2. 如果w曾经在E的输出中出现过,则接受。

再证明 M 设s1,s2,s3,…是Σ∗中的所有串,如果TM M识别语言A,那么这样构造枚举器E:

E:忽略输入,对i=1,2,3,4…重复以下步骤:

  1. 对于s1,s2,s3,…si中的每一个,让M以其作为输入运行i步。
  2. 如果有计算接受则打印相应相应的sj。
Equivalence with other models 与其他模型的等价性

任何其他模型,只要拥有图灵机的“本质特性”–无限制访问无限的存储器,那么这些模型在能力上是等价的(需要满足特定条件,如“在一个步骤中仅执行有限的工作量“。)

3.3 The Definition of Algorithm 算法的定义

以前:“通过有限多次的运算就可以决定的过程“

直到丘其-图灵使用λ-calculus的记号系统来定义算法。

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注