Re: Refuting the halting problem proofs with fully operational code (honest dialogue?)

[olcott]

On 3/11/2021 2:52 PM, Kaz Kylheku wrote:
> On 2021-03-11, olcott <No...@NoWhere.com> wrote:
>> On 3/11/2021 12:54 PM, Kaz Kylheku wrote:
>>> On 2021-03-11, olcott <No...@NoWhere.com> wrote:
>>>> I haven't finished rewriting the global halt decider so I am not sure
>>>> what it would do.
>>>>
>>>> I did have to correct your syntax and create Simulate2() that takes
>>>> three params, Simulate() only takes two params.
>>>>
>>>> Simulate2( (u32)Halts, (u32)H_Hat, (u32)H_Hat );
>>>> Simulate2( (u32)Simulate, (u32)H_Hat, (u32)H_Hat );
>>>
>>> The problem is that you're making a strawman version of the halting
>>> problem.
>>>
>>> There is no inherent self-reference in the real problem.
>> So then H_Hat() does not do the opposite of whatever the halt decider
>> decides ABOUT ITS OWN BEHAVIOR ???
>
> It "does the opposite" of whatever the halt decision algorithm decides
> about any program P that is given itself as input P.
>
> It can do that by having its own copy of the decision algorithm,
> written as a clean-room implementation by the author of H_Hat.
>
> In the conventional proofs, this is simply shown as a function call to Halts.
>
> In reality, it can use any function that is equivalent to Halts.
>
> Your idea of Halts detecting the fact that Halts is being called is
> invalid. It will not detect a copy of Halts being called. And you might
> think that you could compare the instructions; but a copy of Halts can
> look totally different, just calculate the same thing.
>
> So your approach is not only wrong because it doesn't work (pronounces
> H_Hat to be infinitely recursive, when in fact H_Hat(H_Hat) nicely returns)
> but it is fundamentally flawed on a deeper level.
>
> You don't recognize that wildly different pieces of code at different
> addresses in the image could all be equivalent to Halts, and that H_Hat
> could use any of those instead of Halts.

You seem to keep forgetting that I am not defining a universal halt
decider. There is no finite limit to the inputs that a universal halt
decider would be required to decide. All that I am doing is showing how
exactly once instance of the halting problem counter-examples that have
been used to prove undecidability is actually decidable.

The whole: "do the opposite of whatever the halt decider decides"
Does not prove the undecidability of the halting problem, thus refuting
all the proofs that depend on it:

Now we construct a new Turing machine D with H as a
subroutine. This new TM calls H to determine what M
does when the input to M is its own description <M>.

Once D has determined this information, it does the
opposite. That is, it rejects if M accepts and accepts
if M does not accept. (Sipser 1997:165)
http://www.liarparadox.org/sipser_165.pdf

Sipser, Michael 1997. Introduction to the Theory of Computation. Boston:
PWS Publishing Company (165-167)


> When you read the conventional proofs, you must read them as being
> about mathematical functions. A call like Halts(P, P) doesn't mean
> "invoke something at a specific address" but "invoke the abstract
> algorithm Halts(P, P)". That calculation can be embodied in an
> infinite variety of ways which calculate the same thing.
>

As mathematical functions key details are simply abstracted away which
is essentially the same thing as pretending that these details do not
exist. When the counter-example to the halting problem is defined as an
actual computation these key details are mandatory and cannot simply be
assumed away. When these key details are not simply assumed away they
provide the basis of decidability.



--
Copyright 2021 Pete Olcott

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