Foundations of computing with continuous data: algorithms versus experiments with physical systems

物理世界的信息和数据由自然数0、1、2、3、…表示或编码，通常以二进制记数法表示。可以构造物理系统来执行数字计算，例如查尔斯·巴贝奇的机械差分机或当代电子计算机。数字计算机对二进制数执行逻辑和算术运算，并可通过使用已知的物理定律来预测机械系统的行为。即使是非常复杂和有用的系统也是如此，例如对飞机周围的气流进行建模。然而，有可能构建一个计算机无法预测其行为的物理系统吗？在这里，我们在理论和实际之间划出了一条线，在一个混乱的系统中，比如天气，我们可能必须非常准确地知道初始条件，以便预测未来给定时间的事件。我们将考虑这样一个问题，即是否存在表现更差的系统，在这些系统中，任何可以想象的初始精度都无法通过数字计算机提供合理的预测。这样的系统可能会为计算机提供新的更强大的非数字技术。物理系统是用实数来衡量的。现在，实数，如2，1.41421的平方根，是无限长的，在有限的数字计算机中很难处理。因此，从本质上讲，这个问题涉及到计算机如何处理实数，以及它们如何控制实数计算的准确性的理论。该项目的一个主线是找到用实数‘精确’编程的新方法，并将这些方法应用于机械系统，如一般相空间上的哈密顿力学。这涉及到对系统几何形状的可计算描述。它还涉及计算机如何与机械系统相互作用的精确规范。这里的目的之一是说，如果应用某些限制，某些类别的机械系统是可计算的。假设一个系统遵循一定的物理定律，并且具有操纵该系统的特定语言，那么数字计算机什么时候可以预测实验结果呢？当这些结果应用于更一般的系统时，这些结果是如何分解的？另一条线索是寻找在某种意义上不可计算的新型机械系统，并对其进行分析。一方面，一个物理系统可以找到不可计算的量，如果它们从一开始就被构建到它的设计中，尽管有时这是以非常不明显的方式发生的。因此，有必要将机器的建造过程包括在关于可计算性的辩论中。

n the physical world information and data is represented or coded by the natural numbers 0,1,2,3,..., usually in binary notation. Physical systems can be constructed to carry out digital computation, for example Charles Babbage's mechanical Difference Engine or a contemporary electronic computer. Digital computers execute logical and arithmetic operations on binary numbers, and can be used to predict the behaviour of mechanical systems by using the known laws of physics. This is true even of very complicated and useful systems, such as modelling the airflow round an aircraft. However, is it possible to construct a physical system whose behaviour cannot be predicted by a computer? Here we draw a line between theory and practicality, a chaotic system such as the weather is one where we might have to know the initial conditions incredibly accurately in order to predict events a given time in the future. We will consider the question as to whether there are much worse behaved systems, ones in which no conceivable amount of initial accuracy can ever deliver a sensible prediction by a digital computer. Such systems might suggest new more powerful non-digital technologies for computers.Physical systems are measured using real numbers. Now real numbers, such as the square root of 2, 1.41421..., are infinitely long and difficult to handle in a finite digital computer. Therefore by its nature, this problem involves the theory of how computers deal with real numbers, and how they control the accuracy of their computations with real numbers. One thread of the project is to find new methods for programming 'exactly' with real numbers, and to apply these methods to mechanical systems such as Hamiltonian mechanics on general phase spaces. This involves a computable description of the geometry of the system. It also involves precise specification of how a computer can interact with a mechanical system.One aim here is to say that certain classes of mechanical system are computable if certain restrictions apply. Given a system which obeys certain physical laws, and with a specified language for manipulating the system, when are the results of experiments predictable by a digital computer? How do these results break down when applied to more general systems?The other thread is to find novel mechanical systems, which are , in some sense, not computable, and analyse them. One aspect is that a physical system can find non-computable quantities if they are built into its design from the start, though sometimes this occurs in a very non-obvious fashion. It is then necessary to include the process of construction of the machine in the debate about computability.