Algorithm 版 (精华区)

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

定义 一个语言是递归的iff它可以被TM识别.
定义 一个语言是递归可枚举的iff它的特征函数是半可计算的.
定理 一个语言是递归可枚举的iff它是某个TM可计算函数的值域.
注解 实际上通过模拟这里的TM在每个输入下的运行,可以枚举该语言,
这就是"递归可枚举语言"名称的由来.
定理 一个语言是递归可枚举的iff存在TM X,X停机iff输入属于该语言.
定理 递归语言一定是递归可枚举语言.
定理 存在一个递归可枚举语言,不是递归语言.
定理 递归语言的补语言一定是递归的.
定理 如果一个递归可枚举语言的补也是递归可枚举的,那么它就是递
归的.
定理 此问题是不可判定的:已知TM.对每个输入,要求判定是否停机. 
--

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

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