Computation on many-sorted topological algebras: digital and analog paradigms

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

My research in recent years has been in the development of the theory of computation on abstract data types. I have done this largely in collaboration with my colleagues and students in many publications. Classical computability theory, as developed by Turing, Kleene, Church and others, concerned computation over "discrete" structures, such the natural numbers, or integers, or strings ("words") generated by a finite alphabet. However, when computing on "continuous" structures such as the real numbers. the classical techniques do not always work, and the classical results do not always hold. For example, testing for equality between two real numbers is not always decidable. Developing theories of computation on the reals is clearly extremely important, since scientific data are generally given as real numbers (or rational approximations to them). An important distinction can be made between "digital" and "analog" computation. I have also been investigating the relationship between these two paradigms. Computation on discrete structures such as the integers is generally digital, whereas computation on continuous structures can be digital or analog. Briefly, digital computation works by algorithms, represented as programs in a computer, and analog computation works with simulation time, and is "exact". In analog computation, data are represented by physical quantities (e.g. voltage) which are processed by networks of components. I also want to investigate the theory of "hybrid" systems, which investigates analog-digital interfaces. The practical benefit of this is clear, because of the increasingly common use of hybrid systems.