Re: Proof by contradiction? HP solved. [ pathology removed ]

[olcott]

On 7/18/2021 8:35 AM, Ben Bacarisse wrote:
> Mr Flibble <fli...@reddwarf.jmc> writes:
>
>> Proof by contradiction and contradiction are not the same thing; just
>> because there is a contradiction is doesn't necessarily follow that a
>> proof can be based on it.
>
> The halting theorem is much better proved directly. Such proofs
> establish that
>
> For all n, f(n) =/= halts.
>
> Here, f(n) is the function computed by TM number n, and halts is the
> mathematical function from N x N to {true, false} with halts(m, n) true
> if, and only if, TM number m halts on input n.
>

Pathological Input to a halt decider is defined as any input that was
defined to do the opposite of whatever its corresponding halt decider
decides.

This question can only be correctly answered after the pathology has
been removed.

When a halt decider only acts as a pure simulator of its input until
after its halt status decision is made there is no feedback loop of back
channel communication between the halt decider and its input that can
prevent a correct halt status decision.

>> In the case of the HP the contradiction
>> can be avoided in the first place by having a third outcome: P(I) being
>> invalid due to pathology that would result in the contradiction.
>
> Yes, there are only partial halt deciders. There is nothing
> contradictory about a partial decider. Some are even interesting and/or
> useful.
>
>> HP solved;
>
> Students often get confused by what the "problem" is. The decision
> problem called the hating problem has no algorithmic solution, but it
> can be solved by super-algorithmic models. You appear to agree with
> that. The "meta-problem", of whether there is an algorithmic solution
> to the decision problem, was solved (essentially) in 1936.
>
> It's not at all clear what you think you have "solved".
>


--
Copyright 2021 Pete Olcott

"Great spirits have always encountered violent opposition from mediocre
minds." Einstein