2
$\begingroup$

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... *

$\endgroup$
6
$\begingroup$

While trans-Turing computation could in theory (that is, to the best of my knowledge) occur in the physical world, there is currently no reason (again, in my understanding) to believe that it does, so there is no way to really solve an undecidable problem. In particular, all the notions of "hypercomputation" kicking around out there invoke something beyond the reach of current technology, to put it mildly: either computations which run for transfinitely long, or complicated arrangements of black holes (which are really just to facilitate said transfinite computations), or similar.

So insofar as you're asking whether we can in practice solve Turing-undecidable problems, the answer is no. (And things like neural networks, genetic algorithms, etc. - even theoretical quantum computers! - are all no stronger than Turing machines in terms of what they can compute.)

The more interesting aspect of your question is about what happens when we don't demand exactly that the problem in question be solved. The correct thing to say here is:

There are "degrees" of unsolvability; in many ways, saying that a problem is "unsolvable" isn't by any means the end of the story.

The phrase "degrees of unsolvability" can be interpreted as referring to specifically the Turing degrees, but here I mean it more broadly. However, the Turing degree of a problem is indeed one extremely important measure of its undecidability, so let's start there:

$A\le_T B$ if there is an algorithm for deciding $A$ given access to an "oracle" for $B$.

The equivalence classes under "$\equiv_T$" (where $A\equiv_TB$ iff $A\le_TB$ and $B\le_TA$) are called Turing degrees, and there are quite a lot of them with wildly different properties. One important aspect of the Turing degrees is the Turing jump; this is an operation which takes in a (possibly undecidable) problem $A$, and spits out the "halting problem relative to $A$" (denoted $A'$). For example, $\emptyset'$ is just the usual halting problem, and $\emptyset''$ turns out to be $\equiv_T$ the problem of deciding whether a given Turing machine will ever halt on any input. Incidentally, the jump is degree invariant: if $A\equiv_T B$ then $A'\equiv_TB'$ (the converse, however, fails). So we also can talk about the jump of a Turing degree. Iteratively applying the jump to $\emptyset$ (or equivalently the degree of the computable sets) yields the arithmetic hierarchy: a problem $A$ is arithmetic if it is $\le_T0^{(n)}$ for some $n$ (where "$A^{(n)}$" denotes the result of applying the jump to $A$ $n$-many times).

Now we get to a direct connection with your question:

Complexity in the arithmetic hierarchy is related to the kind of "algorithmic approximability" of a problem.

The nicest instance of this is Shoenfield's limit lemma; this states that the following are equivalent (actually it says a bit more but whatever):

  • $A\le_T0'$.

  • There is a computable function $f(x, y)$ of two variables, such that for every $a\in\mathbb{N}$ the limit $\lim_{y\rightarrow \infty}f(a, y)$ exists (that is, it's eventually constant) and equals $A(a)$.

So the sets which are Turing reducible to the halting problem are exactly those which can be "limit computed."

However:

The sense(s) in which a problem is "algorithmically approximable" relies on more than just its Turing degree, and certainly more than just whether it is $\le_T0'$ or not.

For example, a computably enumerable (c.e.) set is one which is the domain of a partial computable function (equivalently, is either empty or the range of a total computable function). C.e. sets are all $\le_T0'$ (this is an easy exercise), so they are limit computable, but in fact they are limit computable in a very nice way: via a computable $f$ which is nondecreasing: if $f(x, y)=1$ then $f(x, z)=1$ for all $z>y$. That is, we can approximate c.e. sets "from below." And this is an exact characterization of them. The complement of a c.e. set, meanwhile, is approximable "from above" - that is, via an $f$ satisfying "if $f(x, y)=0$ then $f(x, z)=0$ for all $z>y$." If a set is approximable both from below and above, it's computable, so since there are noncomputable c.e. sets (like the halting problem itself!) the notion "approximable from below" (resp. above) is not degree-invariant (since a set is always $\equiv_T$ its complement; why?).

Continuing past this we might want to talk about sets which are approximable by a function which "only changes its mind rarely" - e.g. maybe we require that for each $n$, the function $y\mapsto f(n, y)$ only change values at most three times as $y\rightarrow\infty$. This leads to the Ershov hierarchy, which refines the $0'$-computable sets in terms of their limit computability.

And this is all just barely scraping the surface. There are many, many more kinds of "algorithmic approximability" notions out there; you should pick up a good book on computability theory, maybe Downey/Hirschfeldt, to find out more about this.

I'll end by just mentioning one last direction: general-case complexity. It often happens that we have an algorithm with terrible worst-case runtime, but which runs in practice quite efficiently; or we have an algorithm which runs quickly but isn't always correct, but in practice is correct most of the time. And we can have analogies of this for undecidability too. There are many notions of a problem being tractable/solvable in the "general case;" the two most prominent, in my understanding, are generic computability and coarse computability.

| cite | improve this answer | |
$\endgroup$

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.