Re: H(P,P) as a pure function of its inputs is easy [ source-code will be available ]

[olcott]

On 6/12/2022 3:02 PM, Ben Bacarisse wrote:
> Andy Walker <a...@cuboid.co.uk> writes:
>
>> On 11/06/2022 21:10, Ben Bacarisse wrote:
>>> There's nothing interesting about pure functions from a theoretical
>>> point of view, but PO has ditched all notions of a formal model of
>>> computation, [...].
>>
>> Yeah, but others seem to be insisting on "PURE FUNCTIONS" for no
>> good reason that I can discern.
>
> OK, but I've also seen such insistence when it might matter. I do think
> it's the wrong thing to focus on (H could go consult the WWW for all I
> care) but it is one way to try to pin PO's nonsense down a bit.
>
>>> This program prints 1 (on my system) and halts because H_Hat(H_Hat)
>>> "halts" (i.e. returns to main) even though H_Hat is correctly
>>> constructed from H.
>>
>> Except that your "H" is not the decider but merely a subroutine of
>> your program. A correctly constructed "H_Hat" is not based just on such a
>> subroutine but on the entire program which contains "H". [I know you know
>> all this, but it bears occasional repetition.]
>
> Yes, but that's exactly why some people worry about pure functions. By
> re-framing the problem in terms of subroutines (and PO is not alone in
> this -- see Strachey's oft-cited note) extra care is needed.
>
>>> My guess is that it is trickery like this that makes people worry about
>>> functions being pure.
>>
>> Sure, but it's not really to do with purity as much as with replacing
>> an input tape [or near equivalent] by compiled [and non-standard] code invoked
>> from within the program. So the program is not deciding about a program and
>> its input but just running a particular program.
>
> <cut>
>>> Another approach, using C, would have been to make H take the source
>>> code of a C program as a string,
>>
>> That, for me, is what the HP /is/. If "H" then includes a compiler
>> and some way of running/emulating the compiled code, so be it. ...
>
> But there is a "halting problem" for functions entirely analogous to the
> one for whole programs. When PO shifts from Turing machines (about
> which he has nothing to say anymore, having exhausted all avenues for
> confusion) to C-like code, it's not actually wrong to do that, but the
> notion of what a computation is and what "halting" means need to be
> carefully pinned down. I think people reach for pure functions as a
> simple way to deal with some of that.
>

Finally mutual agreement on one key point.
Now that H(P,P)==0 is derived on the basis of a pure function of its
inputs I will be able to post the code for H and P. Prior to that it
would have been rejected on the basis that it depended on static local
data. This only needs very slight code clean up.

If I strip out all of work-in-progress code H, H0, H1, H2 and P takes
ten pages of code. If I add the support code that actually implements
the x86utm operating system this is fifty more pages. This needs lots of
code clean up.

The slightly adapted original x86 emulator (hundreds of pages) has been
adapted to compile under Windows and has the single additional function
of disassembling all of the functions in its machine language input. The
adapted code is very clean.

>>> rather than elide the issue of
>>> representation by using a code pointer but PO rejected any notion of
>>> "encoding" as being "extraneous complexity" for years and he still does
>>> not understand the concept.
>>
>> ... Such a solution may be complex, but it's not "extraneous"!
>


--
Copyright 2022 Pete Olcott

"Talent hits a target no one else can hit;
Genius hits a target no one else can see."
Arthur Schopenhauer

[Mr Flibble]

The only agreement (among ourselves, excluding yourself) is that your H
is not a halt decider; your H should be renamed to S as all it is is a
simulation detector.

/Flibble

[olcott]

(1) But there is a "halting problem" for functions entirely analogous

to the one for whole programs.

(2) When PO shifts from Turing machines to C-like code, it's not
actually wrong to do that.

(3) The notion of what a computation is and what "halting"

means need to be carefully pinned down.

Points of mutual agreement between myself and Ben.

One of the key points of disagreement seems to be that people agree that
a halt decider must compute the mapping from its inputs to an accept or
reject state on the basis of the actual behavior of its inputs

Yet are totally unaware that they contradict themselves when they say
that H(P,P) must report on the behavior of P(P).

When I prove to them THAT the behavior of the correctly emulated input
to H(P,P) has different halting behavior than the directly executed P(P)
and WHY this behavior is different

When P(P) is executed its behavior conditionally depends on the return
value of H.

When H(P,P) is executed the correctly emulated P cannot possibly reach
the point where its behavior depends on H.

They utterly disregard these verified facts because they simply don't
believe them.

[Mr Flibble]

On Sun, 12 Jun 2022 16:18:03 -0500

If P would have halted then your H would get the answer wrong, ergo H
is not a halt decider as it has total disregard for the actual
behaviour of P.

/Flibble

[olcott]

int sum(int x, int y)
{
return x + y;
}

sum(3,4) must return 7 and not the sum of 7 + 9;

H(P,P) must report on the actual behavior of its actual input and thus
not the behavior of P(P).

H2(sum,3,4) will report on the behavior of sum(3,4) because sum was not
intentionally defined to have a pathological relationship with H2.

H(P,P) will not report on the behavior of P(P) because P was
intentionally defined to have a pathological relationship to H.

H must compute the mapping from, its actual inputs to an accept or
reject state on the basis of the actual behavior actually specified by
its inputs.

[Mr Flibble]

On Sun, 12 Jun 2022 16:38:43 -0500

Correct analysis of its input, P, necessitates correct analysis of
the behaviour of P; ignoring what P does means you are not deciding
anything regarding P including whether or not it halts.

/Flibble

[olcott]

Because P was intentionally defined to have a pathological relationship
to H the behavior of the correctly emulated input to H(P,P) has
different behavior than the directly executed P(P).

In every other case where no such pathological relationship was
intentionally defined the correctly emulated input to H(X,Y) will have
the exact same behavior as the directly executed X(Y).

Prior to my key insight of applying simulating halt decider to
pathological inputs no one knew that the correctly emulated input to
H(P,P) could have different behavior that the directly executed P(P) so
the textbook accounts of the HP simply referred to the behavior of P(P).

> ignoring what P does means you are not deciding
> anything regarding P including whether or not it halts.
>
> /Flibble
>

[Mr Flibble]

On Sun, 12 Jun 2022 17:03:31 -0500

Except you don't handle the case of a non-pathological program, N, which
calls H but then halts.

Also your "simulating halt decider" will never return an answer for a
program that doesn't halt but is non-pathological. This is a problem
with simulation in general rather than with your mess specifically.

/Flibble

[olcott]

*THE FOLLOWING CRITERIA ALWAYS WORKS*
H computes the mapping from its input finite strings to its accept or
reject state on the basis of the actual behavior specified by the actual
input as measured by the correct x86 emulation or UTM simulation of this
input by H.

[Richard Damon]

On 6/12/22 5:38 PM, olcott wrote:
>
> int sum(int x, int y)
> {
>   return x + y;
> }
>
> sum(3,4) must return 7 and not the sum of 7 + 9;
>
> H(P,P) must report on the actual behavior of its actual input and thus
> not the behavior of P(P).

Which, by the DEFINITION of a Halt Decider, the behavior of the input to
H(P,P) is the behavior of P(P), or H or P haven't been defined right.

Remember, H is DEFINED to answer about the behavior of the computation
performed by the algorithm described by the first part of its input to
the input described by the seond part of its input.

P is DEFINED to ask H about the computation defined by applying the
algorithm/machine that its input describes to that description.

Thus the input to P MUST BE a description of the program P, and thus P
will ask H about what happens when P is applied to the description of
the Program P, which just happens to be itself.

Thus, if H(P,P) is NOT asking about P(P) then something was done wrong.

If we can't ask H about P(P), then H just fails to be the needed
decider, as that decider was REQUIRED to decide about ANY mahine/input
pair, and this is one.

IF we CAN ask H about P(P), but need a different input, then P was built
wrong, as that was what it was supposed to ask about.

So, which error did you make?

>
> H2(sum,3,4) will report on the behavior of sum(3,4) because sum was not
> intentionally defined to have a pathological relationship with H2.
>
> H(P,P) will not report on the behavior of P(P) because P was
> intentionally defined to have a pathological relationship to H.
>

No special exenption for this case.

> H must compute the mapping from, its actual inputs to an accept or
> reject state on the basis of the actual behavior actually specified by
> its inputs.

Which, as pointed above IS P(P) or H or P weren't defined right, so
either you built your system wrong, or H(P,P) is just wrong.

[olcott]

On 6/12/2022 6:16 PM, Richard Damon wrote:
>
> On 6/12/22 5:38 PM, olcott wrote:
>>
>> int sum(int x, int y)
>> {
>>    return x + y;
>> }
>>
>> sum(3,4) must return 7 and not the sum of 7 + 9;
>>
>> H(P,P) must report on the actual behavior of its actual input and thus
>> not the behavior of P(P).
>
> Which, by the DEFINITION of a Halt Decider, the behavior of the input to
> H(P,P) is the behavior of P(P), or H or P haven't been defined right.
>

This "definition" was based on a false assumption that the behavior of
the correctly emulated input to H(P,P) must be the same as the behavior
of the directly executed P(P). Once the assumption is proven false then
the "definition" based on this assumption is also refuted.

Before my research no one was aware of the possibility that the
correctly simulated input to H(P,P) could possibly have behavior that is
different than the directly executed P(P).

Because P was intentionally defined to have a pathological relationship
to H the behavior of the correctly emulated input to H(P,P) has
different behavior than the directly executed P(P).

In every other case where no such pathological relationship was
intentionally defined the correctly emulated input to H(X,Y) will have
the exact same behavior as the directly executed X(Y).

Prior to my key insight of applying simulating halt decider to
pathological inputs no one knew that the correctly emulated input to
H(P,P) could have different behavior that the directly executed P(P) so
the textbook accounts of the HP simply referred to the behavior of P(P).

[Richard Damon]

On 6/12/22 6:47 PM, olcott wrote:
>
> *THE FOLLOWING CRITERIA ALWAYS WORKS*
> H computes the mapping from its input finite strings to its accept or
> reject state on the basis of the actual behavior specified by the actual
> input as measured by the correct x86 emulation or UTM simulation of this
> input by H.

Sort of, referencing a UTM (or equivalent) works. Just remember, if H
aborts its simulation, it never was a UTM or correct x86 emulation (even
for this definition). So, saying "By H" means that you are DEFINING your
H to actually do this, which means it isn't allowed to abort is simulation.

Doing "Correct Emulation Until ..." does not result in correct and
complete Emulation or behavior like a UTM, so doesn't count for this
definition. Thus if H only does a correct emulation until, or act like a
UTM until, your definition is invalid as it presumes something that
isn't true.

So either your H actually follows this definition, and thus, by this
definition, it can NEVER answer 0 for non-halting computaition, because
it was define to do a complete and correct emulation / UTM Simulation,
and thus fails to be a decider, or your H fails to meet the requirements
of the definition.

Yes, some machines, like Infinite_Loop, can be actually proved to be
non-halting from a partial emulation, but this doesn't mean that all
inputs, (like P(P)) can be so proved.

[Richard Damon]

On 6/12/22 7:33 PM, olcott wrote:
> On 6/12/2022 6:16 PM, Richard Damon wrote:
>>
>> On 6/12/22 5:38 PM, olcott wrote:
>>>
>>> int sum(int x, int y)
>>> {
>>>    return x + y;
>>> }
>>>
>>> sum(3,4) must return 7 and not the sum of 7 + 9;
>>>
>>> H(P,P) must report on the actual behavior of its actual input and
>>> thus not the behavior of P(P).
>>
>> Which, by the DEFINITION of a Halt Decider, the behavior of the input
>> to H(P,P) is the behavior of P(P), or H or P haven't been defined right.
>>
> This "definition" was based on a false assumption that the behavior of
> the correctly emulated input to H(P,P) must be the same as the behavior
> of the directly executed P(P). Once the assumption is proven false then
> the "definition" based on this assumption is also refuted.

But that is the DEFINITION of a CORRECT EMULATION.

You don't get to change the definition. PERIOD. YOU LOSE.

The RULES are the RULES.

>
> Before my research no one was aware of the possibility that the
> correctly simulated input to H(P,P) could possibly have behavior that is
> different than the directly executed P(P).

Which you have yet to actualy show.

Remember a CORRECT emulation must actual correctly emulate each and
every actual detailed step of the input program. That means that when P
calls H, the emulation is of the instruction of H, not some
"meta-emulation" of that H emulation in another layer.

>
> Because P was intentionally defined to have a pathological relationship
> to H the behavior of the correctly emulated input to H(P,P) has
> different behavior than the directly executed P(P).
>

No, it doesn't. Rememver a CORRECT EMULATION looks at each x86 assembly
instruction and emulates it just as if the CPU was executing it. That
includes the instruction is H, as they are not special.

If H is an actual Pure Function / Computation, that emulation through H
of the call of H(P,P) by P will see the exact same sequence as when P(P)
was executed directly.

Now the actual H, if it does return 0, will at some point abort its
emulation and return 0 to the P that called it and that P halts.

But, the CORRECT emulation of that input doesn't stop there but
continues emulating the code in H until that emulation sees the code
doing the same decision and aborting it emulated emulation and returning
to the emualted P and that emualted P then returns/halts.

Your refusal to accept this FACT, just shows that you don't care about
actual truth, but are just trying to push your lie.

[Richard Damon]

And the "functions" so considered include ALL the call tree of that
function, so if P calls H, that H is PART of the "function" that is
being decided on.

>
> (2) When PO shifts from Turing machines to C-like code, it's not
> actually wrong to do that.

yes, you CAN work with C-like code, but care must be taken that
everything thought of as a "function" actually works as one, meanings
its behavior is ONLY a function of its direct parameters.

>
> (3) The notion of what a computation is and what "halting"
> means need to be carefully pinned down.
>
> Points of mutual agreement between myself and Ben.
>
> One of the key points of disagreement seems to be that people agree that
> a halt decider must compute the mapping from its inputs to an accept or
> reject state on the basis of the actual behavior of its inputs
>
> Yet are totally unaware that they contradict themselves when they say
> that H(P,P) must report on the behavior of P(P).

Except that is the DEFINITION

>
> When I prove to them THAT the behavior of the correctly emulated input
> to H(P,P) has different halting behavior than the directly executed P(P)
> and WHY this behavior is different

You have NEVER done this. First, the correct emulation of the input to
H(P,P) needs to show the actual emultaion of the instructions of H when
P calls H(P,P).

Since you don't, you have NEVER shown a "correct" x86 emulation. PERIOD.

>
> When P(P) is executed its behavior conditionally depends on the return
> value of H.
>
> When H(P,P) is executed the correctly emulated P cannot possibly reach
> the point where its behavior depends on H.

But that ONLY happens if H never returns the value 0 but keep emulating,
at which point NO copies of H can ever return the value of 0.

>
> They utterly disregard these verified facts because they simply don't
> believe them.
>

No, because you have just claimed this but never proved it.

Note, to show that the two different instances of the execution of
H(P,P) behave differently, you need to show the first instruction where
that difference in execution behavior occurs. That will be H executing
the same instruction with the same data (since H only uses its input,
and the two inputs were the same and this is the first divergance) but
produces different results.

Until you show this, you are just LYING that you have proved that this
is possible. All your arguments are based on assumptions that this is
what happens, so are based on the fallacy of assuming the conclusion.

Till you actually prove it, it didn't happen, and is just a lie.