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

点击翻译按钮获取中文摘要

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.