摩尔类理论与函数可计算性模型的关系

理论计算机科学电子笔记120（2005）83-95www.elsevier.com/locate/entcs2型可计算性与Moore川村秋俊1计算机科学系日本东京大学大学院情报科学研究科摘要关于函数在实数上的可计算性，有几种模拟的连续时间计算模型，与第二类可计算性的数字离散性质相反。我们研究其中之一，摩尔的实（原始）递归函数，其定义模仿递归函数的经典特征N的封闭性。我们表明，类的类型-2可计算的实函数落在摩尔类之间的保留字：第二类可计算性，实递归函数，模拟计算，积分方程。1介绍本文探讨了标题中的两个理论之间的联系，这两个理论涉及函数从实数到实数的幂律性在模拟计算模型中，连续的量被视为一个实体，计算在连续的时间内进行，这一点越来越受到人们的关注。作为在这样一个模拟世界中的递归性的公式，我们考虑递归函数类及其原始递归函数子类，两者都由Moore [4]引入这些类是由闭包性质定义的，这些性质继承了Kleene1电子邮件地址：akitoshi@is.s.u-tokyo.ac.jp1571-0661 © 2005 Elsevier B. V.在CC BY-NC-ND许可下开放访问。doi：10.1016/j.entcs.2004.06.03684A. Kawamura/Electronic Notes in Theoretical Computer Science 120（2005）83.ΣN.ΣNNN虽然Moore在本文中，我们研究摩尔类型-2可计算性，并通过模拟每个模型来显示来自两个理论的类之间的包含。我们在第2节介绍摩尔我们在第4节中表明，摩尔在下文中，函数可以是部分的，除非明确声明为全函数。我们偶尔会用上标来标注一个函数，以显示它的arity，因此对于一个有m个参数并产生n个值的函数f，我们写fm→n一函数操作的上标，如h=CMm→n[f;g]，表示结果函数h的arity。有关2型糖尿病可计算性我们遵循Weihrauch [7]。2Moore回想一下，自然数上的经典离散递归函数的特征在于函数在某些运算下的闭包性质：并置。 对于n个函数f m→1，.，f m→1，定义1NJ Xm→n[f1，.，f n]（v）=f1（v），.，f n（v）.混合物. 对于函数fm→n和gl→m，定义C Ml→n [f; g]（v）= f g（v）。N上的原始递归 对于N上的函数f m→n和gm +1 +n→n，定义PRm+1 →n[f;g]（v，0）=f（v），P Rm+1 →n[f; g]（v，t +1）= g. v，t，PRm+1 <$1 [f; g]（v，t）<$.最小化N。 对于N上的函数fm+1 <$1，定义M Nm→1[f]（v）=（f（v，t）=0的最小t ∈ N，如果有的话）.N上的递归函数被定义为包含一些基本函数的最小类中的那些函数，并且在上述操作下是封闭的A. Kawamura/Electronic Notes in Theoretical Computer Science 120（2005）8385.Σ.tant = 0 +（1 + tan2τ）dτ，摩尔R上的原始递归对于实函数fm→n和gm+1 +n→n，定义PRm+1 →n[f;g]为积分方程的解h不h（v，t）=f（v）+0G.v，τ，h（v，τ）dτ，其中PR[f;g]完全被定义，并且只有那些（v，t）使得对于所有τ在0和t之间，(i) 积分方程唯一地确定h（v，τ），并且(ii) gv，τ，h（v，τ） 已定义。R上的极小化 对于实函数fm+1 <$1，定义M Nm→1 [f]（v）= μt。 f（v，t）= inf {t ∈ R |f（v，t）= 0}，其中inf选择具有最小绝对值的t。如果两个这样的界限具有相同的绝对值，那么按照惯例选择负的界限。定义2.1原始递归函数是包含0元常数函数00→1，10→1，−10→1的最小类中的函数，并且在JX，CM和PR下是封闭的。递归函数是包含00→1，10→1，−10→1的最小类中的函数，并且在JX，CM，PR和MN下是闭的。PR行动需要一些评论。实数PR与其离散对应物不同，可以从全函数产生部分函数，如等式所示：阿勒特0其解仅定义在开区间（−π/2;π/ 2）上。因此，我们将生成函数的域指定为两个下的最大值。以上条件。条件（i）禁止从例如以下等式h（t）=0 +不零？0.h（τ）dτ为零？（x）=0if x = 01例其他情况其中f（t）=t和f（t）=0（以及另外两个函数）都是解。条件（ii），虽然在摩尔的原始定义[ 4 ]中并不清楚要看到这一点，考虑函数g定义为∫∫86A. Kawamura/Electronic Notes in Theoretical Computer Science 120（2005）83√我+-≤∈›→ΣΣ我我我.2吨如果t为0Σ Σ ΣΣPR2→1id1→1; 13→1和mul2→1 =PR2→1 01→1; id3→1。对于inv1→1，定义11g1→1=PR10→1;CmCmul2→1;JX−11→1，squuare1→1;id2→1，+1.2通过g（t，x）= 1/ |不|对于t ∈ R\{0}，它是原始递归的（和解析的在其领域），这将是明确的。 但函数h定义为h（t）= −2−tift0在t= 0时不可微分，尽管它h（t）= 0 +不g τ，h（τ）0d τ。这就是为什么我们强加（ii），一个比通常的积分概念更严格的条件;根据我们的公式，其中被积函数必须在区间上的任何地方定义，以便定义积分，PR[00→1;g]不是上面的h，而是一个无处定义的函数。 PR的变体是由Campagnolo[1]和Graca[2]进行比较。3例本节给出实递归函数的例子。以下Lemmata3.1、3.2和3.3部分源自Moore[4]。我们从一些原始递归函数开始：引理3.1下列函数是原始递归的：对于每个n N，n元常数0 n→1，1 n→1，1 n→1;对于正整数n和i n，n元投影id n→1到第i个分量;二进制加法加2→1和乘法乘2→1;倒数1→1：x 1/x和自然对数ln 1→1定义为正数;三角函数和指数函数sin 1→1，cos 1→1，exp 1→1和常数e 0→1，π0→1。证据n元常数0n→1由0n→1 =CMn→1 00→1;JXn→0[]建立;对于1n→1和−1n→1类似。投影在n−上归纳定义i通过idi→1=PRi→1[0i−1→1; 1i+1 <$1]且idn+1<$1= P Rn+1 <$1[idn→1; 0n+2<$1]。对于加法和乘法，使用通常的递归定义add2→1 =1 1 +squuare1→1=CMmmul2→1;JXmid1→1，id1→1mm，inv1→1=Cmg1→1;CMadd2→1;JX id1→1，−11→1，∫ΣA. Kawamura/Electronic Notes in Theoretical Computer Science 120（2005）8387.›→.›→≤∈trig1→2=PrJX00→1，10→1;JXid3→1，CMmul2→1;JX−13→1，id3→1，.Σsin1→1 =Cmid2→1;cos1→1=Cmid2→1; cos1→2，32或者用更熟悉的语言来说，square（z）=z2，g（y）=1−y平方0.g（η）d η， inv +=g（x− 1）.对数和指数是类似的，使用适当的积分方程。三角函数定义为：1 2或者等价地，通过方程组. sin（t）=. 0人以上不客气。cos（τ）d τ。cos（t）10−sin（τ）欧拉圆比为π0→1（）= 4 Arctan（1），其中Arctan由适当的积分方程定义。Q没有MN，我们只得到连续函数。接下来，我们通过使用MN来构造具有不连续性的函数：引理3.2以下函数是递归的：零？：x0if x = 01否则，整数？：x0如果x是整数1其他;条件ifthenelse 1+2m→m，如果p = 0，则将（p，a，b）映射到a;2总倒数inv（在引理3.1中扩展了inv+），其中inv（0）= 0，并且对于每个t / = 0，inv（t）=1/t; 3函数将x舍入到（x−1/2; x +1/2]中的唯一整数; 4函数digit将每个（x，b，i）映射到b i的位置，其中b> 1，i ∈ Z，当x以b为底表示时。请注意，digit（x，b，i）对于b1或i /Z是未指定的：对于这样的b或i，它可以被下定义或定义为任何值。我们始终采用这个约定，即当我们声称一个函数是递归的，其值仅在输入空间的某个子集上指定时，我们意味着该函数具有递归扩展，其值在意外参数上我们不关心。证据德费恩零？（x）= µy。 （x2+ y2）（1 − y），整数？（x）=零？ sin（πx），如果thenelse（p，a，b）=.1 -0？（p）·a+零？（p）·b，∫88A. Kawamura/Electronic Notes in Theoretical Computer Science 120（2005）83- -.Σ- 是的. .好吧Σ−−b我2bi+12）t）t tFig. 1. 时钟和时钟的功能。用通常的向量乘法以明显的方式构建，inv（x）= µy。 x（xy −1），round（x）= x µr。整数？（x r），digit（x，b，i）= round. x− 1− b·round. x−1，其中求幂bi由bi= exp（i·ln（b））构建Q我们准备了一些从另一个递归函数创建一个递归函数的一般方法，我们将在第5节中使用这些方法来展示几个复杂的递归函数。引理3.3如果fm→m是递归的，则函数gm+1→m：（v，k）<$→fk（v）=f（f（· ·（f（v））· ·））（k∈N\{0}）.证据 定义Fm+m+1 →m通过克雷奇斯F（b，v，t）= f.如果否则1+2m→m。1− integer？（t）+digit（t，2，−1），b，v，使得domF< $Rm×domf× R且F（b，v，t）=f（b），如果t∈（n;n+ 1/2），其中n∈Z.定义时钟1→1和时钟1→1，clock（t）= digit（t，2，−1），clock（t）= 0 +不客气。02− 4时钟（τ）dτ使用引理3.2中的数字（图1）。让g（v，t）h（v，t）=. v+t2F h（v，τ），v，τh（v，τ）1clock（τ）02. h（v，τ）− g（v，τ）inv. （τ）ΣX1X 为时钟（t1132X1X 为1998年，113222A. Kawamura/Electronic Notes in Theoretical Computer Science 120（2005）8389v∈\{}dτ，使用引理3.2中的inv（图2）。我们有g（v，k）=h（v，k）=fk（v），KN0，根据需要，g在每个时钟时间的前半部分计算下一个值，然后h在后半部分赶上。Q90A. Kawamura/Electronic Notes in Theoretical Computer Science 120（2005）83Σm+2.- 是的Σk→∞.Σ.X12347151吨816f（1）−f（0）f（1）f（2）−x=g（v，t）x=h（v，t）图二. 用实递归函数模拟迭代fk（v）图三.用实递归函数模拟极限limf（kk→∞作为一个应用，如果fm+1 <$1是递归的，那么n−1g：（v，n）<$→f（v，i）（n∈N\{ 0}），i=0时因为g（v，n）= idm+2 <$1Fn（v，0， 0） 其中F（v，t，S）=v，t+ 1，f（v，t）+S.引理3.4如果fm+1 →n是递归的，则函数gm→n：v<$→limf（v，k）（{v}×N阶 domf），其中k贯穿N。证据定义lg：x<$→µy。x（2 y-x）和k：t→ round-lg（1-t）-1/2使用引理3.2的round。则k是递归的，且dom k=（−∞; 1]。因此g（v）=f（v，0）+12k（t）+1f0.v，k（t）+1−f.v，k（t）给出了所需的g（图3）。QXf（v）f2（v）v12T∫A. Kawamura/Electronic Notes in Theoretical Computer Science 120（2005）8391∫ΣΣ.Σ不上界估计精确解x=h（t）较低估计FIG。 四、所以我会在这里等你。 S i n cebi+1−bi0，负的情况是类似的.如果h（t1）是unfined，就没有什么需要证明的了。因此，假设h（t1）被定义，即积分方程h（t）=f（）+gτ，h（τ）dτ0有一个唯一的解决方案定义在所有[0;t1]。则存在n∈ N和有理数β，u，d，b0，b1，.，b n，c0，c1，.，c，n，使得(i)（n−1）u t1≤nu;(ii) b00使得g及其所有导数存在XRici+1Cibi+1f（）个字符b我iu（i+1）ut1不havebi+1h（i+1）u< ci+1ifbi

下载后可阅读完整内容，剩余1页未读，立即下载