论文标题
关于带宽信号的带宽的算术复杂性
On the Arithmetic Complexity of the Bandwidth of Bandlimited Signals
论文作者
论文摘要
信号的带宽是重要的物理属性，在许多信号和信息理论应用中都具有相关性。在本文中，我们研究了与可计算带限制信号的带宽相关的问题。为此，我们采用了图灵计算性的概念，该概念准确地描述了理论上可行的内容，并且可以在数字计算机上计算。最近，已经表明，存在具有有限能量的可计算带限制信号，其实际带宽不是可计算的数字，因此无法在数字计算机上计算。在这项工作中，我们考虑了最通用的频带限制信号，以及其不同的可计算表示。除其他外，我们的分析还包括对此类信号的带宽的算术复杂性的特征，并对是否至少可以计算有限制信号的带宽的非平凡的上限或下界产生了负面答案。此外，我们将带宽计算的问题与Oracle机器的理论联系起来。特别是，我们考虑停止和整体甲然素，这些序列属于计算理论中最常研究的甲骨文机器。
The bandwidth of a signal is an important physical property that is of relevance in many signal- and information-theoretic applications. In this paper we study questions related to the computability of the bandwidth of computable bandlimited signals. To this end we employ the concept of Turing computability, which exactly describes what is theoretically feasible and can be computed on a digital computer. Recently, it has been shown that there exist computable bandlimited signals with finite energy, the actual bandwidth of which is not a computable number, and hence cannot be computed on a digital computer. In this work, we consider the most general class of band-limited signals, together with different computable representations thereof. Among other things, our analysis includes a characterization of the arithmetic complexity of the bandwidth of such signals and yields a negative answer to the question of whether it is at least possible to compute non-trivial upper or lower bounds for the bandwidth of a bandlimited signal. Furthermore, we relate the problem of bandwidth computation to the theory of oracle machines. In particular, we consider halting and totality oracles, which belong to the most frequently investigated oracle machines in the theory of computation.
