Definitions

induction, problem of

Problem of justifying the inductive inference from the observed to the unobserved. It was given its classic formulation by David Hume, who noted that such inferences typically rely on the assumption that the future will resemble the past, or on the assumption that events of a certain type are necessarily connected, via a relation of causation, to events of another type. (1) If we were asked why we believe that the sun will rise tomorrow, we would say that in the past the Earth turned on its axis every 24 hours (more or less), and that there is a uniformity in nature that guarantees that such events always happen in the same way. But how do we know that nature is uniform in this sense? We might answer that, in the past, nature has always exhibited this kind of uniformity, and so it will continue to be uniform in the future. But this inference is justified only if we assume that the future must resemble the past. How do we justify this assumption? We might say that in the past, the future turned out to resemble the past, and so in the future, the future will again turn out to resemble the past. The inference is obviously circular: it succeeds only by tacitly assuming what it sets out to prove, namely that the future will resemble the past. (2) If we are asked why we believe we will feel heat when we approach a fire, we would say that fire causes heat—i.e., there is a “necessary connection” between fire and heat, such that whenever one occurs, the other must follow. But, Hume asks, what is this “necessary connection”? Do we observe it when we see the fire or feel the heat? If not, what evidence do we have that it exists? All we have is our observation, in the past, of a “constant conjunction” of instances of fire being followed by instances of heat. This observation does not show that, in the future, instances of fire will continue to be followed by instances of heat; to say that it does is to assume that the future must resemble the past. But if our observation is consistent with the possibility that fire may not be followed by heat in the future, then it cannot show that there is a necessary connection between the two that makes heat follow fire whenever fire occurs. Thus we are not justified in believing that (1) the sun will rise tomorrow or that (2) we will feel heat when we approach a fire. It is important to note that Hume did not deny that he or anyone else formed beliefs about the future on the basis of induction; he denied only that we could know with certainty that these beliefs are true. Philosophers have responded to the problem of induction in a variety of ways, though none has gained wide acceptance.

Method of raising the temperature of an electrically conductive material by subjecting it to an alternating electromagnetic field. Energy in the electric currents induced in the object is dissipated as heat. Induction heating is used in metalworking to heat metals for soldering, tempering, and annealing, and in induction furnaces for melting and processing metals. The principle of the induction-heating process resembles that of the transformer. A water-cooled coil (inductor), acting as the primary winding of a transformer, surrounds the material to be heated (the workpiece), which acts as the secondary winding. Alternating current flowing in the primary coil induces eddy currents in the workpiece, causing it to become heated. The depth to which the eddy currents penetrate, and therefore the distribution of heat within the object, depend on the frequency of the primary alternating current and the magnetic permeability, as well as the resistivity, of the material.

In logic, a type of nonvalid inference or argument in which the premises provide some reason for believing that the conclusion is true. Typical forms of inductive argument include reasoning from a part to a whole, from the particular to the general, and from a sample to an entire population. Induction is traditionally contrasted with deduction. Many of the problems of inductive logic, including what is known as the problem of induction, have been treated in studies of the methodology of the natural sciences. Seealso John Stuart Mill; philosophy of science; scientific method.

Modification in the distribution of electric charge on one material under the influence of an electric charge on a nearby object. It occurs whenever any object is placed in an electric field. When a negatively charged object is brought near a neutral object, it induces a positive charge on the near side of the object and a negative charge on the far side. If the negative side of the original object is momentarily grounded, the negative charge may escape, so that the object becomes positively charged by induction.

Around 1960, Ray Solomonoff founded the theory of universal inductive inference, the theory of prediction based on observations; for example, predicting the next symbol based upon a given series of symbols. Solomonoff's theory attempts to be mathematically rigorous.

Fundamental ingredients of the theory are the concepts of algorithmic probability and Kolmogorov complexity. The universal prior probability of any prefix p of a computable sequence x is the sum of the probabilities of all programs (for a universal computer) that compute something starting with p. Given some p and any computable but unknown probability distribution from which x is sampled, the universal prior and Bayes' theorem can be used to predict the yet unseen parts of x in optimal fashion.

Another direction of inductive inference is based on E. Mark Gold's model of learning in the limit from 1967 and has developed since then more and more models of learning. The general scenario is the following: Given a class S of computable functions, is there a learner (that is, recursive functional) which outputs for any input of the form (f(0),f(1),...,f(n)) a hypothesis. A learner M learns a function f if almost all hypotheses are the same index e of f with respect to a previously agreed on acceptable numbering of all computable functions; M learns S if M learns every f in S. Basic results are that all recursively enumerable classes of functions are learnable while the class REC of all computable functions is not learnable. Many related models have been considered and also the learning of classes of recursively enumerable sets from positive data is a topic studied from Gold's pioneering paper in 1967 onwards. A far reaching extension of the Gold’s approach is developed by Burgin theory of inductive Turing machines, which are kinds of super-recursive algorithms.

References

• Angluin, D., and Smith, C. H. (1983) Inductive Inference: Theory and Methods, Comput. Surveys, v. 15, no. 3, pp. 237—269
• Mark Burgin (2005), Super-recursive algorithms, Monographs in computer science, Springer. ISBN 0387955690
• Burgin, M. and Klinger, A. Experience, Generations, and Limits in Machine Learning, Theoretical Computer Science, v. 317, No. 1/3, 2004, pp. 71-91
• Gasarch, W. and Smith, C. H. (1997) A survey of inductive inference with an emphasis on queries. Complexity, logic, and recursion theory, Lecture Notes in Pure and Appl. Math., 187, Dekker, New York, pp. 225-260
• Ming Li and Paul Vitanyi, An Introduction to Kolmogorov Complexity and Its Applications, 2nd Edition, Springer Verlag, 1997.
• Ray Solomonoff "Two Kinds of Probabilistic Induction," The Computer Journal, Vol. 42, No. 4, 1999
• Ray Solomonoff "A Formal Theory of Inductive Inference, Part I" Information and Control, Part I: Vol 7, No. 1, pp. 1-22, March 1964
• Ray Solomonoff "A Formal Theory of Inductive Inference, Part II" Information and Control, Part II: Vol. 7, No. 2, pp. 224-254, June 1964