Measuring Power of Algorithms, Programs and Automata
Mark Burgin · 2010
We are living in a world where complexity of systems created and studied by people grows beyond all imaginable limits. Computers, their software and their networks are among the most complicated systems of our time. Science is the only efficient tool for dealing with this overwhelming complexity. One of the methodologies developed in science is the axiomatic approach. It proved to be very powerful in mathematics. In this paper, we develop further an axiomatic approach in computer science initiated by Manna, Blum and other researchers. In the traditional constructive setting, different classes of algorithms (programs, processes or automata) are studied separately, with some indication of relations between these classes. Thus, the constructive approach gave birth to the theory of Turing machines, theory of partial recursive functions, theory of finite automata, and other theories of constructive models of algorithms. The axiomatic context allows one to research classes of classes of algorithms, automata, and processes. As a result, axiomatic approach goes higher in the hierarchy of co mputer and network models, reducing in such a way complexity of their study. The suggested axiomatic methodology is applied to evaluation of possibilities of computers and their networks. People more and more rely on computers and other information process ing systems. So, it is vital to know better than now what computers and other information processing systems can do and what they can’t do. The main emphasis is done on such properties as computability, decidability, and acceptability.