8
$\begingroup$

Perhaps a way to better understand the Halting Problem's importance is to know what would happen or what could be possible if this was solved.

What would be the Halting Problem's implications in today's technology, mathematics and its practical applications, if it was somehow solved?

Improve this question
$\endgroup$
4
  • 9
    $\begingroup$ If the halting problem were decidable, then 1 + 1 = 3, which would cause all sorts of problems. $\endgroup$
    – Rick Decker
    Commented Dec 6, 2014 at 0:09
  • $\begingroup$ As @RickDecker points out, it's strange to ask people working in mathematics or computer science what the consequences of a logical inconsistency would be. This sounds more like a question for the philosophers. As we understand the world as it is, the occurrence of a logical inconsistency is impossible and/or meaningless. It is a logical fact that the Halting problem is not "solvable" (by a turing machine). $\endgroup$
    – cody
    Commented Dec 6, 2014 at 0:34
  • $\begingroup$ related: cs.stackexchange.com/questions/28599/… $\endgroup$
    – Ran G.
    Commented Dec 6, 2014 at 2:00
  • 1
    $\begingroup$ This question appears to be off-topic because it is about what would happen in a provably counterfactual situation. $\endgroup$
    – David Richerby
    Commented Dec 6, 2014 at 8:41

1 Answer 1

Reset to default
8
$\begingroup$

Maybe I should make a more serious answer. First off: the unsolvability of the halting problem by "conventional" computing methods is a logical theorem. It is very simple to prove, and can be proven in almost any reasonable logical framework (that can express the problem).

There are however two questions we can reasonably ask:

  1. What are the mathematical consequences of having a halting oracle? A halting oracle can be imagined as a genie (instantly) giving us the answer to any halting problem we ask of it. This is a rather well studied subject in computability theory and the "world" in which you have access to such a genie is called the first turing degree.

    An interesting observation is that even given such an oracle, we can ask computational problems for which we cannot compute the answer, such as "does the turing machine $M$ with access to the halting oracle halt on all inputs"? The proof is almost identical to the original proof of undecidability of the halting problem!

  2. What would happen if we could solve all halting problems that come up "in practice"? This isn't really a mathematical question, since you would need to define in practice but it's a really interesting scientific question. The whole field of termination analysis tries to find such algorithms. It works surprisingly well: if you write a reasonable program to compute some quantity, odds are that there is a tool in this list that can handle it.

    It's not too hard to find examples that break these tools though: even a program as simple as the $3n+1$ algorithm would choke them, since there it is not known whether it halts on all inputs. A lot of similar open problems in number theory (the twin primes conjecture, the existence of odd perfect numbers) can be expressed as a halting problem, which suggests that there are many such problems that can't be handled by any "reasonable" automated termination tool.

Improve this answer
$\endgroup$
4
  • 4
    $\begingroup$ Your last paragraph hints at something OP may find interesting. A consequence of solving the halting problem would be that we'd immediately get answers to all mathematical theorems about existence of any finitely describable objects, such as this 3n+1 conjecture - because you can just write a program to generate them until the object of interest is found, and check if the program halts. $\endgroup$
    – jkff
    Commented Dec 6, 2014 at 5:28
  • $\begingroup$ The last paragraph contains a fallacy. While it is true that if we could solve the halting problem we could solve these number theoretic questions (i.e. 3n+1 reduces to Halting) but that does not mean that there is no algorithm deciding 3n+1 (that would be the reduction in the other direction). In fact, 3n+1 is either true or false, admitting trivial algorithms. See also here. $\endgroup$
    – Raphael
    Commented Dec 6, 2014 at 8:58
  • 1
    $\begingroup$ The last paragraph refers to practical termination algorithms (hence the qualifier "reasonable"). Given the difficulty of "3n+1-like" problems, it's likely there isn't a practical automated termination algorithm within current reach that could solve a large class of such problems. A generalization of this problem is undecidable as well. $\endgroup$
    – cody
    Commented Dec 8, 2014 at 15:39
  • $\begingroup$ Also, no mention is made of "truth" in the last paragraph. I'm not sure what truth is at any rate :) $\endgroup$
    – cody
    Commented Dec 8, 2014 at 15:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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