6
$\begingroup$

What does it mean that some problem is undecidable?

For instance the halting problem.

Does it mean that humans can never invent a new technique that always decides whether a turing machine will halt?

If not, what techniques are allowed such that halting problem is still undecidable?

For instance induction is a good technique, why cant one discover some new technique?

I have trouble understanding how some new invention cannot solve the halting problem.

Given some computer and a program, is there really insufficient information stored in it to determine if it will halt?

It seems like a purely mechanical problem

$\endgroup$

closed as off topic by arnab, Dave Clarke Apr 7 '11 at 9:52

Questions on Theoretical Computer Science Stack Exchange are expected to relate to research-level theoretical computer science within the scope defined by the community. Consider editing the question or leaving comments for improvement if you believe the question can be reworded to fit within the scope. Read more about reopening questions here. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 8
    $\begingroup$ This is not a research level theoretical computer science question. $\endgroup$ – Dave Clarke Apr 7 '11 at 9:54
  • 2
    $\begingroup$ @Dave The research part is what techniques we should do research for to solve the halting problem which is the fundemantal problem of all theoretical computer science $\endgroup$ – user4580 Apr 7 '11 at 10:03
  • 11
    $\begingroup$ Your statements show a fundamental lack of understanding of undecidability and the halting problem. This is why it is not a research level question. $\endgroup$ – Dave Clarke Apr 7 '11 at 10:06
  • $\begingroup$ The answer is very simple: it is possible to build a program to solve halting problem but it is known that it will be not total; it is proven that it is impossible to decide halting of given algorithm on given input in fixed amount of time. In other words, for any time T there is always be algorithms and inputs such that our decider will exceed T while deciding their halting. $\endgroup$ – Vag May 25 '11 at 8:13