A class of problems is called decidable if there is an algorithm which will give the answer to any problem of the class after a finite length of time. The purpose of this paper is to discuss the classes of problems that can be solved by infinitely long decision procedures in the following sense: An algorithm is given which, for any problem of the class, generates an infinitely long sequence of guesses. The problem will be said to be solved in (...) the limit if, after some finite point in the sequence, all the guesses are correct and the same. Functions, sets, and functionals which are decidable by such infinite algorithms will be calledlimiting recursive. These, together with classes of objects which can beidentified in the limit, are the subjects of this report.Without qualification,setwill mean set of numbers;functionwill mean number-theoretic function of 1 variable, possibly partial;functionalswill take numerical values and have any number of numerical and/or function variables, the latter ranging solely over total functions of 1 variable. Thus a function is a special case of a functional,xwill invariably stand for a numerical variable;φfor a function variable;gfor a guess ;nfor the numerical variable which indexes the guesses, referred to as thetime. (shrink)

Traditional analyses of the curve fitting problem maintain that the data do not indicate what form the fitted curve should take. Rather, this issue is said to be settled by prior probabilities, by simplicity, or by a background theory. In this paper, we describe a result due to Akaike [1973], which shows how the data can underwrite an inference concerning the curve's form based on an estimate of how predictively accurate it will be. We argue that this approach throws light (...) on the theoretical virtues of parsimoniousness, unification, and non ad hocness, on the dispute about Bayesianism, and on empiricism and scientific realism. * Both of us gratefully acknowledge support from the Graduate School at the University of Wisconsin-Madison, and NSF grant DIR-8822278 (M.F.) and NSF grant SBE-9212294 (E.S.). Special thanks go to A. W. F. Edwards.William Harper. Martin Leckey. Brian Skyrms, and especially Peter Turney for helpful comments on an earlier draft. (shrink)

The problem of induction reminds us that science cannot wait for empirical hypotheses to be verified and Duhem’s problem reminds us that we cannot expect full refutations either. We must settle for something less. The shape of this something less depends on which features of full verification and refutation we choose to emphasize. If we conceive of verification and refutation as arguments in which evidence entails the hypothesis or its negation, then the central problem of the philosophy of science is (...) to explicate a relation of confirmation or support that is weaker than full entailment but which serves, nonetheless, to justify empirical conclusions. (shrink)

The problem of theory choice and model selection is hard but still important when useful truths are underdetermined, perhaps not by all kinds of data but by the kinds of data we can have access to ethically or practicably—even if we have an infinity of such data. This article addresses a crucial instance of that problem: the problem of inferring causal structures from nonexperimental, nontemporal data without assuming the so-called causal Faithfulness condition or the like. A new account of epistemic (...) evaluation is developed to solve that problem and justify a standard practice of causal inference in data science. (shrink)

Ockham’s razor is the characteristic scientific penchant for simpler, more testable, and more unified theories. Glymour’s early work on confirmation theory eloquently stressed the rhetorical plausibility of Ockham’s razor in scientific arguments. His subsequent, seminal research on causal discovery still concerns methods with a strong bias toward simpler causal models, and it also comes with a story about reliability—the methods are guaranteed to converge to true causal structure in the limit. However, there is a familiar gap between convergent reliability and (...) scientific rhetoric: convergence in the long run is compatible with any conclusion in the short run. For that reason, Carnap suggested that the proper sense of reliability for scientific inference should lie somewhere between short-run reliability and mere convergence in the limit. One natural such concept is straightest possible convergence to the truth, where straightness is explicated in terms of minimizing reversals of opinion and cycles of opinion prior to convergence. We close the gap between scientific rhetoric and scientific reliability by showing that Ockham’s razor is necessary for cycle-optimal convergence to the truth, and that patiently waiting for information to resolve conflicts among simplest hypotheses is necessary for reversal-optimal convergence to the truth. (shrink)

A U-shaped curve in a cognitive-developmental trajectory refers to a three-step process: good performance followed by bad performance followed by good performance once again. U-shaped curves have been observed in a wide variety of cognitive-developmental and learning contexts. U-shaped learning seems to contradict the idea that learning is a monotonic, cumulative process and thus constitutes a challenge for competing theories of cognitive development and learning. U-shaped behavior in language learning (in particular in learning English past tense) has become a central (...) topic in the Cognitive Science debate about learning models. Antagonist models (e.g., connectionism versus nativism) are often judged on their ability of modeling or accounting for U-shaped behavior. The prior literature is mostly occupied with explaining how U-shaped behavior occurs. Instead, we are interested in the necessity of this kind of apparently inefficient strategy. We present and discuss a body of results in the abstract mathematical setting of (extensions of) Gold-style computational learning theory addressing a mathematically precise version of the following question: Are there learning tasks that require U-shaped behavior? All notions considered are learning in the limit from positive data. We present results about the necessity of U-shaped learning in classical models of learning as well as in models with bounds on the memory of the learner. The pattern emerges that, for parameterized, cognitively relevant learning criteria, beyond very few initial parameter values, U-shapes are necessary for full learning power! We discuss the possible relevance of the above results for the Cognitive Science debate about learning models as well as directions for future research. (shrink)

A Photcopy of Thinking Things Through, Princeton Univeresity Press, 1980.