PROBLEMS WITH COMPLEXITY IN GOLD'S PARADIGM OF INDUCTION Part I: Dynamic Complexity
Peter D. Turney · International Journal of General Systems · 1990
In 1967, the computer scientist E. M. Gold published an article on inductive inference, which founded a new paradigm for the study of induction. This approach to induction has since become known as “Gold's Paradigm”. The purpose of this paper is to introduce Gold's paradigm to a broad audience, and to raise a problem with the paradigm, a problem which has largely been ignored by computer scientists. In particular, which complexity measures are suitable for inductive inference in Gold'ls paradigm? This paper is the first of two papers on this topic. The paper begins with an introduction to Gold'ls paradigm. It then introduces Blum's axioms for dynamic complexity measures. It is argued that further progress in Gold's paradigm requires strengthening Blum's axioms. As they stand, Blum's axioms allow measures which are not suitable for inductive inference. The second paper deals with static complexity measures.