Consistent Polynomial Identification in the Limit Author: Werner Stein Source: Lecture Notes in Artificial Intelligence Vol. 1501, 1998, 424 - 438. Abstract. This paper aims to extend well known results about polynomial update-time bounded learning strategies in a recursion theoretic setting. We generalize the update-time complexity using the approach of Blum's computational complexity measures. It will turn out, that consistency is the first natural condition having a narrowing effect for arbitrary update boundaries. We show the existence of arbitrary hard, as well as an infinite chain of harder and harder consistent learnable sets. The complexity gap between consistent und inconsistent strategies solving the same problem can be arbitary large. We prove an exact characterization for polynomial consistent learnability, giving a deeper insight in the problem of hard consistent learnability. ©Copyright 1998 Springer