没有合适的资源?快使用搜索试试~ 我知道了~
理论计算机科学电子笔记174(2007)141-149www.elsevier.com/locate/entcs一致连续模的单调辩证综合在证明系统MinLogMircea-Dan Hernest米尔西亚-丹·赫内斯特1,2信息技术学院F-91128 Palaiseau -FRANCE摘要我们在计算机上对Güodel的T(N → N)→(N → N)的一系列列的前几个元素提取了一些一致连续模。人类可以快速推断出基因组的选择。这种模的自动合成是从证明t与其自身的遗传扩张相等开始的,因此证明了在伯杰-布赫霍尔茨-施维希滕贝格系统Z的弱扩张变体中t <$(N→N)→(N→N)t。我们在机器上使用一个实现,Schwichtenberg这个新版本的单调Dialectica产生的NbE-正规形式的术语通过一个经常性的部分NbE-正规化。这种局部评价是绝对必要的。关键词:从(经典)证明中提取程序,提取程序的复杂性,MinLog中的证明和预生成的文件系统,Güodel的函数预生成,P a r t i a l E v a l uat i o n,M i n n g的预生成,单调辩证解释。1单调函数辩证法解释Kohlenbacch对G o?d el的赋形法(又称“Dialectica”)的改进是在[18]中进行的,它是对[ 8 ]中G o?d el的赋形法3的一种改进这种“单调的辩证法解释”的主要特征4对于一些精确的实现者5. 在数学实践中,这个运算证明1ProjectLogiCal-PoleComund eRecherchenfrmiquedeS aclay,CNRS,Eol ePolytechnique,INRIAetUive sitePari s-Sud-France2电子邮件:danher@lix.polytechnique.fr3论文[1]提供了一个很好的英文调查,其中包括对完整分析的扩展。[4]在本文中,我们仅积极使用Howard5它们不是有效地产生的,但它们的强烈存在是直观地保证的。1571-0661 © 2007 Elsevier B. V.在CC BY-NC-ND许可下开放访问。doi:10.1016/j.entcs.2007.01.023142M.- D. Hernest/Electronic Notes in Theoretical Computer Science 174(2007)141MMMMM要简单得多6比合成的一些实际的确切实现者的纯粹哥德尔定义1.1[单调辩证法程序提取的基本算法]我们用WeZ表示Berger-Buchholz-Schwichtenberg系统Z(在[ 2 ]中引入,也见[ 24 ])的弱扩展变体(见[10Quantifier被添加(连同它的定义公理,见[10,24]),并且还添加了所有必要的单调元素,即函数不等式常数≥连同控制其通常行为的公理7。注意,系统WeZ是,即,没有单调元素的WeZ-(在[10]中表示为WE-Z-)是[26]的第1.6.12节中所有有限类型WE-HAω中弱扩张Heyting算术定义1.2[单调辩证法提取的扩展算法]我们用WeZ+表示WeZ的扩张,其中前提独立,M m普遍前提,选择公理和马尔可夫定义1.3[[14]的第2节,改编为[10]9的T表示]霍华德x≥Ny:在(≥xy)x≥ρτy:n =zρ,zρ(z1≥ρz2→xz1≥τyz2),1 2其中≥是在[10]中定义的N×N单调的Dialectica解释(缩写为更短,MDI)是一个递归的句法翻译,从证明在WeZ+10至WeZ中的证明,使得证明的结论公式中的强正出现和负出现分别Bezem)在Godeel的T. 这些优化术语也被称为定义1.4[布尔项与无量化器公式的关联]通过无量化器公式,我们理解了一个由素公式构建的公式at(tbool)和通过来,→,如果可用,也是。这样的配方6见,例如,[21]和[22]为两个全面调查的广泛的数学应用,这种纯粹的证明理论的技术。7 ∃−详细信息参见[10]的3.1 节-我们的 系统WeZm在这里用WE−Zm表示。[8]例如,[10]的2.3节给出了这些公理的详细定义(加上注释)。9请注意[10]第3.1节中相应定义中的错别字。[10]这可以扩展到完全经典的证明,模一些双重否定翻译。11这正是Kohlenbach的MD -解释的要点[ 18 ],与他的MD I的前身[16]形成对比,后者通过Howard [ 14 ]或Bezem [ 6 ]的算法对Güo de el的Dial e c t i c a ex a c t r e a l i z errs and s ub s eque n t l y e e j o r i z i z e e s e t ize e t i zes e e t i ze e t i ze t i zeM.- D. Hernest/Electronic Notes in Theoretical Computer Science 174(2007)141143MMi=1i=1Mi=1i=1Mi=1i=1MDi=1在WeZ中是可判定的。存在布尔项到无量化器公式A0<$→tA0这样WeZ就可以► A0Participat(tA0).证明的MD-解释包括以下公式的翻译定义1.5[MD-公式的解释]递归定义:AMD:TAMD:T(tA)对于无量化器公式A(AB)MD:x,uy,v[(AB)MD:AMD(x;y;a)BMD(u;v;b)](zA(z,a))MD:z<$,x<$y[(zA(z,a))MD(z<$,x;y;a):AMD(x;y;z<$,a)](zA(z,a))MD:Xz<$,y[(zA(z,a))MD(X;z<$,y;a):AMD(X(z<$);y;z<$,a)](A→B)MD:Y,Ux,v[(A→B)MD:AMD(x;Y(x,v))→BMD(U(x);v)]其中·→·<$是一个映射,它为每个给定的变量z分配一个完全新的变量z<$,它具有相同的z类型。MD的自由变量就是A的自由变量。定理1.6(通过MD解释的主要实现子合成)12存在一种算法,在输入时给出自然演绎证明,P:{Ci(ai)}n► A(a)[因此,结论公式A,其自由变量从WeZ+中未解除的假设公式{Ci}n]形成元组a,在输出处产生以下内容(下面的let a:1,.,an,a):(i) 设置{Ti[a]}n的最大值(ii) 变量的元组{xi}n[001 pdf 1st-31 files]和T[a],它们的自由变量是和y,所有这些,(iii) WeZ中的以下验证证明(下面的let x:1,.,xn):PMD:你好,1. Yn,X [n(λ a. Ti)≥Yi<$(λ a.T)≥X <$x,y({n我 (xi;Yi(a,x,y);ai)} →AMD(X(a,x);y;a))]此外,变量x和y不会出现在P中(它们都是全新的)。因此x和y在提取的项{Ti}n和T.证据见[11]的证明草图(在自然演绎)或[18,21]的希尔伯特风格设置的等效原始公式的完整证明。Q注1.7MD-翻译证明PMD也被称为验证证明,因为它在算术上验证了MD-提取程序实际上优化了MD-解释的一些(强的,直观地证明存在的)实现器的事实。C144M.- D. Hernest/Electronic Notes in Theoretical Computer Science 174(2007)141输入时证明的结论公式[12]这个定理已经在[10]的3.1节中得到证明(以较弱的形式)。M.- D. Hernest/Electronic Notes in Theoretical Computer Science 174(2007)141145当哥德尔[A]. /BA→B. 这是因为,对于与Dialectica 13相关的缩写,收缩式A变成原始(尚未归一化)实现项的14许多这样的D-相关收缩公式,它们不是最终执行的强归一化提取项的一部分,可以在提取阶段被消除,参见[12]中的示例。不幸的是,在提取某些收缩(我们在[ 12 ]中称之为“冗余”)时,这种先验消除MD解释简化了所有非冗余相关收缩的辩证法处理,因此,每当这种“持久”收缩出现在输入证明中时,提取程序的复杂性都有重要的改进2MinLog中的最小算术HeExtEqMinLog是H. Schwichtenberg和慕尼黑大学逻辑小组的成员。 它基于一阶自然演绎演算,并使用原始最小而不是经典或直觉逻辑。见[9,25]详细信息。遗传延伸相等性检验案例(简称HeExtEq)是由U.Kohlenbach作为应用Mono-tone Dialectica程序从证明中提取的一个有趣的例子,见[21]的第8章。事实上,在[20]的第五章中,它已经通过[16]中介绍的单调辩证法的前身在理论层面上进行了。[21]中的处理甚至更柏拉图式,通过大量的元定理。我们接受了使用机器提取的挑战,以便在计算机上分析HeExtEq示例的一些具体实例定义2.1[[26],第2.7.2节,改编为[10]中的T在类型σ<$σ 1.σnN,记为= σ,定义为x = Ny:xat(=xy)x= σy:zσ1. . zσn(xz1. . . zn=Nyz1. . . zn),1N其中=在[ 10 ]中被定义为N × N上的普通相等布尔函数。直接的是x = ρτyzρ(xz =τyz)。 作为与可 优性的平行[13]并非所有的逻辑缩略语都与《辩证法》的解释相关,参见[12]关于这个问题的简短说明或[11]关于全部细节。[14]通过与MD-根式A MD(一个无量化器的公式)相关联的布尔项(见定义1.4),MD又通过定义1.5与公式A相关联。146M.- D. Hernest/Electronic Notes in Theoretical Computer Science 174(2007)141N→NN→N)→(N→N)关系(见定义1.3),遗传延伸等式定义在T型结构,xNy:x=Nyx<$ρτy:<$$>zρ,zρ(z1<$ρz2→xz1<$τyz2),1 2定义2.2[最小算术]我们用WeZm表示系统WeZ,它没有强代数,也没有Ex-Farso-Quodlibet公理→F,因此具有一个底层的最小逻辑(在[15]的意义上)子结构。命题2.3([20] - 5.13或[21] - 8.17,改编)L ettρbea clos edtermofG?odel's T. Wez先生不介 意 。证据通过对t的组合结构的归纳,由于哥德尔T的闭项无λ-abstraction)from0,Suc,Géodelr R and d c o m b i n a t r s t r a n d e n.Q推论2.4([20,21])设t(N→N)→(N→N)是闭T-项. 以来WeZm<$$>xN→N,yN→N[x=N→NyParticix<$N→Ny],它立即遵循,WeZm=N→N,yN→N[x=N→Ny→t(x)=N→Nt(y) ].命题2.5([20] - 5.15或[21] - 8.19,改编)设t(N→N)→(N→N)是GüodelT. 这是一致的,因为每个节点都有一个封闭的定义:N{xN→N|北卡罗来纳州 y(z)≥Nx(z)},其一致连续模是等价的y(uniformlyyinyN→ N),即T的一个封闭的模t(y)N→N,即,一个可以通过MD-interrretation)闭合的T-temt(s.t.:Wez► y< $x,x∈B <$Net(y)(k) x(i)=x(i)→Kt(x)(j)=t(x)(j)]m12y k[1N2i=0时1N2j=0证据直接从推论2.4和定理1.6,见[20,21]的细节(在希尔伯特风格的设置)证明最初介绍在[17]。QHeExtEq示例在MinLog[9]中实现,因为N→N,y[x = N→Ny→t(x)=N→Nt(y)]对于每个特定的T项t(N→N)→(N→N),通过方案[23]程序机械地生成,该程序将这样的具体MinLogT项t作为参数。[20]的引理2.6给出了从λ-项到组合项的句法转换。M.- D. Hernest/Electronic Notes in Theoretical Computer Science 174(2007)141147˜3浅单调的辩证法解读我们的方法用于均匀连续t的通用模的MinLog提取,给定具体的MinLog项t与命题2.5的字母不同。事实上,它相当于MD解释的新变体的设计,其结合了由于Kohlenbach16而产生的先前存在的版本的那些特征,这些特征在机器上是有用的我们在这里命名为轻单调辩证法(缩写为LMD-解释,甚至更短,LMDI),这种优化的Kohlenbach的MD -解释的提取因此,新的光MD解释的特殊性是正规形式的项的产生。一般来说,一个术语的标准形式可能比它通过抽象的更紧凑的表示更大。但另一方面,规范化可以消除许多冗余的部分,的ESTA项。我们的实际经验与自动化,机器程序提取,表明后一种情况更经常出现在我们的实验中,特别是对于HeExtEq的情况。这种新形式的MD解释的主要特点如下:(i) 在输入证明结构上递归的每一步提取的项既不是精确实现子,也不是优数,而是部分优数,在这个意义上,只有持久压缩像[18]中那样处理(ii) 在每个隐含消除(又名推理前件)应用的结论的证明挖掘之后,出于优化目的,执行这种提取的部分优变量的NbE归一化(参见[3,4,5]的原始NbE)这种反复出现的部分标准化形式带来了巨大的改进。在嵌套的前件式的长序列的情况下的单个最终按值调用NbE归一化过程。我们将此技术命名为“提取期间的HeExtEq证明(在上面的第2节中描述)实际上包含了相当长的嵌套前件式序列。(iii) 最 后 的 这 种 提 取 的 部 分 优 变 量 是 NbE- 归 一 化 的 , 然 后 它 的 majorant 是builtlikein[16],但使用的是Godeel的rec ur s orRfrom [ 19 ]的majorant4MinLog中HeExtEq案例研究的机器结果我们使用了我们的轻型Monotone DialecticaMinLog提取模块,这些模块在特殊的19MinLog发行版中可用[9]。我们用了LMDI提取物-[16]我们区分了单调辩证法解释的三种变体,它们是在(按时间顺序排列的)[16],[18]和最后[19]中引入的。另见朱克3 - 6,原始的,非正式的和相当原始的形式的MD-解释。[17]这里的原始的按值调用NbE规范化技术参见[3,4,518这是部分求值的一种循环形式部分评价方案编制方法的说明见卷[7]19我们的Dialectica模块目前与来自[25]的官方MinLog发行版不兼容148M.- D. Hernest/Electronic Notes in Theoretical Computer Science 174(2007)141在MinLog HeExtEq证明中,对于项t的以下具体实例:• 简单求和:f,k <$→ f(0)+···+f(k)。• 双重和:f,k <$→ f(f(0))+···+f(f(k))。• 三重和:f,k <$→ f(f(f(0)+···+f(f(f(k)。在简单和的情况下,机器的输出如预期的那样是恒等函数,而与实际的f无关,因此是泛函f,k<$→k。同样对于双和,结果是期望的,即f,k →max{k,f(0),···,f(k)}。相反,对于三重和,数学家需要工作好几分钟才能产生以下最佳结果f,k →max{k,f(0),f(1),.,f(max{k,f(0),f(1),. . .,f(k)})}(1)机器在不到一分钟的时间内产生的输出可以是等体积的,物理上适于显示如下:f,k →max{k,f(0),.,f(k),max{f(0),. . . ,f(max{f(0),. . . ,f(k)})}(2)很容易注意到,机器生成的表达式(2)直接等同于更人性化的表达式(1)。还请注意,在逐点连续性需求的上下文中,最佳答案为f,g,k → max{k,f(0),f(1),. . . ,f(k),max{f(f(0)),f(f(1)),. ,f(f(k))}}其严格低于对于一致连续性的情况的机器(或人)最优输出。事实上,当我们第一次试图用大脑解决三重和问题时,我们首先错误地认为这是一个一致连续的模,事实并非如此。我们后来通过简化机器结果产生了(1)(2)经过检查,我们意识到了错误。因此,我们只能在计算机提取的帮助下才尽管如此,现在人类可以注意到在项tl的HeExtEq问题的解决方案中的模式:λf,k.f(l)(0)+···+f(l)(k),其中f(l)(i):λf(f···(f(i),其中f在右侧出现l次我们再次写出上面对于tl的一致连续模,其中l:=1,2,3:t1(f,k)M.- D. Hernest/Electronic Notes in Theoretical Computer Science 174(2007)141149t∈2(f,k)≠x{k,f(0), . . , f(t<$1(f,k))}t∈3(f,k)≠x{k,f(0), . . , f(t<$2(f,k))}·······································150M.- D. Hernest/Electronic Notes in Theoretical Computer Science 174(2007)141˜因此,我们立即推导出对于每个l∈N的一般(递归)解:t∈l+1(f,k)∈x{k,f(0), . . , f(t<$l(f,k))}证明tl是tl的一致连续的最优模现在是一个简单的练习,我们留给读者(见[11]的解决方案)。5结论和今后的工作对于输入项t的其他各种具体实例,可以并且应该执行更多这样的一致连续性模量的MinLog提取。轻MD-解释应该在数学上形式化,与哥德尔的辩证法[ 1 0 ]的轻优化相结合。这意味着该方法也适用于HeExtEq证明的情况。应高度优先研究这一问题。还应该给出提取期间归一化(NdE)的完整数学公式。确认感谢U教授。感谢Kohlenbach向我们提出HeExtEq的例子可能会在计算机上产生有趣的结果。我们也感谢教授。H. 施维希滕贝格向我们提出,从计算机应用的角度来看,单调(或有界)辩证法的现有公式可能不够令人满意引用[1] 再见,J。 和S。 Feferman,G?odel's fun cti o n a l('Di a l e cti c a ')interp r et a t i o n,in:S. Buss, editorr, Handbook of Proof Theory,Studies in Logic and the Foundations of Mathematics 137,Elsevier,1998,pp. 337-405[2] 伯 杰 大 学 , W. Buchholz 和 H. Schwichtenberg , Refined Program Extraction from Classical Proofs,Annals of Pure and Applied Logic114(2002),pp. 三比二十五[3] 伯杰,美国和H. Schwichtenberg,An inverse of the evaluation functional for typed λR. Vemuri,编辑,Proceedings of the Sixth IEEE Symposium on Logic in Computer Science,IEEEComputer Society Press,Los Alamitos,1991,pp.203-211.[4] Berger,U., M. EberlandH. Schwichtenberg,N or mal iz ati onyEv aluati on,in:B. Moéll eranddJ.Tucker,编者,《硬件基础展望》,LNCS 1546,Springer Verlag,1998年,第110页。117比137[5] 伯 杰 大 学 , M. Eberl 和 H. Schwichtenberg , Term rewriting for normalization by evaluation ,Information and Computation183(2003),pp. 19[6] Bezem,M.,有限型强可优化泛函:包含不连续泛函的,J。的Symbol。《逻辑》50(1985),pp.652-660[7] Danvy,O.,R.GlučkandP.这位女士编辑说,“P a r t i a l E v a l uat i on。 DagstuhlCastle,Germany,February 1996”,LNCS 1110,Springer Verlag,1996.[8] Godel,K.,U?bereinebishernochnichtenu?teErweiterungdefinnitenStandpunktes,Dialectica12(1958),pp. 280-287M.- D. Hernest/Electronic Notes in Theoretical Computer Science 174(2007)141151[9] Hernest,M.D、MinLogforDialecticaprogram-extraction,Freesoftware-codehttp://www.brics.dk/edanher/MinLogForDialectica,官方MinLog见[25].[10] Hernest,M. D、Light Functional Interpretation,LNCS3634,Springer Verlag,2005,pp. 477 -[11]Hernest,M.D、 可行的程序从(非建设性)证明轻(单调)辩证法i nterpret ati on,PhDThe s i s,E'col e Polytechni qu eandUniver s ityofMunich( 2006 ) , Inpre pration, drafthttp://www.brics.dk/ edanher/teza/.[12] Hernest , M.D 、 Light Dialectica program extraction from a classical Fibonacciproof , in :Proceedings of DCM接受出版,http://www.brics.dk/e danher/.[13] Hernest,M.D、 NdE-提取过程中的归一化,定期摘要,CiE'06的本地会议记录http://www.brics.dk/(2006年欧洲可计算性),可在作者的网页上获得,参见www.example.com e danher/。全文正在编写中。[14] 霍华德,W.,有限型的遗传可优化泛函,在[26],附录章节,第454- 461页。[15] 约翰在上面,I. 、DerMinimalkalku?l,埃伊恩reduzierter 我不知道你在说什么对于那些不幸的人,Comp os itioMatematica 4(1936),pp. 119比136[16] 科伦巴赫大学,从分析中的非有效证明的有效界限:函数解释和优化的应用,J。Logic57(1992),pp.1239-1273年。[17] 科伦巴赫大学,点态遗传优化和一些应用,Archive for Mathematical Logic31(1992),pp. 227-241[18] 科伦巴赫大学,在分析中分析证明,在:W。Hodges,M.海兰角Steinhorn和J. Truss,编辑,逻辑:从基础到应用,Keele,1993,欧洲逻辑讨论会(1996),pp. 225-260.[19] 科伦 巴赫大学 ,数学 上强大的 分析子系 统与可证 明递归泛 函的低增 长率, Archive for MathematicalLogic36(1996),pp. 31比71[20] 科 伦 巴 赫 大 学 ,证 明 解 释 , 技 术报 告 BRICS LS-98-1 , DAIMI , Department of ComputerScience,UniversityofAarhus,Aarhus,Denmark(1998),Freehttp://www.brics.dk/LS/Abs/BRICS-LS-Abs/BRICS-LS-Abs.html.[21] 科伦巴赫大学,Proof Interpretations and the Computational Content of Proofs,作者网页最新版本[22] 科伦巴赫大学Oliva,Proof mining:A systematic way of analyzing proofs in Mathematics,Proc. of theSteklov Institute of Mathematics242(2003),pp. 136-164。[23] Cadence Research Systems,(Petite)Chez Scheme,http://www.scheme.com(2006)。[24] Schwichtenberg,H.,可计算函数的最小逻辑,从(经典)证明中提取程序的讲座课程。在MinLog发行版中可用[25]。[25] Schwichtenberg,H.和其他,证明和程序提取系统MinLog,免费软件-代码源和文档@http://www.minlog-system.de/.[26] Troelstra,A.,编者,
下载后可阅读完整内容,剩余1页未读,立即下载
cpongm
- 粉丝: 4
- 资源: 2万+
上传资源 快速赚钱
- 我的内容管理 收起
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
会员权益专享
最新资源
- 基于单片机的瓦斯监控系统硬件设计.doc
- 基于单片机的流量检测系统的设计_机电一体化毕业设计.doc
- 基于单片机的继电器设计.doc
- 基于单片机的湿度计设计.doc
- 基于单片机的流量控制系统设计.doc
- 基于单片机的火灾自动报警系统毕业设计.docx
- 基于单片机的铁路道口报警系统设计毕业设计.doc
- 基于单片机的铁路道口报警研究与设计.doc
- 基于单片机的流水灯设计.doc
- 基于单片机的时钟系统设计.doc
- 基于单片机的录音器的设计.doc
- 基于单片机的万能铣床设计设计.doc
- 基于单片机的简易安防声光报警器设计.doc
- 基于单片机的脉搏测量器设计.doc
- 基于单片机的家用防盗报警系统设计.doc
- 基于单片机的简易电子钟设计.doc
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功