Re: Halting Problem: What Constitutes Pathological Input

On 2025-05-07 16:17:09 +0000, Mr Flibble said:

On Wed, 07 May 2025 11:35:07 +0100, Richard Heathfield wrote:
 

On 07/05/2025 11:26, Fred. Zwarts wrote:

Op 07.mei.2025 om 03:39 schreef olcott:

 <snip>
 

There must be an algorithm having a specified sequence of steps that
are applied to the input to derive the output.
 

Your 'must' has no basis.

 Not only that, but he is literally begging the question - i.e. assuming
as true that which he hopes to prove. "All questions must be decidable,
therefore all questions are decidable."
 Turing assumed the same thing: "All questions are decidable." But he
went on to demonstrate that if the assumption is true, it must be false
- a patent absurdity that shows that his original assumption was false.

 Wrong. All *well-formed* questions are decidable; the question the halting
problem asks is not *well-formed*; if is *ill-formed* as it is predicated
on a category (type) error.

There are well-formed questions that are undecidable. For example, we
may ask whether a Truing machine that has no rules halts. The question
is well formed and the answer is that it does. We may also ask whether
the one state Turing machine that has one rule 'in the start state if
the symbol under the head is 1 change it to 2 and move the head to right
and continue in the start state' halts if the input string is 12. The
question is well-formed and the answer is that it does.
Questions about more complex Turing machines and longer inputs are
equally well-formed although harder to answer. But for every pair of
a Turing machine and an input there is a correct answer. That the
answer is hard to find does not make the question ill-defined. For
some Turing machines it is so hard to find whether they halt that
nobody knows. Even that does not make the question ill-defined but
may make it a research project.
That you say "category (type) error" without pointint to any indicates
that you are bluffing.
--
Mikko