[Solved]: If the Halting Problem was solvable, and we solved it, what would be its implications?

Problem Detail: 

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?

Would we have time travel? Access to the Force? Mutants?

Asked By : Mark Gabriel

Answered By : cody

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/33908

 Ask a Question

 Download Related Notes/Documents