之前我曾经介绍了一个计算机模型,接下去依次给出一定的证明

cjaizss

机器如下:
R0,..Rn,...(有任意多个存储器)
每个存储器可以存储任意大的自然数(0,1,2,3...)
支持以下4条指令:
A n (对Rn加1)
S n (对Rn减1,但如果Rn为0,则执行后Rn依然为0)
E n,C (跳转指令,如果Rn不为0,则执行第C条指令,否则执行下一条指令)
S  (停机指令)

这是1963年由研究证明论/模型论等数理逻辑分支的数学家Helmut Schwichtenberg给出的计算机模型,名字叫unlimited register machine(URM)
机器虽然很简单,但是不要小看它.
我要指示的就是这个简单的机器也是图灵等价的,也就是所有的一般递归函数都是可计算的.

[ 本帖最后由 cjaizss 于 2009-6-10 09:15 编辑 ]

cjaizss

原帖由 cjaizss 于 2009-6-10 01:53 发表
机器如下:
R0,..Rn,...(有任意多个存储器)
每个存储器可以存储任意大的自然数(0,1,2,3...)
支持以下4条指令:
A n (对Rn加1)
S n (对Rn减1,但如果Rn为0,则执行后Rn依然为0)
E n,C (跳转指令,如果Rn不为0,则 ...

另外,睡觉之前,我想说一下,这里的任意是无界的意思,是潜无穷,也就是你想用多少个都可以,想存储多大都可以，但无论如何，对于一个具体的运算，所使用存储的数量和存储的值都会有一个上限，因为对于一个计算理论意义上的算法来说，是不存在使用无穷多的存储，也不可能会有无穷大的数。其实，你把其看为实无穷对我们的认识也没有问题。

goter

什么意思啊？什么先进思想啊？

nicolas.shen

隐隐约约感觉是这样的，比如对我来说吧，超过r10以后，就得用额外的办法判断当前用的寄存器，很麻烦，但是不知道理论上是咋证明的，期待ing...

cjaizss

恩,一直没有什么时间来写.现在就开始写一点东西,相关的内容我不会一天讲完.
首先介绍几个概念:
自然数集:{0,1,2....};
数论函数:一个定义域和值域都为自然数集的子集的函数
通过已知函数构造新函数的手段有两种:
一种叫叠置子:
对于已知函数f1....fn,新构造出来的函数g.g在任何一处的函数值只依赖于f1....fn有界多处的函数值.
即对于任意a,g(a)只倚赖于f1(x(1,1)),......fn(x(n,m))
而右边的数量有一个上限.
例如,对于f1,f2,我们构造g=f1f2
则对于任意g(a)
我们只需要考察
b=f2(a)
f1(b)
两处值即可知道g(a)

另一种方法叫算子:
对于已知函数f1....fn,新构造出来的函数g.g在任何一处的函数值依赖于f1....fn无界多处的函数值.
即对于任意a,g(a)倚赖于f1(x(1,1)),......fn(x(n,m))
而右边的数量没有一个上限,甚至是无穷多
例如,假设对于已知f
我们构造函数
g(n) = 0 (n=0)
g(n) = g(n-1)+f(n) (n>0)
对于任意a>1,g(a)倚赖于
f(1)....f(a)
是无界多的

[ 本帖最后由 cjaizss 于 2009-7-18 22:57 编辑 ]