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

Improve this question
$\endgroup$
4
  • 9
    $\begingroup$ This is not a research level theoretical computer science question. $\endgroup$
    – Dave Clarke
    Commented Apr 7, 2011 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
    Commented Apr 7, 2011 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
    Commented Apr 7, 2011 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
    Commented May 25, 2011 at 8:13

0

Reset to default