On the Learnability of the Uncomputable

Abstract

Within Valiant's model of learning as formalized by Kearns, we show that computable total predicates for two formally uncomputable problems (the classical Halting Problem, and the Halting Problem relative to a specified oracle) are formally learnable from examples, to arbitrarily high accuracy with arbitrarily high confidence, under any probability distribution. The Halting Problem relative to the oracle is learnable in time polynomial in the measures of accuracy, confidence, and the length of the learned predicate. The classical Halting Problem is learnable in expected time polynomial in the measures of accuracy, confidence, and the (1 0 ffl=16) th percentile length and run-time of programs which do halt on their inputs (these quantities are always finite). Equivalently, the mean length and run-time may be substituted for the percentile values in the time complexity statement. The proofs are constructive. While the problems are learnable, they are not polynomial...