Abstract
The logic of scientific discovery is now a concern of computer scientists, as well as philosophers. In the computational approach to inductive inference, theories are treated as algorithms (computer programs), and the goal is to find the simplest algorithm that can generate the given data. Both computer scientists and philosophers want a measure of simplicity, such that simple theories are more likely to be true than complex theories. I attempt to provide such a measure here. I define a measure of simplicity for directed graphs, inspired by Herbert Simon's work. Many structures, including algorithms, can be naturally modelled by directed graphs. Furthermore, I adapt an argument of Simon's to show that simple directed graphs are more stable and more resistant to damage than complex directed graphs. Thus we have a reason for pursuing simplicity, other than purely economical reasons.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Angluin, D. C. and C. H. Smith: 1983, ‘Inductive Inference: Theory and Methods’,Computing Surveys 15, 237–69.
Ball, M. O.: 1980, ‘Complexity of Network Reliability Computations’,Networks 10, 153–65.
Blum, L. and M. Blum: 1975, ‘Toward a Mathematical Theory of Inductive Inference’,Information and Control 28, 125–55.
Boolos, G. S. and R. C. Jeffrey: 1980,Computability and Logic, Cambridge University Press, Cambridge.
Bunge, M.: 1963,The Myth of Simplicity, Prentice Hall, New Jersey.
Buzacott, J. A.: 1980, ‘A Recursive Algorithm for Finding Reliability Measures Related to the Connection of Nodes in a Graph’,Networks 10, 311–27.
Dawkins, R.: 1976, ‘Hierarchical Organization, a Candidate Principle for Ethology’, in P. P. G. Bateson and R. A. Hinde (eds.),Growing Points in Ethology, Cambridge University Press, Cambridge, pp. 7–54.
Frank, H., R. E. Kahn, and L. Kleinrock: 1972, ‘Computer Communication Network Design — Experience with Theory and Practice’,AFIPS Conference Proceedings 40, 255–70.
Garey, M. R. and D. S. Johnson: 1979,Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman and Co., New York.
Goodman, N.: 1972,Problems and Projects, Bobbs-Merrill Co., Inc., New York.
Kelmans, A. K.: 1972, ‘Connectivity of Graphs Having Vertices which Drop Out Randomly’,Automation and Remote Control 33, 613–20.
Kelmans, A. K.: 1976, ‘Comparison of Graphs by their Number of Spanning Trees’,Discrete Mathematics 16, 241–61.
Laudan, L.: 1977,Progress and Its Problems, University of California Press, Berkeley.
Laudan, L.: 1984,Science and Values, University of California Press, Berkeley.
Putnam, H.: 1975, ‘Probability and Confirmation’, inMathematics, Matter and Method, Cambridge University Press, Cambridge, England.
Simon, H. A.: 1962, ‘The Architecture of Complexity’,Proceedings of the American Philosophical Society 106, 467–82.
Sober, E.: 1975,Simplicity, Clarendon Press, Oxford.
Solomonoff, R. J.: 1964, ‘A Formal Theory of Inductive Inference’,Information and Control 7, 1–22, 224–54.
Thom, R.: 1975,Structural Stability and Morphogenesis: An Outline of a General Theory of Models, Translated by D. H. Fowler, Benjamin/Cummings Publishing, Massachusetts.
Valiant, L. G.: 1979, ‘The Complexity of Enumeration and Reliability Problems’,SIAM Journal of Computing 8, 410–21.
van Fraassen, B. C.: 1980,The Scientific Image, Clarendon Press, Oxford.
Author information
Authors and Affiliations
Additional information
This paper is based on part of my doctoral dissertation. Thanks to my thesis supervisor Professor Alasdair Urquhart for his encouragement, constructive criticism, and for directing me to several relevant articles; to my advisor, Professor Ian Hacking, for reminding me to concentrate on results that might have some application in the real world; to Professor Eric Mendelsohn for checking my use of graph theory; and to my friend Wendy Brandts for sharing her ideas on a closely related problem.
Thanks to my friends and family (the latter being a (proper) subset of the former, and both including Dr. Louise Linney, of course) for ongoing support in my scholastic endeavors.
Thanks to the Social Sciences and Humanities Research Council for financial assistance. (Awards 452-86-5885 and 453-87-0513.) Thanks to the University of Toronto for financial assistance.
Rights and permissions
About this article
Cite this article
Turney, P. The architecture of complexity: A new blueprint. Synthese 79, 515–542 (1989). https://doi.org/10.1007/BF00869285
Issue Date:
DOI: https://doi.org/10.1007/BF00869285