Mathematical Theory and Computational Practice
Mathematical Theory and Computational Practice
复制标题
数学理论与计算实践
DOI：
10.1007/978-3-642-03073-4_42
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
Pratt-Hartmann I
中科院分区：
文献类型：
--
作者：
Pratt-Hartmann I
算数电路是一个带标签的有向非循环图，指定要对非负整数集执行的算术和逻辑运算的级联。在本文中，我们通过算术电路考虑从非负整数集合的元组到非负整数集合的函数的可定义性。我们证明了两个负面结果：第一个粗略地表明，如果一个函数具有无限范围和亚线性增长，那么它就不是电路可定义的；第二个粗略地表明，如果一个函数具有有限的范围并且无法收敛到包含在内的某些“稀疏”链上，则该函数不是电路可定义的。我们观察到各种感兴趣的功能都属于这些描述。
Anarithmetic circuitis a labelled, directed, acyclic graph specifying a cascade of arithmetic and logical operations to be performed on sets of non-negative integers. In this paper, we consider the definability of functions from tuples of sets of non-negative integers to sets of non-negative integers by means of arithmetic circuits. We prove two negative results: the first shows, roughly, that a function is not circuit-definable if it has an infinite range and sub-linear growth; the second shows, roughly, that a function is not circuit-definable if it has a finite range and fails to converge on certain ‘sparse’ chains under inclusion. We observe that various functions of interest fall under these descriptions.