(1) 阅读 (1074)

比奇算术 编辑

词条创建者 匿名用户

比奇算术

编辑

基数为k的比奇算术是自然数的一阶理论,有加法和函数它被定义为k的xxx幂除以x,为纪念瑞士数学家JuliusRichardBüchi而命名。Büchi算术的签名只包含加法运算。和平等,完全省略了乘法运算。与Peano算术不同,Büchi算术是一个可解理论。这意味着,对于比奇算术语言中的任何句子,都可以有效地确定该句子是否可以从比奇算术的公理中得到证明。

比奇算术和自动机

编辑

一个子集在基数为k的Büchi算术中是可定义的,当且仅当它是可识别的。如果n=1{displaystylen=1},这意味着整数集是可以被识别的。这意味着基数为k的X的整数集被一个自动机所接受。同样地,如果n>1{displaystylen>1}存在一个自动机,可以读取xxx个数字。存在一个自动机,它读取基数为k的n个整数的xxx个数字,然后是第二个数字,以此类推,如果这n个整数在关系式X中,则接受这些字。

比奇算术

Büchi算术的属性

编辑

如果k和l是乘法依赖的,那么基数为k和l的Büchi算术具有相同的表达能力。事实上此外,根据Cobham-Semënov定理,如果一个关系在k和lBüchi算术中都可以定义,那么它在Presburger算术中也可以定义。


内容由匿名用户提供,本内容不代表vibaike.com立场,内容投诉举报请联系vibaike.com客服。如若转载,请注明出处:https://vibaike.com/167675/

发表评论

登录后才能评论

词条目录
  1. 比奇算术
  2. 比奇算术和自动机
  3. Büchi算术的属性

轻触这里

关闭目录

目录