COMPUTING AS COMPRESSION - AN OVERVIEW OF THE SP THEORY AND SYSTEM
This article is an overview of a programme of research based on the conjecture that all kinds of computing and formal reasoning may usefully be understood as information compression by pattern matching, unification and metrics-guided search. The research aims to develop this idea into a theory of computing to integrate and simplify diverse concepts in the field. The research also aims to develop a 'new generation' computing system, based on the theory, to integrate and simplify diverse kinds of computing and to achieve more flexibility and 'intelligence' than conventional computers. Software simulations of the proposed new system provide a concrete expression of the developing theory and a test-bed for the ideas. The background to the research is briefly reviewed including evidence that information compression is a significant element in biological information processing systems. Concepts of information and redundancy are described as a basis for describing how information compression may be achieved by the comparison or matching of patterns, the merging or unification of patterns which are the same, together with metrics-guided search (e.g., 'hill climbing', 'beam search') to maximise compression for a given computational effort. The main elements of the SP theory and of the proposed SP system are described with a summary of developments to date. Some of the kinds of computing which be interpreted as information compression are briefly reviewed. These include: the 'low level' workings of conventional computers; information retrieval, pattern recognition and de-referencing of identifiers; unsupervised inductive learning (grammatical inference, data mining, automatic organisation of software and of knowledge bases); the execution of mathematical or computing functions; deductive and probabilistic inference; parsing and natural language processing; planning and problem solving. Areas of uncertainty where further work is needed are indicated at appropriate points throughout the article.
information compression theory of computing information retrieval pattern recognition learning deduction abduction