3 ms·
That is incorrect. The halting problem can be answered -- every Turing Machine either halts or does not halt on a given input. Undecidable only means that we
by betterunix2 8y ago
That is incorrect. The halting problem can be answered -- every Turing Machine either halts or does not halt on a given input. Undecidable only means that we cannot have a single algorithm that outputs the correct answer in every case.
- fspeech 8y agoThis is the first paragraph from the Wikipedia article on undecidable problems: “In computability theory and computational complexity theory, an undecidable problem is a decision problem for which it is proved to be impossible to construct an algorithm that always leads to a correct yes-or-no answer. The halting problem is an example: there is no algorithm that correctly determines whether arbitrary programs eventually halt when run.” https://en.m.wikipedia.org/wiki/Undecidable_problem https://en.m.wikipedia.org/wiki/Undecidable_problem