理论计算机科学电子笔记167（2007）387-423www.elsevier.com/locate/entcs实计算曼努埃尔湖Campagnolo1D. M./ I.S.A.里斯本科技大学和SQIG/IT葡萄牙Kerry Ojakian2Department of MathematicsSQIG - IT and IST，Portugal葡萄牙里斯本摘要这项工作背后的基本动机是将各种计算复杂性类联系在一起我们提供了调查这些问题的一般工具，使用我们称之为近似方法的技术。本文给出了这种方法的一般发展，并应用它得到了两个定理。首先将线性递归的离散运算（基本上等价于有界和与有界积的组合）与线性微分方程联系起来，从而为Campagnolo，Moore和Costa [3]的结果提供了另一种证明其次，我们推广了这一结果，证明了类似于Bournez和Hainry [1]的结果，为在初等时间内可计算的实函数提供了一个函数代数他们的证明涉及使用函数代数模拟图灵机的操作我们避免这种模拟，使用一种技术，我们称之为虽然我们并不认为我们的结果一定是一种改进（也许只是不同），但我们确实想指出，我们的两种技术似乎很容易适用于这类其他问题。关键词：可计算分析，实递归函数，初等可计算。1 电子邮件地址：mlc@math.isa.utl.pt2电子邮件：ojakian@math.ist.utl.pt1571-0661 © 2007 Elsevier B. V.在CC BY-NC-ND许可下开放访问。doi：10.1016/j.entcs.2006.09.013388M.L. 坎帕尼奥洛湾Ojakian/Electronic Notes in Theoretical Computer Science 167（2007）3871引言我们将研究函数类的计算复杂性，展示不同计算模型之间的联系。经典的情况是，当函数类的定义域和范围是自然数N时，使用类似图灵机的东西来指定哪些函数在类中最近的工作已经将计算复杂性扩展到实数R上的函数类。在经典的情况下，有一个商定的概念，计算和计算复杂性与不同的模型产生相同的功能集。这不是对实数的类似工作我们将集中讨论两种模型实数上的计算，“实数递归函数”和“可计算分析”。前者是由摩尔[6]和后者与Grzegorczyk [4]。在可计算分析中，图灵机被用来描述实数上的各种函数类，其思想是，如果一个实数函数可以从函数的近似值近似到适当的精度水平，则该函数可以由图灵机计算。在实递归函数的情况下，函数类是使用函数代数定义的，其中递归的离散运算被找到离散方程的解的运算所取代我们的目标是研究这三种不同类型的函数类之间的联系，经典的自然类，可计算分析中产生的函数类，以及实递归函数中产生的函数类已经有许多结果将这三种不同的计算模型联系在一起。Campagnolo、Moore和Costa [3]描述了一类实函数（他们称之为L），它们使用线性微分方程代替离散递归;他们表明L的在此基础上，Bournez和Hainry [1]证明了由某种极限运算扩张的L是R上的C2初等可计算函数类.在第4节中，我们给出了[3]结果的另一种证明在第5节中，我们证明了[1]结果的一个变形，特别地，我们通过微分极限运算推广了L，并证明了这正是R上的初等可计算函数。我们为这些问题带来的新奇之处是两种新技术，我们称之为“近似方法”和“提升”。 第一技术在整个文件中使用。 这种技术的基本思想是定义一种可以在两个类函数F和H。粗略地说，我们会说H近似F，如果对于任何所需的精度，F的任何函数都可以用H的函数近似到该精度;这将粗略地写为F≤M.L. 坎帕尼奥洛湾Ojakian/Electronic Notes in Theoretical Computer Science 167（2007）387389H，并且在适当的条件下实际上将是传递关系。我们对这两个定理的方法是首先证明两类函数彼此近似，然后从充分接近的近似中导出所需的等式。证明中的逼近包含是通过构造函数代数的归纳法来进行的由于近似关系的传递性质，为了证明一个类近似于另一个类，我们可以将证明分解为一系列自然的任务。第二种技术，这个想法是从N上的一个已知复杂度结果开始，例如，TuRingg Machines定义的简单功能实际上函数代数FA [+，. ，U，0，1; comp，， ]，然后抬起这个R上的结果。 提升可以看作是一个三步过程。 首先我们举起 N上的结果与有理数Q上的类似结果，其中模型将有理数视为自然数对。第二步（最复杂的一步）是将其提升到Q上的结果，其中有理数由Oracle近似给出（即严格限制在Q上的可计算分析模型）。第三步是通过应用限制将其提升到R。在[1]的工作中，证明涉及到对R上的基本可计算函数类进行新的图灵机模拟;我们设法避免使用新的图灵机模拟，通过重用经典结果（当然涉及图灵机模拟）并将其提升到R。我们认为这些技术的优点是双重的。首先，它们提供了一种不同的方法来解决其中的一些问题，这似乎有助于思考这些问题，特别是在处理函数代数时。其次，这些技术似乎比一些早期的方法更容易推广和更广泛的应用我们声称这是基于其他正在进行的工作，并根据发展的特点。一些引理是一般的，而不是特定于初等可计算函数。此外，对于初等可计算函数所陈述的一些引理，似乎可以用更一般的方式陈述这种方法的更广泛的愿景是收集具有广泛应用的通用工具我们提出了这样一个发展的开端2近似为了正式地发展近似的定义，我们需要能够以精确的方式讨论函数及其参数。 如果函数f（x1，...，xk）精确定义在Xk上，取值于X，我们称之为390M.L. 坎帕尼奥洛湾Ojakian/Electronic Notes in Theoretical Computer Science 167（2007）387一个X−函数，或者等价地，它有论域X;我们不考虑向量值函数。我们总是假设宇宙是R的一个子集，事实上，我们在本文中考虑的唯一特殊情况将是N，Q，R. 为了准确地引用函数参数，我们使用“变量”的概念定义2.1（变量）• 设集合V ={vi|i∈N}称为变量。如果我们提到一个• 假设X∈R是某个集合。对于一组变量ν<$V，一个函数，v到X称为X中的赋值。• 如果我们写μ;ν，我们意味着变量μ和ν的集合是不相交的（而写μ，ν在这一点上是中性的）。• Sup pposev={vi1， .. . ，vik}，wherei1<.. . 0且a和b是弹性素的。• 我们定义一个解释λ：Q→N。对于任何以最低项表示的有理（−1）ka/b，令λ（（−1）ka/b）= 2对（a，b）+k（其中=码（a，b，k））。• ρ1和ρ2是从N到N的唯一函数，使得对于任何以最低项表示的有理数（−1）ka/b，ρ1（λ（（−1）ka/b））= a，且ρ2（λ（（−1）ka/b））= b。例2.11考虑函数mut（x，y）=xy，在Q上。 假设我们想要一个N上的函数multn（n，m），使得它解释multn（viaλ），即mult ≤λmult，按照我们的惯例，这意味着mult≤{0}，[λ]mult。给定2有理数以最低项表示为x=（−1）k（p/q），y=（−1）c（a/b），它们的乘积是通过将分数的顶部相乘，除以底部的乘积，并考虑符号，得到（−1）k+cpa/qb，其中，预分配可能不长，r是最少的项。为了解释这一点，我们进行同样的过程，但对编码有理数的自然数n和m。 因此，顶部应该是ρ1（n）ρ1（m），底部应该是ρ2（n）ρ2（m），符号应该是s（n，m）=delta（n）delta（m）parity（parity（n）+parity（m）），其中如果x= 0，则delta（x）= 0，否则为1为了创建正确的代码，我们需要将分数的最低项，这只是意味着除以顶部和底部的最大公约数。定义函数代码是为了使这种编码更加方便。所以最后，我们得到multi（n，m）=code（ρ1（n）ρ1（m），ρ2（n）ρ2（m），s（n，m））。我们现在可以检查解释是否正确，在这种情况下相当于显示：（*）λ（mult（x，y））= mult<$（λ（x），λ（y）），其中x，y∈ Q.如上所述考虑x和y，然后我们有ρ1（λ（x））=p，ρ1（λ（y））=a，ρ2（λ（x））=q，ρ2（λ（y））=b，奇偶性（x）=k，奇偶性（y）=C.（*）的左边是λ（（−1）k+cpa/qb），右边是code（pa，qb，delta（λ（x））delta（λ（y））parity（k+c））.他们是平等的，nitions。我们现在来讨论一些定义，为了本文的目的，我们可以避免这些定义。然而，它们对于展示这些技术如何变得更通用是必不可少的。我们将定义“边界类”和“错误类”的概念直觉上，一类函数是394M.L. 坎帕尼奥洛湾Ojakian/Electronic Notes in Theoretical Computer Science 167（2007）387边界类，如果它可以用来衡量一些其他类的函数的增长率。一个函数类是一个错误类，如果它可以用来衡量一个函数类逼近另一个函数类时的错误。定义2.12一个函数类B是一个边界类，如果它具有以下性质：(i) 宇宙是R。(ii) 存在一个f ∈ B使得f ≥ 1。(iii) f∈ B意味着f的值总是> 0。(iv) 对于f（x; t）∈ B，f（x; t）= f（x; −t），对任意变量t。(v) f∈ B意味着f是递增的。此外，对于f（μ; t），其中t是f的任意变量，f在强意义下收敛于无穷大，即对于任意正的N ∈ R，存在正的M ∈ R使得对于任意μ → x ∈ R，我们有f（μ→x; M）>N。(vi) 如果β（ν）在B中，γ是与ν不相交的变量，则存在β（ν;γ）在B中，使得β（ν）≤β∈（ν; γ）。(vii) 若f，g∈B，则存在h1，h2，h3∈ B使得f+g≤h1，f∈g≤h2且f ∈ g ≤ h3.定义2.13一个函数类E是一个错误类，如果它具有以下性质：(i) 宇宙是R。(ii) f∈ E意味着f的值≥ 0。(iii) 对于f（x; t）∈ E，f（x; t）= f（x; −t）.(iv) f∈ E意味着f是递减的。此外，对于f（μ; t），f在强意义下收敛于零，即对任意正的m ∈R，存在正的M ∈ R使得对任意μ → x∈ R，f（μ → x; M）≤ m。(v) 如果β（ν）在E中，且γ是与ν不相交的变量，则存在β（ν;γ）在E中，使得β（ν）≥β∈（ν; γ）。(vi) 若f ∈ E，则存在f ∈ E使得f ∈≤（1/2）f.我们总是使用E来表示一般的错误类，因此我们并不总是提到这一点。我们通过取倒数来联系这些类。定义2.14对于一组函数F，1/F={1/f|f∈ F}。命题2.15如果B是一个边界类，那么1/B是一个错误类。证据 我们可以检查1/B是否满足6个定义性质。例如，考虑最后一个属性。假设我们有1/f∈1/B，我们需要f∈B使得（1/f∈）≤（1/ 2）（1/f）。由于f∈ B，且B是一个边界类，则M.L. 坎帕尼奥洛湾Ojakian/Electronic Notes in Theoretical Computer Science 167（2007）387395++正/负++是f<$∈ B使得f<$≥f+f=2f，它具有所需的性质.Q下面是一些边界类的例子;TW是我们在本文中唯一使用的定义2.16（1）A（|X1|+1）b.. . （一）|Xn|+1）b|n∈N，a， b∈Q，a，b>0}.（ii）LetT Wbe{2···2p|p∈P}，这是由两个2的幂的函数，在顶部有一个多项式。命题2.17 P和TW是边界类。因此，1/P和1/TW是错误类。我们还将对另一个使用迭代日志定义的错误类感兴趣;我们实际上对log2进行了修改，因此函数在所有R上都有定义。定义2.18⎧如果y≥2，则为n = log2y;• 设lg（y）=101、其他• 让我做{a·lg.. . 1g（p）|p∈P， a∈Q， a>0}命题2.19 1/IL是一个错误类。请注意，IL不是一个边界类（尽管如果我们在边界类的定义中从最后一行删除条件fg≤h2，现在我们通过证明它在正确的条件下是一个偏序来证明近似符号引理2.20（传递性）假设A、B和C分别是论域A、B和C上的函数类，ω：B→C是一个解释。(i) 如果A≤EE正/负CtenA≤E，idA<$B <$CC(ii) 如果A≤EB≤EC，则A≤E，(iii) 若Domain（ω）<$A且A ≤E B ≤[ω]C则A ≤E，ωC证据(i) 设f（μ）∈ A，α（μ; ν）∈ E，且我们需要h（μ; ν）∈ C使得|f（x）−h（x; y）|≤ α（x; y），其中x; y∈ A <$B<$C。 由于E是一个误差类，所以存在α∈（μ;ν）∈E，使得α∈（μ;ν）≤（1/2）α（μ;ν）。设g（μ;ν）∈Bsuchthat|对于所有x ; y ∈ A <$B，≤ α <$（x ; y）。| ≤ α∗ (x; y) for all x; y ∈ A∩ B.设h（μ;ν）∈C使得|≤α <$（x ; y），其中x ; y ∈ B <$C。| ≤ α∗ (x; y) for x; y ∈ B ∩ C.因此|f（x）−h（x; y）|≤B≤396M.L. 坎帕尼奥洛湾Ojakian/Electronic Notes in Theoretical Computer Science 167（2007）387+正/负正/负正/负正/负根据需要，α（x;y）+α（x;y）≤α（x;y请注意，我们需要(ii) 这个证明与前一个非常相似。(iii) 设f（μ）∈ A，α（μ;ν）∈ E，且h（μ;ν）∈ C，使得|对于所有的x ; y ∈ Domain（ω），≤ α（x，y）。| ≤ α (x, y) for allx; y ∈ Domain (ω).设g（μ; ν）∈ B使得|f（x）−g（x; y）|对于所有x;y∈A<$B，≤ α（x ; y）。设h（μ; ν）∈ C使得|g（x; y）−ω−1<$h（ω（x）; ω（y））|全部≤ 0x;y∈Domain（ω）.因此|f（x）−ω−1<$h（ω（x）; ω（y））|对于所有x; y∈A<$B<$Domain（ω），≤ α（x ;y）是足够的，因为Domain（ω）<$A，B.注意，条件Domain（ω）<$A也确保A ≤E，ωC就说得通了Q一个有用的简写是下面的定义2.21我们写一个字母B表示A≤EB和E正/负一个保持。注意，随着近似的定义（及其特定的量化器）重要的是要按照正确的顺序阅读定义。 我们使用B ≥EA作为A ≤E B的另一种写法。函数类之间的另一种重要关系是一类支配另一类。定义2.22假设A和B是同一个单位域X上的函数类。我们写A ≤ B，如果对于每个函数f（x）∈ A，有一个函数h（x）∈ B，使得|f（x）|对于所有的x ∈ X，≤h（x）。再次注意，由于定义中的量化器，我们阅读表达式的顺序很重要;通过写作B≥ A，我们意味着A ≤ B。3函数代数与运算我们将使用函数代数来定义大多数函数类它们通过给出一些基本函数并在函数的操作下关闭类来定义定义3.1（运算）函数运算（或简称运算）是一个函数，它接受一些带变量的函数（可能还有一些变量）作为输入，并输出一个带变量的函数。一个运算有论域F（一组函数），如果它是定义在来自F的函数上，并返回F中的一个函数（对于我们考虑的任何F，总是有一个相关联的X<$R，使得F中的所有函数都有论域X）。如果B≤M.L. 坎帕尼奥洛湾Ojakian/Electronic Notes in Theoretical Computer Science 167（2007）387397F是所有具有论域X的函数<$R，我们称运算具有论域X.例如，克乌尔德 定义 手术 呼叫嗯，”（f（x;y）;y;z），其中N是唯一的，其中有一个函数和两个变量并返回g（x;z）=zy=0时f（x; y）.定义3.2（函数代数）假设B是一组函数（称为基本函数），O是一组运算。则称FA [B; O]为函数代数，它表示包含B且在O中的运算下闭的函数的最小集合。为了便于阅读，我们经常将B或O的元素简单地列成一个由逗号分隔的列表。我们将使用的函数代数的一个例子是元素可计算通过有界和和有界乘积定义的函数。我们行动吧-如果N是一个非线性函数f（x′;y），则返回sg（x′，z）=zy=0时 f（x′;y）.设Comp是一个操作，其中使用了一些函数，组成他们。我们定义这个类的基本函数定义3.3设基函数N是下列函数，其论域为N：+，。，P，0，1，其中P是N上的所有投影函数的集合，并且。是通常的截零减法，定义为.X. y= x-y如果x≥y.0否则因此FA[基本N;comp， Σ是基本的可计算函数。定义3.4设函数代数FA[basicN;comp，由FAN。Σ， ]be fixed vi-回想一下，按照惯例，所有函数集（包括通过函数代数定义的函数集）都是隐式的带变量函数，在sub下闭合（注意sub实际上是一个运算，因此惯例意味着它作为运算之一包含在所有函数代数中）。注意，在函数代数中，可以有两种不同的方法来构造同一个函数。这突出了函数代数的语法方面，这将成为第5节的一个问题。定义3.5给定一个函数代数F，且f∈F，f的构造树是指描述函数代数中f的构造的树。这个树的叶子由代数中的各种基本函数标记，内部节点由代数中的运算标记。因此，我们可以将树看作指定如何构建函数，从叶子开始，沿着树向上移动然后，每个节点可以被视为指定398M.L. 坎帕尼奥洛湾Ojakian/Electronic Notes in Theoretical Computer Science 167（2007）387一个句法术语，以及相应的功能。对于树要关联到f，意味着f是与树的根相关联的函数。现在我们发展一种有用的概念，即一种运算近似于另一种运算。粗略的想法是，一个操作近似于另一个操作，如果通过从相互近似的函数开始，应用操作保持这种近似。定义3.6假设运算A OPB 是相同性质k >0，分别对应于宇宙A和B，我们称之为opAE，[ω]正/负OPB如果由于任何f1，.，fk∈ A和任何ε ∈ E，其变量包含所有opA（f1，.，fk），存在ε1，.，εk∈ E，使得对任意f∈，. ，f∈ B，1K若fi≤εi，[ω]f∈（i= 1.. . k）nop（f1， .. . ，fk）≤ε，[ω]op（fk， .. . ，f）。+/−i A+/−B1k近似的符号约定（注释2.8）继续适用于运算近似;回想一下，按照约定，我们可以在上面的定义中通篇选择考虑到上述定义，可以想象我们最终考虑f≤ωf，其中domain（ω）/domain（f）或domain（f）/range（ω）。这会给定义带来一些问题，所以我们在处理时只需按照惯例排除这一点。近似运算。为了使定义更具体，考虑一个“解释”的组成（它将在后面使用）。 假设F是一个函数类，我们用compF表示从F合成函数的运算;如果代替F，我们有一个集合A<$R，我们表示F包括所有论域为A的函数。命题3.7假设X，Y<$R和ω：X→Y是一个解释。则compX≤[ω]compY。证据 设f（μ; t）和g（γ）是论域X上的函数，f ω（μ; t）和gω（γ）是论域Y上的函数，使得f ≤ωf ω，g ≤ωgω. 我们需要证明f（μ; g（γ））≤ωf ω（μ;gω（γ））。 固定任何赋值μ → a; γ → b ∈ X，下面的计算证明了 这一点：ω−1<$fω（μ→ω（a）;gω（γ→ω（b）=ω−1<$fω（μ→ω（a）;ω<$g（γ→b））=ω−1<$ω<$f（μ→a;g（γ→b））=f（μ→a;g（γ→b））第一个等式遵循g≤ωgω，第二个等式遵循f≤ωfω。Q定义3.8对于运算集合OA和OB，我们写OA≤ E，[ω]OB，如果对于每个opA ∈OA，存在一个opB ∈ OB，使得opA ≤ E，[ω]opB。≤M.L. 坎帕尼奥洛湾Ojakian/Electronic Notes in Theoretical Computer Science 167（2007）387399正/负正/负正/负正/负给定一个函数代数，我们也可以把它看作是指定操作。对于x，y，f（x;y）∈FAN，我们可以构造函数g（x;u;z）=u+zy=0时 f（x; y）.我们可以把这看作是一个将具有论域N的任意函数f作为输入并输出函数g。定义3.9给定论域X上的一组函数B <$R，以及论域X上的运算O，我们令OP[B;O]为论域X上的以下运算集：将“函数变量”与基本函数B一起包括在内，并考虑在运算O下通过闭运算定义的函数代数。结果- ing“函数”，其中至少有一个函数变量可以被看作是操作，其中任何函数（与宇宙X）可以取代一个函数变量。下面是一个简单但反复使用的引理。引理3.10假设B1和B2是函数类，O1和O2是运算集合，它们的论域分别包含B1和B2。 如果B1≤ E，[ω]当FA [B1; O1]≤E，[ω]FA [B2;O2]时，O1≤E，[ω]OP [B2;O2].+/− +/−我的律师。 我们归纳地证明了FA[B1; O 1 ]有FA[B1;O1]≤E ，[ω]FA[B2;O2]. 对于基本函数B1 ，我们给出了这一事实。 现在考虑任何op ∈ O1的ari yk和anyf1， . . ， fk∈FA[B1;O1].Le t h=o p（f1 ， .. . . ， fk ）∈FA[B1;O1].Givenanyα∈Ewhose包含h，we当h≤α，[ω]时，需要dh∈FA[B2;O2]h.自OP ∈ O1，我们有op∈OP[B2;O2]，则op≤α，[ω]op∈ OP [B2; O2]，即α1， . . ，αk∈E这样，对于任何一个F，，f≠，使得f≤α1;[ω]f，.. .，f≤αk;[ω]f，wehave1k1+/-1k+/−kop（f1，. ，fk）≤α，[ω]op（f，. ，f）。因此，我们有这样的F…，f，所以+/−1k1k我们让h= op（f，. ，f）。Q1K前面的引理演示了近似运算的效用。要证明某个函数代数包含另一个函数代数（或近似另一个函数代数），最直接的方法是对所讨论的特定函数代数进行归纳对于另一项相关的权利要求，进行了同样的过程，从头开始有了近似操作的概念，这一技术要点符合我们的愿景，即在近似方法的背景下，试图开发一系列普遍适用的工具现在我们将展示如何以一般方式近似合成（在本文中，它将用于两种特殊情况）。我们介绍一些400M.L. 坎帕尼奥洛湾Ojakian/Electronic Notes in Theoretical Computer Science 167（2007）387+术语，以便提出索赔。定义n3.11|<$b−a<$|abb revia tes|b1−a1|+.. . +的|bn−an|.我们定义了Lipshitz条件的一个修正定义3.12• 设f是一个有n个参数的函数，L是一个有2n个参数的函数。f是L−lipshitz，如果Lc的逆不等于f的帽子，且|f（<$b）−f（a<$）|≤L（<$b;a<$）|<$b−a<$|ala和b在f的逆中。• 假设F和L是函数类，我们说F是L-lipshitz，如果对每一个f∈ F都有一个L∈ L使得f是L-lipshitz。首先，下一个引理似乎是说，当边界变得更糟时，近似变得更好。但是，请注意，对于两个边界类，P和T W，op≤1/T Wop不是一个强有力的要求比行动≤1/Pop，因为A+B A+B在后一种近似中，运算所应用的函数只有1/P的精度。引理3.13假设B是一个有界类，F是一类满足B-Lipshitz，复合闭，且满足F ≤ B的函数。然后1/BcompF ≤OP[sub，comp]。证据 设f（u），g（x）∈ F（单变量），r（x; y）∈ B. 若f≤1/α1，则α1，α2∈B f≠0且g≤1/α2 g_n，如果h（x）=f（g（x）），我们可以从f_n，g_n，comp，sub构造h_n，使得h ≤1/rh_n。设r∈（z;y）为r（x;y），其中x被新变量z取代。 设s（u;y;z）∈ B使得s（u;y;z）≥r∈（z;y）;注 的 s（u;y;z） 和α1（u;y;z）= 2s（u;y;z）是B中的.现在我们描述α2。使用我们对F的假设，设L（b; a）是f的B−Lipshitz函数，设bg是B中的函数，使得|g（x）|≤bg（x）。 设p（x;y<$）=1+2r（x;y<$）L（bg（x）;bg（x）+1）. 根据边界类的性质，存在α2（x;y）∈ B使得|p| ≤ α2。Nowsupposef（u;y;z）是su chthatf≤1/α1f，g（x;y）是su chthatg≤1/α2g。Leth（x;y<$）=f（g（x;y<$）;y<$;x）. 请注意，h是在f和g上使用的cop和sub的结果。 注意，f可以使用近似g和所有的变量;这就是我们需要任意长的参数列表的原因现在我们证明h≤1/rh。我们从以下内容开始：|≤|f（g（x））− f（g <$（x ; y <$））|+的|f（g <$（x ; y <$））− f <$（g <$（x ; y <$）; y <$; x）|.|.我们来看看上面的两个术语。考虑第一个。M.L. 坎帕尼奥洛湾Ojakian/Electronic Notes in Theoretical Computer Science 167（2007）387401埃什基.|≤L（g（x）;g））| g（x）− g <$（x ; y <$）|g (x) −g∗ (x;y¯)|≤L（g（x）;g（x） +1）|g（x）−g<$（x;y<$）|1≤L（g（x）;g（x）+1）≤1/2r（x;y<$）2r（x;y<$）L（bg（x）;bg（x） +1）对于第二个不等式，请注意，对于所有x; y，由p（x;y）的定义，g ≠ 0至少在g（x）的1以内;特别地，g≠ 0（x;y<$）≤g（x）+1。我们始终使用B中的函数正在增加的事实。考虑第二个任期。|≤1 / α 1（x ; y <$; x）≤ 1 / 2 r（x ; y），根据α 1的定义。|≤1/α1(x;y¯;x)≤1/2r(x;y),bydefinition of α1.THUS|h（x）−h<$（x，y<$）|≤1/2r+1/2r=1/r。Q4线性递归与线性微分方程在这一节中，我们应用逼近的思想来重新证明[3]中的一个结果定义4.1（来自[3]）设F是R上的一类函数。F的离散部分，记为dp（F），我们指的是论域N上的下列函数类：首先取F中所有值在N中的函数在域N上;然后将这些函数限制在域N上。在R上的关键类比运算是求线性微分方程的解;对于k∈N乘Ck，我们指的是R上的k−次连续可导函数。定义4.2L1是取任何C2函数的运算，其中TW为bounds g1（x<$）， . . ，gn（x<$），s11（x<$，y）， . . ，snn（x′，y）和returnsh1（x′，y），其中我们有以下定义方程：h1（x<$，0）=g1（x<$）.hn（x<$，0）=gn（x<$）（h1（x<$，y））=s11（x<$，y）h1（x<$，y） +.. . +s1n（x<$，y）hn（x<$，y）.402M.L. 坎帕尼奥洛湾Ojakian/Electronic Notes in Theoretical Computer Science 167（2007）387埃什基（hn（x<$，y））=sn1（x<$，y）h1（x<$，y） +.. . +snn（x<$，y）hn（x<$，y）定义4.3设基本R是以下函数，其论域为R：0， 1，−1，π，P，θ3，其中P是R上所有投影函数的集合（注意，与论域无关，我们对投影使用相同的符号π是函数t和t，f或任意k∈N（k>0），θk（x） =2000年，<0;其中x≥0。，一个Ck−1版本的不连续函数，表明一个数字是在零的左边还是右边我们现在要讨论的实数上的函数代数是：FA [碱性R; comp，LI]。注意，在L1到C2函数的限制与TW界限对这个类没有影响，但在引理5.22中用于近似L1。我们使用下面的符号从以前的文件。定义4.4设L表示函数代数FA [基本R; comp，LI]。我们现在的目标是定理4.25：dp（L）= FAN.[3]中的证明通过显示两个包含来进行。在构造FA N中的函数时，利用L的每一步运算，归纳地证明了包含包含依赖于众所周知的事实，即函数代数FAN对应于初等时间。我们将给出这个包含的另一种证明，其中我们不使用这个事实或使用任何图灵机;证明自然地使用函数代数本身的运算进行如果一个人开始考虑沿着这些路线的证明，一个明显的问题出现了。函数f∈dp（L）由于一些相关的构造树（召回定义3.5）而在那里。虽然f（与构造树的根相关联的函数）需要在自然数输入上具有自然数值，但对与构造树中的其他节点相关联的函数没有这样的约束（它们可能是实值）。为了归纳地表明f在FAN中，需要我们处理FAN中的这些非根节点;然而，如何处理FAN中的实数值还不清楚。我们解决这个问题的方法是引入一个中介函数M.L. 坎帕尼奥洛湾Ojakian/Electronic Notes in Theoretical Computer Science 167（2007）387403有论域Q的代数这个函数代数将自然地逼近L（推论4.24）。然后我们可以自然地将Q上的这个函数代数解释为FAN（见推论4.12）。该定理随后由近似关系的传递性。在本节的最后，我们将讨论一些这种方法的优点函数g在Q上的主要运算将在有界的情况下进行和（线）和有理数上的有界积（线）。 他们是德-这样，它们在应用于连续函数时保持连续函数这个属性对下一节很重要，虽然对本节不重要，但对它来说并不复杂。我们称之为运算（在n=f（x;y）上）对于固定dx∈Q的一条直线，g（x;z）=line（f
我的内容管理
展开
