Re: Undecidablity of halting problem and pathological programs

0 views
Skip to first unread message

olcott

unread,
Jul 19, 2021, 10:45:07 AMJul 19
to
On 7/18/2021 5:43 AM, David Brown wrote:
> Olcott and Mr. Flibble have got themselves tied up with their idea that
> you can make a halting decider that works for all computations except
> "pathological" ones designed specifically to confound your decider - and
> that these "pathological" computations need knowledge of your decider
> and are therefore cheating.
>

No Flibble says that not me:

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.

> Let us suppose that they are correct that it is cheating to look inside
> the "black box" and design a confounding input based on that knowledge.
> Here is the outline of a proof that it is still not possible to make a
> halting decider. (Apologies if my terminology is imprecise - it is a
> /long/ time since I did this stuff formally.)
>
>
> First, let me give a few facts. We are talking here about calculable
> functions - things that can be done using a finite Turing Machine in
> finite time. (You can substitute any other Turing complete computation
> model if you prefer - unlimited register machines, cellular automata,
> x86 simulators, etc. It's all equivalent.) You can give each TM a
> number, and thus order them - there are a /countably/ infinite number of
> different TM's. Every Turing Machine has a number, and every number
> (positive integer) corresponds to a Turing Machine. We call TM(x) the
> Turing Machine corresponding to number x, and num(t) the number
> corresponding to Turing Machine t.
>
>
> Call the partial halting deciders H_1, H_2, H_3, etc., ordered by their
> TM numbers. We suppose that these can solve the halting problem for any
> (P, X) input that is not constructed with special knowledge of which
> halting decider we are using. (It may also be able to solve for inputs
> with knowledge of the partial decider being tested - we just don't
> require it.)
>
> This rules out having P defined as "if H_1(P, P) loop forever, else
> return 0" as a confounder for H_1, and so on.
>
> Obviously a complete halting decider H must be a member of this set, if
> such a halting decider exists.
>
> How big is this set { H_1, H_2, etc. } ?
>
> Suppose it is finite, and we have H_1, ..., H_n.
>
> H_n is a TM, and thus corresponds to a number N in our ordered list of
> Turing Machines.
>
> Define P_n as:
>
> P_n(x) =
> if x == 1 then if TM(1)(x, x) loop forever;
> if x == 2 then if TM(2)(x, x) loop forever;
> ...
> if x == N then if TM(N)(x, x) loop forever;
> return 0
>
>
> Now (P_n, num(H_n)) is a confounder for each of H_1, ..., H_n.
>
> P_n has no knowledge of any of the partial halting functions, and does
> not look inside the "black box".
>
>
> Perhaps the set is infinite. Then we can't write such a confounder
> function in this form, as the definition would also be infinite (and
> TM's are always finite). Does this infinite set contain a true
> universal halting decider H somewhere? Well, H must be finite - thus it
> must equal H_n for some n. We can ignore the rest of the list - P_n is
> a confounder for all of H_1 up to H_n that does not rely on any
> knowledge of the partial halting function being tested. Since it
> confounds H_n, and therefore our supposed universal halting decider, we
> know that no such universal halting decider can exist.
>
>


--
Copyright 2021 Pete Olcott

"Great spirits have always encountered violent opposition from mediocre
minds." Einstein
Reply all
Reply to author
Forward
0 new messages