Algorithm 版 (精华区)

发信人: ssos (存在与虚无), 信区: Algorithm
标  题: 可计算性简明纲要(8)
发信站: 哈工大紫丁香 (2001年06月14日15:43:08 星期四), 站内信件

第四节 NP和NPC
定义 一个k带不确定型图灵机是一个6元组(Sigma, Tou, S,F,*,M),
其中Sigma是一个有限集合,称为带字符集;Tou是一个有限集合,称为
状态集;S属于Tou,称为开始状态;F是Tou的子集,称为结束状态集;
*属于Sigma,称为空字符;M是
   Sigma^k X Tou -> rou(Sigma^k X Tou X {L,R,O}^k)
的映射.不确定型图灵机简写为NTM.
注解 NTM与TM的差别在于,NTM的每一步都可以有多种选择,走其中
哪种是不确定的.所以,NTM只有理论上的意义.TM运行的每时刻只有
一个格局(在这里为了避免烦琐,不予定义),NTM的每时刻有一个格
局集合.
定义 一个函数是NTM可计算的iff把它的输入放在NTM的前k-1条带
上开始运行NTM,有限步后格局集合中必有停机的格局,并且在此格局
的第k条带上有函数值.
定理 一个函数是NTM可计算的iff它是递归可枚举的.
定义 NTM计算一个语言的特征函数的过程称为识别该语言.

--

   
<<社会契约论>>是一本好书,应当多读几遍
风味的肘子味道不错,我还想再吃它      

※ 来源:·哈工大紫丁香 bbs.hit.edu.cn·[FROM: 202.118.230.220]