Algorithm 版 (精华区)

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

第二节 判定问题
记号 rou(A)表示A的幂集.A*表示A的闭包.
定义 设Sigma是一个有限集合,rou(Sigma)的任何一个子集称为Sigma
上的一个语言,Sigma称为它的字母表.它的补集称为补语言.
定义 设L是Sigma上的一个语言,一个Sigma*->{0,1}的映射f:
   f(S)=1 if S属于L
        0 otherwise
称为L的特征函数.记作chr(L).
定义 一个TM能识别语言L是指它能够计算chr(L).
定义 一个判定问题是一组实例的集合,对其中任意一个实例,要求判定
一个命题能成立.一个TM能判定一个问题是指其任何一个实例都是该
TM可计算的.如果改为判定命题不能成立,则为该问题的补问题.
注解 注意到判定问题和识别语言是等价的.判定补问题相当于识别补
语言.问题和补问题的差别体现在不确定型TM的识别上,对目前的确定
TM,如果能停机,就是完全一样的.

--

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

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