> No undecidable problem can ever be solved by a computer or computer program of any kind. In particular, there is no Turing machine to solve an undecidable problem.
This clearly not true. The halting problem can be solved for many problems from trivial to complicated.
For example, the busy beaver competitions show that the halting problem is routinely solved for thousands of Turing machines, some with extremely long and complicated running time.
Also all kinds of practical problems are routinely analyzed by static program analyzer. Many will point out halting problems to you.
What is probably meant, is that there is no Turing program that will work on any input.
> The halting problem can be solved for many problems from trivial to complicated.
The halting problem by definition takes an arbitrary program and input. Restrict either parameter and it is no longer "the halting problem". They define it this way in the article:
> The halting problem takes two inputs:
> an arbitrary program P
> P's input D
>The decision problem is: does P halt on input D?
That some programs can be easily shown to halt given certain inputs is also discussed in the article.
3 comments
[ 1.8 ms ] story [ 18.7 ms ] thread> No undecidable problem can ever be solved by a computer or computer program of any kind. In particular, there is no Turing machine to solve an undecidable problem.
This clearly not true. The halting problem can be solved for many problems from trivial to complicated.
For example, the busy beaver competitions show that the halting problem is routinely solved for thousands of Turing machines, some with extremely long and complicated running time.
Also all kinds of practical problems are routinely analyzed by static program analyzer. Many will point out halting problems to you.
What is probably meant, is that there is no Turing program that will work on any input.
It is true by definition: the word "undecidable" here means exactly that there is no algorithm to decide the problem.
The halting problem by definition takes an arbitrary program and input. Restrict either parameter and it is no longer "the halting problem". They define it this way in the article:
> The halting problem takes two inputs:
> an arbitrary program P
> P's input D
>The decision problem is: does P halt on input D?
That some programs can be easily shown to halt given certain inputs is also discussed in the article.