2
$\begingroup$

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.

Improve this question
$\endgroup$
5
  • $\begingroup$ 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? $\endgroup$
    – Evil
    Sep 17 '16 at 19:56
  • 3
    $\begingroup$ "is AI problem decidable?" -- What do you mean by "AI problem"? $\endgroup$
    – David Richerby
    Sep 17 '16 at 21:16
  • $\begingroup$ @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 $\endgroup$
    – Sufeng Niu
    Sep 17 '16 at 21:28
  • $\begingroup$ @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 $\endgroup$
    – Sufeng Niu
    Sep 17 '16 at 21:31
  • 2
    $\begingroup$ @SufengNiu The definition of decidability says nothing about "tradition". If there's an algorithm, it's decidable. $\endgroup$
    – David Richerby
    Sep 17 '16 at 23:02
2
$\begingroup$

For a problem to be approachable using what we presently call "AI methods", it has to be, at least theoretically, also solvable using "regular" methods (writing a set of instructions that solves it, line by line). Thus, decidable.

AI systems may create effective algorithms whose operation no human can understand. Also, by using AI methods we may find solutions to new problems, by accident, or discover that problems are decidable. These things do not contradict the affirmative above.

An algorithm exists that solves the problem.

Improve this answer
$\endgroup$
6
  • $\begingroup$ Thank you. also, @DavidRicherby The "regular"/"traditional" method I mentioned is that running on the Turing machine it gives definitely yes or no answer, while in machine learning, it let me feel quite different: the prediction may be right or wrong (based on prediction rates), which it might accept or reject. Do you think is this decidability still applicable on the machine learning? $\endgroup$
    – Sufeng Niu
    Sep 18 '16 at 1:24
  • $\begingroup$ If I may answer, you are getting some things mixed up here. First of all, Turing machines don't necessarily give yes/no answers, we define them that way because we want to, when this is the case. This distinction has to do with how the problem is defined, not with how the solution is given. The reason why we don't use machine learning to solve decision problems is because these are theoretical problems. You are confusing an algorithm that solves a problem itself with one that represents the solution of a theoretical problem. $\endgroup$
    – André Souza Lemos
    Sep 18 '16 at 2:15
  • $\begingroup$ Thank you. I see what you mean, just clarify: how to define the problem is the algorithm, right? if this is the true, I guess the machine learning problem (ex: Alpha go beat human) is not theoretical problems (ex: DFA equivalence). In this sense, machine learning problems should be undecidable. my confusion comes from that the machine learning learned from the training data rather than rule written by set of instructions, but regular algorithm is executed as formal way. Just wondering if this "how" differences affect the decidability? $\endgroup$
    – Sufeng Niu
    Sep 18 '16 at 3:47
  • 1
    $\begingroup$ It is not that these problems are "undecidable". It is that they are not decision problems, and there is nothing special about that. $\endgroup$
    – André Souza Lemos
    Sep 18 '16 at 5:45
  • 1
    $\begingroup$ Testing a move in a Go game, to see if it is the best possible move in that position, is a decision problem. One that is solvable, in principle. Alpha Go doesn't do that, because it is way too hard with our current knowledge and technology. $\endgroup$
    – André Souza Lemos
    Sep 18 '16 at 5:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.