Algorithm 版 (精华区)

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

定义 对一个k+1带TM X,k带TM Y, 以及X的输入P,如果对Y的任意
输入Q,有:
1)X在输入PQ下停机iffY在输入Q下停机,
2)并且此时X和Y的输出完全相同,
那么称X用程序P模拟了Y.
定义 如果一个k+1带TM能够模拟所有k带TM,那么就称它为通用TM.
定理 对任意k>=2,存在k带通用TM.
定理 任意k带TM可计算的函数都是1带TM可计算的,并且如果k带TM
用了N步,1带TM只要O(N^2)步.
定理 存在一个函数,2带TM用N步计算时,1带TM需要OMIGA(N^2)步.
定理 任意k带TM可计算的函数都是k+1带TM可计算的,并且当k带TM
用N步时,k+1带用O(N)步.

--

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

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