Algorithm 版 (精华区)

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

定理 此问题是不可判定的:任给TM的表示,要求判定对空输入是否停
机.
定义 设P是语言的一个性质,如果P对所有语言都恒成立或恒不成立,
则称为平凡的;否则称为不平凡的.
Rice定理 设P是一个不平凡的性质.L(X)表示TM X识别的语言.以下问
题是不可判定的:任给TM X的表示,要求判定P对L(X)成立.

--

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

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