1图灵机
1.1图灵机的定义
定义1.1 图灵机由如下的元素组成:
- 字母表(alphabet): 一个有限的集合
- 空白符号(blank symbol):
- 外部字母集(external alphabet): 一个
的子集
,且
。输入和输出的字符串是从这里取出来的。这也是为什么叫external。
- TM的状态(internal state of TM): 一个有限集合
,用来控制下一步执行什么。
- 一个初始状态(initial state):
.
- 状态转移函数(transition function):
注:转移函数是一个partial function,也就是说它的定义域是的子集。如果定义域是全集的话,称为total function。
图灵机的硬件组成:
- 无限长的纸带(Tape): 左边有限,输入的开始,右边是无限的。被分成一个一个小格子(cell),里面是
中的元素,每个cell只能存储一个symbol.
- 一个读写头(Head): 可以沿着纸带移动。
- 有限状态自动机(Automaton): 控制图灵机的行为。内部存储了图灵机现在的状态。通过读纸带cell中的symbol,再根据转移函数确定下一步状态,要写的symbol以及Head移动的方向。其中转移函数的映射是有限的。
注:图灵机演示网址 此外,图灵机停止的标准是,某一时刻的状态转移函数未定义,或者Head移动到了纸带的最左端。
图灵机的配置(Configuration of a TM): 是一个三元组
-
是无限长的符号序列,每一个符号都是属于
的。它是纸带上的内容,会有很多的空白符号,到右边是无限长。
-
是Head的位置,是一个非负整数。 当
时,图灵机停止运行。
-
是图灵机的内部状态internal state。
输入输出的方式
输入:
输出:当图灵机停止运行时,从左到右读Tape,直到读到不属于的symbol,则这之前的都是图灵机的输出。
1.2 可计算函数和可判定谓词(Computable functions and decidable predicates)
每一个图灵机都计算了一个partial function:
。其中
是
上的所有字符串。
定义1.2 函数可计算的定义:
一个部分函数是可计算的(computable),如果存在一个图灵机
使得
。我们称
由
计算。
注:并不是所有的函数都是可计算的。因为的函数时不可数的,但是图灵机的数目是可数的。
predicate: 一个total function输出0或1,true or false。可以把它叫做布尔值函数(Boolean function)。这样一个predicates可以由一个的子集确定:
。
的子集也被叫做
上的language。
decidable predicate: 一个布尔值函数 如果是可计算的,则被称为可判定的(decidable)。
很自然的,computable function and decidable predicate 可以扩展到多变量的情况。
现在我们有图灵机,对应多变量函数
,我们可以在exteral alphabet中加入一个分隔符
,即
然后就可以把上述函数化成一个变量的形式:
。对于多变量,我们引入如下定义。
定义1.3 多变量函数可计算的定义:
部分函数是可计算的,如果存在图灵机
,使得
。
对于多变量的predicate来说,我们同样可以定义decidable。一个多变量predicate如果是可计算的,则被称为可判定的(decidable)。
图灵机的复杂度
时间复杂度对应计算的step数,空间复杂度对应访问的cell数。
时间:对任意长度为的输入,最多执行
step,则称图灵机works in time
。
空间:对任意长度为的输入,最多访问
个cell,则称图灵机works in space
。
1.3 图灵论题和通用机
Turing's thesis: "Any algorithm can be realized by a Turing machine."也被称为Church-Turing。它并不是数学定理,而是对算法概念的非正式陈述。没有被证明,但是有经验支撑。
Universal Turing Machine
因为图灵机是有限的对象,在定义1.1中都要求有限,所以它可以编码为一个字符串(长度有限)。现在我们考虑使用字母表的通用图灵机
,
的输入是
,
是由
中symbol编码
形成的编码序列,
。
输出是
。则
计算了如下的函数
这个函数对可计算函数
来说是universal的。
对应于一个
,就有
。
我们用算法描述通用图灵机,所以它的存在性可以由Church-Turing thesis得到。但是通用图灵机的存在性是一个数学定理,可以用显式的构造法来证明。
1.4 复杂性类型
一个函数的可计算性并不能保证它真的可以计算。在实际中,我们还需要考虑算法的有效性(effective)。一个算法的有效性可以从多个角度定义,从而导致了不同的复杂度类别。其中最重要的是多项式(polynomial algorithm)算法。
polynomial growth: 我们称一个函数是多项式增长的,如果
。其中
是常数,
充分大。记为
。
定义1.4 多项式时间内可计算--用图灵机衡量
一个在上的函数
是多项式时间可计算的(computable in polynomial time),如果存在一个图灵机,当输入长度是
时,可以在时间
内计算
。如果
是一个布尔值函数(predicate),我们称它是多项式时间可判定的(decidable in polynomial time)。
Class P:由所有多项式时间可计算的函数构成的集合。
注:1. 此处所讲的既包含了多项式时间可计算函数,也包含了多项式时间可判定的布尔值函数(predicate)。有的复杂性种类只针对predicate而定义。2. 如果在多项式时间内可计算,则
。因为对图灵机来说,输出的长度不会超过输入长度和执行步数的最大值。
Encoding is important
对于判断是否为素数的问题,采用除以
的方式来判断。当使用unary来编码输入整数时(5的表示为11111),这个算法是多项式时间的。因为输入长度为
,需要执行
次除法。当使用binary编码时,输入的长度为
,
,此时算法执行
不是多项式时间的。
定义1.5 多项式空间内可计算
一个在上的函数
是多项式空间可计算的(computable in polynomial space),如果存在一个图灵机,当输入长度是
时,可以在空间
内计算
。如果
是一个布尔值函数(predicate),我们称它是多项式空间可判定的(decidable in polynomial space)。
Class PSPACE: 所有多项式空间内可计算的函数类。
注: 根据前面的注,多项式时间运行必然多项式空间运行,所以有。很多人认为包含关系是严格的,即
,但还没有人给出证明。
网友评论