9、n∈∈∈DN｝｝｝存在求n被被被m除所得余数的标准方法。。。若没有一个余数是0，，，则，则则则n是质数。。。若有一个或几个余数是0，，，则，则则则n不是质数。。。｛｛｛f(n)的值是什么？？？
10、n∈∈∈DN｝，这里f是由f(n)=2n(n∈∈∈DN)))所定义的函数)所定义的函数f(n)=2n期望用数学的方式把算法概念精确化，并且用数学的方式刻画算法可计算的函数类。早期研究者提出的不同形式的描述，大致可分类为描述例子抽
11、象的（（（（（（精确定义的））））））计算机图灵机算法概念的特征计算过程的形式结构图厄系统产生函数类的形式结构递归函数类算法可计算的函数类的描述图灵机：处理理想纸带的抽象机器。图厄系统：纯粹的形式系统。递归函数类：基本函数和规则。Church论题：算法可计算的部分函数类等同于递归部分函数类。可计算的算法导致递归部分函数类。递归部分函数是算法可计算的。算法可计算最小数算子部分函数Church论题递归Church论题算法可计算的部分函数类等同于递归部分函数类。。。注释接受Church论题相
12、当于把直观的算法概念对应于已给出的数学描述具体化。没有任何论据表明这样处理是不合理的。作用可以用数学技巧证明给定的函数或集合是（或不是）递归的，从而证明对于一个特殊的问题类存在（或不存在）一个算法这一事实。反之，当已经找到一个特殊的算法时，Church论题常常用以推出对应的集合或函数是递归的。基本函数规则1.零函数z(n)=0I.复合：：：f(n,…,n)=g(h(n,…,n),…,h(n,…,n))1k11kj1k2.后继函数s(n)=n+1II.递归式：：：f(n1,…,nk,0)=g(n1,…
13、,nk)3.射影函数Pk(n,…,n)=nf(n1,…,nk,n+1)=h(n1,…,nk,n,f(n1,…,nk,n))i1kiIII.最小数算子：：：f(n,…,n)=µµµn[g(n,…,n,n)=0]1k1k例子f(m,0)=P1(m)11加函数f(m,n+1)=s(P3(m,n,f(m,n)))131f2(m,0)=0乘函数f(m,n+1)=P3(m,n,f(m,f(m,n))2312设f和g是D上用算法可计算函数，则f·g是由算法可计算的。N用计算g的算法计算g(n)，然后用计算f的
14、算法计算f(g(n))。设f:D→D是由函数g使用递归式如下定义的：NNf(0)=kf(n+1)=g(n,f(n)).假设g是算法可计算的，对于每一m∈∈∈D，计算f(m).N若m=0，则f(m)=k。若m>0，用计算g的算法计算f(1)=g(0,f(0))，然后再用计算g的算法计算f(2)=g(1,f(1))等等，直至得到f(m)的值为止。计算阶乘函数f(n)=n!(n∈∈∈D)。例如计算10!。N依次计算1!,2!,3!,…,9!,10!。已知N中为真的N的wf.的哥德尔数集不是递归的
15、，于是从Church论题推出，对于下述问题类中的问题，我们找不到算法，｛A在N中为真吗？
16、A是N的wf.｝。设A是由所有是两数平方之和的数所组成的D的子集。A是递归的。N若直接根据下述定理来证明这个函数是递归的颇不容易，回答问题类｛是否n∈A？
17、n∈DN｝，可以表述如下：给定数n，取每一对小于n的数p,q，计算，若某个数对p,q有，则回答是，如果不存在数对p.q使，则回答非。于是由Church论题，A是递归集。设S是N的扩张，且S的非逻辑公理的哥
