@InProceedings{10.1007/978-3-319-08019-2_12,
author="Czarnecki, Marek 
and Godziszewski, Micha{\l} Tomasz
and Kaloci\'nski, Dariusz",
editor="Beckmann, Arnold
and Csuhaj-Varj{\'u}, Erzs{\'e}bet
and Meer, Klaus",
title="Learnability Thesis Does Not Entail Church's Thesis",
booktitle="Language, Life, Limits",
year="2014",
publisher="Springer International Publishing",
address="Cham",
pages="113--122",
abstract="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 algorithmically learnable but intuitively computable sets form a proper superset of recursive sets.",
isbn="978-3-319-08019-2"
}