Computing and Information Compression: A Reply

Article type: Research Article

Authors: Wolff, J. Gerard

Affiliations: School of Electronic Engineering and Computer Systems, University of Wales, Dean Street, Bangor, Gwynedd, LL57 1UT, UK. Telephone: +44 248 382691; fax: +44 248 361429. E-mail: gerry@sees.bangor.ac.uk

Abstract: An earlier article [25] discusses the proposition that the storage and processing of information in computers and in brains may often be understood as information compression. A subsequent article [15] criticises the computing aspects of [25] and research on the more specific conjecture that all forms of computing and formal reasoning may usefully be understood as information compression. The present article, which is intended to be intelligible without recourse to earlier articles, answers the main points in [15], tries to correct the many inaccuracies and misconceptions in that article, and discusses related issues. Topics which are discussed include: the way theories are or should be developed; the role of evidence in motivating research; apparent shortcomings in the Turing machine concept as a reason for seeking new principles of computing; the apparent conflict between the idea of ‘computing as compression’ and the fact that computers may create redundancy - and how the contradiction may be resolved; monotonicity and non-monotonicity of functions; information theory as a basis for ‘computing as compression’; computer models of a proposed ‘new generation’ computing system dedicated to information compression by pattern matching, unification and metrics-guided search (and how, within this framework, the effect of re-write rules may be imitated; how information may be transposed from one place to another; and how the effect of procedural programming may be achieved); computational complexity of information compression; the relationship of current proposals to research on inductive inference and algorithmic information theory.

DOI: 10.3233/AIC-1994-73-404

Journal: AI Communications, vol. 7, no. 3-4, pp. 203-219, 1994