lambda演算下的半群问题及表示

可在www.sciencedirect.com在线获取理论计算机科学电子笔记325（2016）299-304www.elsevier.com/locate/entcs关于半群及其它同余在λ演算里克·斯塔曼1卡内基梅隆大学，宾夕法尼亚州美国摘要我们表明，每一个半群的RE字的问题，可以逐点表示的lambda演算。此外，我们证明了由任意RE组合子子集生成的自由幺半群可以表示为固定有限点集的所有项的幺半群保留字：lambda演算，半群，表示1引言组合器既是函数又是参数，可以通过应用和组合相互作用。更一般地，如果$J 和 $” 是 在 beta 转 换 下 封 闭 的 组 合 子 集 合 ， 则 $ j 对 $” 的 A 作 用 是 集 合{AMN|M：$J和N：$”}在beta转换下关闭。首先，我们回顾一下一些熟悉的组合子的定义：B ： =λabc.a（ bc ） BJ ：=λabc.b （ ac ）C：=λab.baK：=λab.aI：=λa.aS：=λabc.ac（bc）O：=（λx.xx）（λx.xx）0：=λyz.zs：=λxyz.y（xyz）Y：=（λxz.z（xxz））（λxyz.z（xxz））例1.1A：=K：这是平凡的动作。例1.2A：=I：这是应用动作。1电子邮件：statman@cs.cmu.eduhttp://dx.doi.org/10.1016/j.entcs.2016.09.0441571-0661/© 2016作者。出版社：Elsevier B.V.这是CC BY许可下的开放获取文章（http://creativecommons.org/licenses/by/4.0/）。300R. Statman/Electronic Notes in Theoretical Computer Science 325（2016）299∼例1.3A：=B：这是半群作用。例1.4A：=S：逐点应用动作。当然，这个定义通过Currying扩展到多个参数。 我们写M=N mod beta如果Mβ转换为N。一般的A可以简化为I，多个参数可以通过配对简化为一个参数，这是微不足道的。此外，由于K（xy）=Bx（Ky）mod beta，所以应用作用可以归结为半群作用.然而，还有另一个约化，即λI。让D：= Y（λfxyz. fx（zy）），其中Y是上面的图灵定点组合子。引理1.5对于任何U，V，如果B（C<$U）D=B（C<$V）Dmod beta，则U = V mod beta。证据直 截 了 当 。Q现在给定$J和$JJ，因为C（AM）=B（B（CM）（CA））Bmod betaC（AMN）=B（B（B（CM）（CA））B）（B（CN）D）mod beta，以及=B（C<$M）（B（C<$A）（BB（B（C<$N）D）mod beta$J在$JJ上的A作用等价于{CM|M：$J}在{（B（C<$A）（BB（B（C<$N）D）上|N：$JJ}。下面我们考虑I在表示半群时的作用的一个例子。定义1.6令$J是在beta转换下闭的组合子的RE集合。在$J上的等价关系被称为在$JJ上是逐点可表示的，如果对于每个M，N：$J，我们有MP：$JJ对于所有P：$JJMNi for allP：$JJMP=NP mod beta实施例1.7（Kleene）：$J=全递归函数$JJ=教会数字，<$j=外延相等R. Statman/Electronic Notes in Theoretical Computer Science 325（2016）299301非示例（Plotkin）：302R. Statman/Electronic Notes in Theoretical Computer Science 325（2016）299$J=所有组合子$JJ=所有的组合子，而= beta转换。设$是生成元个数可数的半群。我们假设生成元用正整数表示。$的元素用单词表示w= w（1）. w（l）。在$的生成元上的可变长度l我们写u=v mod $，如果单词uv等于$。 我们用λ项' w j：= B j Ow（1）（B j Ow（2）（. BJOw（n− 1）Ow（n）.. . ））其中整数被它们的Church数字替换。我们定义组合子P，Q，R如下。根据[7]的定理3，存在一个闭项P，使得PM=PN mod beta当且仅当M=Nmod beta或M=现在我们开始p：=教会数字的前身，以及A：= Y（λxy. y 0（B（py）1）（An = Imodbeta的n次η展开式）Q：= λxy .Y（Ax（fsx）（Py））R：= Q 0.对于每个单词w，我们通过lambda项定义第二个表示“w jj：= B（C 'w j）B.则B和 为 任何 单词w1，.，wn，u1，...，um“w j j（R“w 1 jj.. . “w n j j）（R j j u j 1 j.. .=Q（n+1）（P（“w1jj”））。 . （P（“w n j j））（P“w j j（（R“u j 1 j. .=Q（n+1）（P（“w1jj”））。 . （P（“w n j j））（P“w j j）m o d b et a.现在不难证明，如果Q（n+1）（P（“w1jj））.. . （P（=Q（n+1）（P（“w1jj”））。 . （P（“ w n jj ） ） （ P “ u j j ） m o d b e t a t h e n w = u m o d $ .N o w tk e for$J是所有“w j j”的集合，对于$jj是所有R（“w1jj"）的集合。 . （“W N JJ）。我们我们已经证明了R. Statman/Electronic Notes in Theoretical Computer Science 325（2016）299303命题1.8每个RE半群都是点态可表示的。304R. Statman/Electronic Notes in Theoretical Computer Science 325（2016）299∼对于一般的RE同余，我们以二元函数sym bol f为例进行了说明.我们假设我们有一个哥德尔n，它把t，r的项t j，r j与一个由λ项F表示的递归函数t，r <$→ftr联系起来，即F 't j ' r j = ' ftr j mod beta。根据[ 7 ]的定理3，存在一个闭项P，使得PM=PNmod beta当且仅当M=Nmod beta或M=“uj mod beta，N =”vjmod beta和u = v mod $。现在定义一个应用程序A：= λabcde。阿贾河定义”“f“：= λxy。A，F（xK）（yK），P（F（xK）（yK））集合$JJ可以被认为是所有项的集合。 因此，在本发明中，命题1.9每个RE同余都是逐点可表示的。这些表示结果隐含地使用表示的如果表示函数本质上是不规则的，并且在该集合上的beta转换是可判定的，例如Church数的集合，则可以表示co-RE同余。对于哥德尔数为e的递归函数使用Kleene括号{e}，我们有引理1.10设k是自然数集合上的co-RE等价关系。则存在一个递归函数f，使得对于任意e，{f（e）}是全递归的，且i<$ji <${f（i）}={f（j）}。证据我们递归地进行，假设f（i）被定义为i= 0，...，n.为了定义f（n+1），我们计算连续值{f（n +1）}（j），其中j = 0，...， K. 假设这些已经计算到k。为了计算k +1的值，让@是{0，1，...，n}，使得i：@ i ≠不存在j

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