On the power of probabilistic strategies in inductive inference (Q760795)

The paper deals with probabilistic algorithms for inductive inference of programs solely from input/output examples. Let \(LIM_ n\) denote the family of all classes of recursive functions U limit identifiable with n changes of hypotheses in the following sense: there exists a deterministic Turing machine with input tape and output tape such that for every function \(f\in U\), starting the computation when exactly all the values f(0), f(1), f(2),... are written on the input tape in natural order, the machine never stops and on the output tape it writes a nonempty, finite sequence of at most \(n+1\) numbers, the last one of which being an f-program, i.e. an index of f in an acceptable Gödel numbering of partial recursive functions. For p \((1/2\leq p<1)\) let \(p\)-LIM\({}_ n\) denote the family of all classes U such that, with probability p, U is limit identifiable (by some probabilistic Turing machine) with n changes of hypotheses. It is proved that \(\cup_{n\in N}1/2-LIM_ n=\cup_{n\in N}LIM_ n\). However if the number of changes of hypotheses is a priori bounded then probabilistic identification strategies are more powerful than deterministic ones. Namely, it is shown that: (1) for every \(n\geq 2\) there is a class U such that U is in \((1- \epsilon)-LIM_ n\) for every \(\epsilon >0\), but \(U\not\in LIM_ n\); (2) for every \(n\geq 0\) and every p \((1/2\leq p<1)\), \(LIM_{\det (n,p)}\subseteq p-LIM_ n\), where \(\det (n,p)=\max \{k:\) \(k\leq ((n+1)/(p+\epsilon))-1\) for some \(\epsilon >0\}\); (3) for every \(n\geq 0\), \(LIM_{2n}\subset 1/2-LIM_ n\subset LIM_{8n+2}\). This last result shows both the strength and the weakness of probabilistic strategies with a priori bounded number of changes of hypotheses.