# decidability of artificial intelligence

Not sure whether this is the correct place to post the question. some of my terms might not accurate.

currently AI is used for classification, inference, and so forth, is AI problem decidable? for example, given a dataset, prior/constraints and neural network, whether it can recognize a pattern (properly accuracy greater than some lower bound) is decidable? I understood the decidable problem is searching in a finite space. In terms of Machine learning techniques, the parameter space is finite, can I say it is decidable?

Also, Many problem solved by machine learning is quite different with traditional problem which has an algorithm, but machine learning problem doesn't have an algorithm format. And therefore, it is undecidable

Finally, for many proved math theorem, let's say the bound in some constrained problems (ex: Shannon limit in communication). Can I say such problem (constrained problem exists bound) is decidable, since people could find an algorithm (or math formula) to define limits.

• Finite space between 0 and 5 is quite huge if we do not limit to integers. If one number is $\pi$ it complicates a bit. What decidable means to you? – Evil Sep 17 '16 at 19:56
• "is AI problem decidable?" -- What do you mean by "AI problem"? – David Richerby Sep 17 '16 at 21:16
• @Evil the decidable I mean giving a machine learning problem, for example, an image recognition by giving some dataset, whether it can reach some accuracy, is solvable; or there exists some knowledge upperbound for machine learning by giving dataset and prior/constraints, is solvable. The most naive way I can think is search all possibilities for parameters, but as you mentioned, the searching space is too huge – Sufeng Niu Sep 17 '16 at 21:28
• @DavidRicherby I mean some machine learning problem, for example, pattern recognition, inference, etc. These problem cannot be solved by traditional algorithm but rather the machine learning techniques – Sufeng Niu Sep 17 '16 at 21:31
• @SufengNiu The definition of decidability says nothing about "tradition". If there's an algorithm, it's decidable. – David Richerby Sep 17 '16 at 23:02