PAC-learning is Undecidable

arXiv.org Machine Learning

The problem of attempting to learn the mapping between data and labels is the crux of any machine learning task. It is, therefore, of interest to the machine learning community on practical as well as theoretical counts to consider the existence of a test or criterion for deciding the feasibility of attempting to learn. We investigate the existence of such a criterion in the setting of PAC-learning, basing the feasibility solely on whether the mapping to be learnt lends itself to approximation by a given class of hypothesis functions. We show that no such criterion exists, exposing a fundamental limitation in the decidability of learning. In other words, we prove that testing for PAC-learnability is undecidable in the Turing sense. We also briefly discuss some of the probable implications of this result to the current practice of machine learning.


The Church-Turing Thesis

Communications of the ACM

Chapter in New Computational Paradigms: Changing Conceptions of What Is Computable, S.B. Cooper, B. Lowe, and A. Sorbi, Eds.


Beyond Turing Machines

arXiv.org Artificial Intelligence

This paper discusses "computational" systems capable of "computing" functions not computable by predefined Turing machines if the systems are not isolated from their environment. Roughly speaking, these systems can change their finite descriptions by interacting with their environment.


Non-computability of human intelligence

arXiv.org Artificial Intelligence

Question 1. Can human intelligence be completely modelled by a Turing machine? To give away the ending we show here that the answer is no. More specifically we show that at least some thought processes of the brain cannot be Turing computable. In particular some physical processes are not Turing computable, which is not entirely expected. The main difference of our argument with the well known Lucas-Penrose argument is that we do not use Gödel's incompleteness theorem, (although our argument seems related to Gödel's) and we do not need to assume fundamental consistency of human reasoning powers, (which is controversial) we also sidestep some meta-logical issues with their argument, which have also been controversial. The argument is via a thought experiment and at least partly physical, but no serious physical assumptions are made. Furthermore the argument can be reformed as an actual (likely future) experiment. We will give a complete definition of a Turing machine after the introduction.


Problem Theory

arXiv.org Artificial Intelligence

The Turing machine, as it was presented by Turing himself, models the calculations done by a person. This means that we can compute whatever any Turing machine can compute, and therefore we are Turing complete. The question addressed here is why, Why are we Turing complete? Being Turing complete also means that somehow our brain implements the function that a universal Turing machine implements. The point is that evolution achieved Turing completeness, and then the explanation should be evolutionary, but our explanation is mathematical. The trick is to introduce a mathematical theory of problems, under the basic assumption that solving more problems provides more survival opportunities. So we build a problem theory by fusing set and computing theories. Then we construct a series of resolvers, where each resolver is defined by its computing capacity, that exhibits the following property: all problems solved by a resolver are also solved by the next resolver in the series if certain condition is satisfied. The last of the conditions is to be Turing complete. This series defines a resolvers hierarchy that could be seen as a framework for the evolution of cognition. Then the answer to our question would be: to solve most problems. By the way, the problem theory defines adaptation, perception, and learning, and it shows that there are just three ways to resolve any problem: routine, trial, and analogy. And, most importantly, this theory demonstrates how problems can be used to found mathematics and computing on biology.