Search results for "inductive inference"

On speeding up synthesis and prediction of functions

1974

Computational complexity of prediction strategies

1977

The value f(m+1) is predicted from given f(1), ..., f(m). For every enumeration T(n, x) there is a strategy that predicts the n-th function of T making no more than log2(n) errors (Barzdins-Freivalds). It is proved in the paper that such "optimal" strategies require 2^2^cm time to compute the m-th prediction (^ stands for expoentiation).

Towards a theory of inductive inference

1973

Prediction of the next value of a function

1981

The following model of inductive inference is considered. Arbitrary set tau = {tau_1, tau_2, ..., tau_n} of n total functions N->N is fixed. A "black box" outputs the values f(0), f(1), ..., f(m), ... of some function f from the set tau. Processing these values by some algorithm (a strategy) we try to predict f(m+1) from f(0), f(1), ..., f(m). Upper and lower bounds for average error numbers are obtained for prediction by using deterministic and probabilistic strategies.