Wikipedia in https://en.wikipedia.org/wiki/Undecidable_problem defines
undecidable problem is a decision problem for which it is known to be impossible to construct a single algorithm that always leads to a correct yes-or-no answer
This definition of undecidability is quite strong and it gives impressions that still there can be some kind of solutions of undecidable problems. E.g.:
- definition requires that algorithmic solution should exist. But is it possible some problem to have non-algorithmic solutions? E.g. computer science is about algorithms, but mathematics if far more general. Maybe there can be non-algorithmic means to solve undecidable problems? This definition of undecidability is so strongly connected with the computation that is hard to believe that computation can determine the foundations of math. Maybe heuristic (algorithmically non deterministic approach) methods like neural networks or genetic algorithms can be such "unalgorithmic" means?
- definition requires that the solution should be always correct. But maybe there can exist algorithmic solutions or nonalgorithmic means that gives approximate but arbitrarily close answer to the problem, answer that is good enough in some kind of metrics? In practice that should be good solution.
So - my question is this: does undecidability determines complete unsolvability of the problem (i.e. from this strong definition of the undecidability follows this complete unsolvability of the problem) or does undecidability definition is indeed about computation only and it allows to find solution by unalgorithmic means or to find approximate solutions?
Approximate reasoning is branch of mathematics - maybe approximate reasoning can be practical solution for the undecidable problems? This is reference request - research about approximate reasoning methods for the solution of undecidable problems.
*Some data added to question:
- There is example about approximate approach: http://ieeexplore.ieee.org/document/7809557/ "Automatic test data generation for path coverage is an undecidable problem and genetic algorithm (GA) has been used as one good solution."
- There is article http://www.sciencedirect.com/science/article/pii/S0304397507003192 about "In particular, the third class deals with non-recursive solutions of undecidable problems. The approach is illustrated by solutions of some intractable and undecidable problems."
- There is another article https://www.igi-global.com/chapter/foundations-evolutionary-computation/19652 "Here we show how to achieve the same results, i.e., to find exact solutions for hard problem, in a finite number of steps (time). Namely, we can use super-recursive algorithms. They allow one to solve many problems undecidable in the realm of recursive algorithms (Burgin, 2005). We argue that it is beneficial for computer science to go beyond recursive algorithms, making possible to look for exact solutions of intractable problems or even to find solutions of undecidable problems, whereas recursive solutions do not exist. As the basic computational model, we take evolutionary automata, which extend computational power of evolutionary Turing machines introduced in (Eberbach, 2005) and parallel evolutionary Turing machines introduced in (Burgin&Eberbach, 2008). "
- Another one http://www.sciencedirect.com/science/article/pii/S0303264705000699 "We show that an Evolutionary Turing Machine is able to solve nonalgorithmically the halting problem of the Universal Turing Machine and, asymptotically, the best evolutionary algorithm problem. In other words, the best evolutionary algorithm does not exist, but it can be potentially indefinitely approximated using evolutionary techniques."
I don't know what to think about all of this... *