(N, +, V2, V3) IS UNDECIDABLE

被引：0

作者：

VILLEMAIRE, R

机构：

来源：

COMPTES RENDUS DE L ACADEMIE DES SCIENCES SERIE I-MATHEMATIQUE | 1992年 / 314卷 / 10期

关键词：

D O I：

暂无

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

Let V2 and V3 be the functions of N to N which sends x to the greatest power of 2 which divides x and to the greatest power of 3 which divides x, respectively. It is shown that the theory of < N, + V2, V3 > is undecidable. By Buchi's Theorem [21, this means that there is no machine which recognizes exactly the sets of integers built up from the 2-recognizable sets and from the 3-recognizable sets by the operations of intersection, complementation and projection.

引用

页码：775 / 777

页数：3