Algorithm 版 (精华区)

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

定义 一个随机存取机(RAM)是拥有一个无限长指令阵列和一个可以
任意读写的无限存储器的机器,其中指令可以是如下的任何一种:
   1)X[i]=0 2)X[i]=X[i]+1 3)X[i]=X[i]-1
   4)X[i]=X[i]+X[j] 5)X[i]=X[i]-X[j]
   6)X[X[i]]=X[j] 7)X[i]=X[X[j]]
这里i,j都是整数,作为内存单元的地址;X[i]表示第i个单元的内容.
定理 一个函数是RAM可计算的iff它是TM可计算的.
定义 一般递归函数是可以如下定义的函数f:
   f(u,x0)=A(u,x0)
   f(u,x)=B(u,x,f(u,g(u,x))), if x<>x0
其中A,B都是已知函数;g满足
   g(u,...g(u,g(u,x)))=x0
(迭代有限次)
定理 一个函数是TM可计算的iff它是一般递归函数.
Church-Turing论题 一个函数是可以计算的iff它是TM可计算的.
注解 注意这里"可以计算的"没有定义,所以无法证明.

--

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

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