Learnability Thesis Does Not Entail Church's Thesis

摘要

We consider the notion of intuitive learnability and its relation to intuitive computability. We briefly discuss the Church's Thesis. We formulate the Learnability Thesis. Further we analyse the proof of the Church's Thesis presented by M. Mostowski. We indicate which assumptions of the Mostowski's argument implicitly include that the Church's Thesis holds. The impossibility of this kind of argument is strengthened by showing that the Learnability Thesis does not imply the Church's Thesis. Specifically, we show a natural interpretation of intuitive computability under which intuitively learnable sets are exactly algorithmi-cally learnable but intuitively computable sets form a proper superset of recursive sets.