31 March 2015, Logic Tea, Michal Tomasz Godziszewski

Abstract

We consider the notion of intuitive learnability and its relation to intuitive computability. We briefly present and discuss the Church's Thesis in the first section. A set is intuitively learnable if there is a (possibly infinite) intuitive procedure that for each input produces a finite sequence of yeses and nos such that the last answer in the sequence is correct. In the second section we formulate the Learnability Thesis which states that the notion of intuitive learnability is equivalent to the notion of algorithmic learnability. Our claim is analogous to the Church's Thesis. Further, in the third section, we analyse the “proof” of the Church's Thesis presented by Mostowski. The “proof” goes in unusual lines – by giving a model of the world, namely F M (N ), separating knowable (intuitively computable) sets from FM-representable (algorithmically learnable) ones and showing that knowable sets are exactly recursive. We indicate which assumptions of the Mostowski's argument implicitly include that Church's Thesis holds. The impossibility of this kind of argument is strengthened in the fourth section 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.

For more information, please visit the website http://www.illc.uva.nl/logic_tea/ or contact Thomas Brochhagen (t.s.brochhagen at uva.nl), Johannes Marti (johannes.marti at gmail.com), Masa Mocnik (masa.mocnik at gmail.com) or Julian Schloder (julian.schloeder at gmail.com).