论文标题
关于非竞争性的非可探可可探可以及数字计算机上电路方程解决方案的不合同性的程度
On non-detectability of non-computability and the degree of non-computability of solutions of circuit and wave equations on digital computers
论文作者
论文摘要
众所周知，存在实用相关性的数学问题，这些问题无法在图灵机上计算。一个重要的例子是计算连续可区分函数的第一个衍生物。本文精确地对Zheng-Weihrauch层次结构中第一衍生物的最大声明的最大声音进行了分类。基于此分类，本文研究了图灵机是否有可能通过观察问题的数据来检测第一个衍生物的这种非竞争性，以及是否可以检测到连续微分函数的第一个衍生物的峰值值的上限。因此，从实际的角度来看，问题是是否可以实现观察第一个衍生物的非竞争性的出口范围功能。本文甚至研究了两种不同类型的出口质量功能。一个强大的图灵机必须总是停止的，而弱的机器则在且仅当输入位于相应的关注集中时停止。可以证明，图灵机无法检测到第一个衍生物的非竞争性，即两个具体示例，即用于计算输入的问题 - 简单模拟电路的输出行为以及三维波方程的解决方案。另外，还表明，对于第一派生的最大规范，甚至不可能检测到上限。特别是，这表明这三个问题甚至都不是半决定的。最后，我们简要讨论了这些结果对模拟和量子计算的含义。
It is known that there exist mathematical problems of practical relevance which cannot be computed on a Turing machine. An important example is the calculation of the first derivative of continuously differentiable functions. This paper precisely classifies the non-computability of the first derivative, and of the maximum-norm of the first derivative in the Zheng-Weihrauch hierarchy. Based on this classification, the paper investigates whether it is possible that a Turing machine detects this non-computability of the first derivative by observing the data of the problem, and whether it is possible to detect upper bounds for the peak value of the first derivative of continuously differentiable functions. So from a practical point of view, the question is whether it is possible to implement an exit-flag functionality for observing non-computability of the first derivative. This paper even studies two different types of exit-flag functionality. A strong one, where the Turing machine always has to stop, and a weak one, where the Turing machine stops if and only if the input lies within the corresponding set of interest. It will be shown that non-computability of the first derivative is not detectable by a Turing machine for two concrete examples, namely for the problem of computing the input--output behavior of simple analog circuits and for solutions of the three-dimensional wave equation. In addition, it is shown that it is even impossible to detect an upper bound for the maximum norm of the first derivative. In particular, it is shown that all three problems are not even semidecidable. Finally, we briefly discuss implications of these results for analog and quantum computing.
