David Bourget (Western Ontario)
David Chalmers (ANU, NYU)
Rafael De Clercq
Jack Alan Reynolds
Learn more about PhilPapers
Synthese 79 (3):515 - 542 (1989)
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.
|Keywords||No keywords specified (fix it)|
No categories specified
(categorize this paper)
Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
|Through your library|
References found in this work BETA
George Boolos, John Burgess, Richard P. & C. Jeffrey (2007). Computability and Logic. Cambridge University Press.
L. Laudan (1977). Progress and its Problems: Toward a Theory of Scientific Growth. University of California Press.
Larry Laudan (1984). Science and Values: The Aims of Science and Their Role in Scientific Debate. University of California Press.
Nelson Goodman (1972). Problems and Projects. Indianapolis,Bobbs-Merrill.
Michael R. Garey & David S. Johnson (1983). Computers and Intractability. A Guide to the Theory of NP-Completeness. Journal of Symbolic Logic 48 (2):498-500.
Citations of this work BETA
No citations found.
Similar books and articles
Bernhard Lauth (1995). Inductive Inference in the Limit of Empirically Adequate Theories. Journal of Philosophical Logic 24 (5):525 - 548.
Joke Meheus & Dagmar Provijn (2007). Abduction Through Semantic Tableaux Versus Abduction Through Goal-Directed Proofs. Theoria 22 (3):295-304.
Daniel Steel & S. Kedzie Hall (2010). A New Approach to Argument by Analogy: Extrapolation and Chain Graphs. Philosophy of Science 77 (5):1058-1069.
Brenda J. Latka (1994). Finitely Constrained Classes of Homogeneous Directed Graphs. Journal of Symbolic Logic 59 (1):124-139.
Peter Caws (1963). Science, Computers, and the Complexity of Nature. Philosophy of Science 30 (2):158-164.
Jiji Zhang & Peter Spirtes, A Transformational Characterization of Markov Equivalence for Directed Maximal Ancestral Graphs.
Miklos Ajtai & Ronald Fagin (1990). Reachability is Harder for Directed Than for Undirected Finite Graphs. Journal of Symbolic Logic 55 (1):113-150.
Added to index2009-01-28
Total downloads12 ( #200,924 of 1,725,833 )
Recent downloads (6 months)2 ( #268,271 of 1,725,833 )
How can I increase my downloads?