On 5/30/2022 8:14 AM, Dennis Bush wrote:
> On Monday, May 30, 2022 at 8:56:49 AM UTC-4, olcott wrote:
>> On 5/29/2022 11:04 PM, Dennis Bush wrote:
>>> On Sunday, May 29, 2022 at 11:42:27 PM UTC-4, olcott wrote:
>>>> On 5/29/2022 7:44 PM, Dennis Bush wrote:
>>>>> On Sunday, May 29, 2022 at 8:33:53 PM UTC-4, olcott wrote:
>>>>>> On 5/29/2022 6:24 PM, Mike Terry wrote:
>>>>>>> On 29/05/2022 22:56, André G. Isaak wrote:
>>>>>>>> On 2022-05-29 15:41, olcott wrote:
>>>>>>>>> On 5/29/2022 4:30 PM, André G. Isaak wrote:
>>>>>>>>>> On 2022-05-29 15:16, olcott wrote:
>>>>>>>>>>> On 5/29/2022 4:00 PM, André G. Isaak wrote:
>>>>>>>>>>>> On 2022-05-29 14:35, olcott wrote:
>>>>>>>>>>>>> On 5/29/2022 2:58 PM, André G. Isaak wrote:
>>>>>>>>>>>>>> On 2022-05-29 13:26, olcott wrote:
>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>> Agree. I think PO probably can't understand the proper
>>>>>>>>>>>>>>>> definition of halting. That definition doesn't involve any
>>>>>>>>>>>>>>>> UTMs or emulation - it's just a mathematical definition, first
>>>>>>>>>>>>>>>> of the computation steps, then of halting in terms of there
>>>>>>>>>>>>>>>> being an n such that computation step n is a final state of
>>>>>>>>>>>>>>>> the TM. That's TOO ABSTRACT for PO, so all he can do is
>>>>>>>>>>>>>>>> replace it with something he thinks he /can/ understand:
>>>>>>>>>>>>>>>> something more concrete - a simulation run in some "actual
>>>>>>>>>>>>>>>> machine" processing a TM description and tape description!
>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>> HERE IS WHY ACTUAL COMPUTER SCIENTISTS WILL AGREE WITH ME
>>>>>>>>>>>>>>> Every decider computes the mapping from its input finite
>>>>>>>>>>>>>>> string(s) to an accept or reject state based on a semantic or
>>>>>>>>>>>>>>> syntactic property of this finite string.
>>>>>>>>>>>>>>
>>>>>>>>>>>>>> Finite strings don't have semantic properties.
>>>>>>>>>>>>>
>>>>>>>>>>>>>
>>>>>>>>>>>>> In computability theory, Rice's theorem states that all
>>>>>>>>>>>>> non-trivial semantic properties of programs are undecidable.
>>>>>>>>>>>>
>>>>>>>>>>>> And how 'bout them Mets?
>>>>>>>>>>>>
>>>>>>>>>>>>> A semantic property is one about the program's behavior (for
>>>>>>>>>>>>> instance, does the program terminate for all inputs),
>>>>>>>>>>>>>
>>>>>>>>>>>>> https://en.wikipedia.org/wiki/Rice%27s_theorem
>>>>>>>>>>>>>
>>>>>>>>>>>>> In formal semantics this would be the semantic property of a
>>>>>>>>>>>>> finite string.
>>>>>>>>>>>>
>>>>>>>>>>>> No, it would be a semantic property of the program. That program
>>>>>>>>>>>> might be *represented* as a string, but the string itself has no
>>>>>>>>>>>> semantic properties.
>>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>> The semantic property of the string when it is interpreted as the
>>>>>>>>>>> description of a program.
>>>>>>>>>>
>>>>>>>>>> WHOOOSH!
>>>>>>>>>>
>>>>>>>>>> As soon you you add 'when it is interpreted as...' you are no longer
>>>>>>>>>> talking about the string but the thing which the string represents.
>>>>>>>>>>
>>>>>>>>>
>>>>>>>>> Yes. The string has no semantics on its own.
>>>>>>>>>
>>>>>>>>> The input to H(P,P) determines (Mike's word) an execution trace of
>>>>>>>>> x86 instructions when correctly emulated by H.
>>>>>>>>>
>>>>>>>>> The input to H1(P,P) determines (Mike's word) an execution trace of
>>>>>>>>> x86 instructions when correctly emulated by H1.
>>>>>>>>
>>>>>>>> And neither of those sentences make any sense. Replacing 'specifies'
>>>>>>>> with 'determines' doesn't make things any clearer. You need to
>>>>>>>> actually DEFINE your terms.
>>>>>>>>
>>>>>>>>> These execution traces are not the same.
>>>>>>>> Which means at least one of the above programs is *not* interpreting
>>>>>>>> its input in the correct way, i.e. in the way which the specification
>>>>>>>> of a halt decider demands.
>>>>>>>
>>>>>>> Hows about...
>>>>>>>
>>>>>>> Computation P(P) goes through a sequence of steps, which for
>>>>>>> illustration I'll just refer to as <a> <b> ... <z> with <z> being the
>>>>>>> final (RET) step where the computation halts. Now, H and H1 calculate
>>>>>>> these steps ["emulate their input"] something like this:
>>>>>>>
>>>>>>> H1 H
>>>>>>> ---- ----
>>>>>>> <a> <a> // P(P) very first state!
>>>>>>> <b> <b>
>>>>>>> <c> <c>
>>>>>>> <d> <d>
>>>>>>> <e> <e>
>>>>>>> <f> <f>
>>>>>>> <g> <g>
>>>>>>> <h> <h>
>>>>>>> <i> <i>
>>>>>>> <j> <j>
>>>>>>> <k> <k>
>>>>>>> <l> <l> // no divergence so far!
>>>>>>> <m> <m>
>>>>>>> <n> <n>
>>>>>>> <o> <o>
>>>>>>> <p> <p>
>>>>>>> <q> <q>
>>>>>>> <r> <r> // H spots some pattern and stops simulating
>>>>>>> <s>
>>>>>>> <t>
>>>>>>> <u>
>>>>>>> <v>
>>>>>>> <w>
>>>>>>> <x>
>>>>>>> <y>
>>>>>>> <z> // P(P) final state - it halts!
>>>>>>>
>>>>>>> So in PO language "the input to H(P,P)" is (P,P), and this determines
>>>>>>> the steps of the computation P(P) which are being calculated by the
>>>>>>> emulator in H, which calculates <a>...<r> then stops calculating because
>>>>>>> it spotted some pattern. [in PO terms, <a>...<r> are the x86
>>>>>>> instructions or their trace entries].
>>>>>>>
>>>>>>> "the input to H1(P,P)" is also (P,P), and this determines the steps of
>>>>>>> the computation P(P) which are being calculated by the emulator in H1,
>>>>>>> which calculates <a>...<r>...<z> then stops because final state [ret
>>>>>>> instruction] is reached.
>>>>>>>
>>>>>>> PO might try to deny that H1 calculates the same steps as H from <a> to
>>>>>>> <r>, or might agree. I don't think PO really understands what's
>>>>>>> happening in his own program. :)
>>>>>>>
>>>>>>> In PO language, perhaps, BOTH the above are "correct emulations" because
>>>>>>> the sequence of "x86 instruction transitions" <a> --> <b> etc. is
>>>>>>> correct on a step-by-step basis. (That would be consistent with his
>>>>>>> claim repeated 1000 times, that we can check the emulation is correct by
>>>>>>> comparing the machine code listings and verifying that emulation is
>>>>>>> [doing each instruction correctly].)
>>>>>>>
>>>>>>> H's decision to stop emulating is not (IMO) part of the emulation
>>>>>>> itself. (How could it be? but probably that's just a matter of agreeing
>>>>>>> the terms we're using.)
>>>>>>>
>>>>>>> Anyhow, he who would argue with PO would do well to pin PO down on his
>>>>>>> strange choice of phrases to avoid weeks or months of
>>>>>>> miscommunications. And you have to start by discovering /something/ you
>>>>>>> agree on... Just demanding he "defines all his terms" won't get far as
>>>>>>> he can't "define" anything properly. :)
>>>>>>>
>>>>>>>
>>>>>>> Mike.
>>>>>>>
>>>>>> The input to H1(P,P) halts.
>>>>>> In this same computation the input to H(P,P)
>>>>>> would never reach its "ret" instruction in 1 to ∞ emulated steps.
>>>>>
>>>>> But the fixed algorithm of H, hereafter referred to as Ha and the P that call it referred to as Pa, does not simulate for an infinite number of steps. It simulates for a particular number of cycles.
>>>> _Infinite_Loop()
>>>> [000012c2](01) 55 push ebp
>>>> [000012c3](02) 8bec mov ebp,esp
>>>> [000012c5](02) ebfe jmp 000012c5
>>>> [000012c7](01) 5d pop ebp
>>>> [000012c8](01) c3 ret
>>>> Size in bytes:(0007) [000012c8]
>>>>
>>>> H correctly simulates its input until it determines that a correct
>>>> simulation of ∞ steps of this input would never reach the "ret"
>>>> instruction of this input.
>>>
>>> By definition, a correct simulation is performed by a UTM. UTM(_Infinite_Loop,"") does not halt. UTM(Pa,Pa) does halt, so Ha(Pa,Pa)==0 is wrong.
>> UTM(P,P) determines an execution trace of P that reaches its "ret"
>> instruction. Yet this is a deliberately deceptive example and you know
>> it. Here is an actual comparable example:
>
> It is not deceptive. It is the *definition* of a correct simulation.
>
>>
>> Emulate(P,P);
>>
>> void P(u32 x)
>> {
>> if (Emulate(x, x))
>> HERE: goto HERE;
>> return;
>> }
>
>
> What you call Emulate is Hn,

No I would not because the H means halt decider.

> and because of that, P is Pn. And Pn(Pn) does not halt, nor does Hn(Pn,Pn).
>
> So you're claiming that Ha(Pa,Pa)==0 is correct because Pn(Pn) does not halt.

When-so-ever any input to a simulating halt decider must have its
simulation aborted to prevent the infinite simulation of this input this
input is correctly determined to be a non-halting input.

H(P,P) determines the infinite behavior of Hn(P,P) in a few steps thus
conclusively proving that its input never reaches its "ret" instruction
whether it aborts the simulation of this input or not.

Even though H itself has fixed behavior H correctly determines the
behavior of its input for an infinite set of definitions of itself.
(a) H that aborts the simulation of its input at some point.
(b) Hn that never aborts the simulation of its input.

> Which is invalid, > because Pn(Pn) has nothing to do with Pa(Pa).
>
>>
>>>
>>> Ha3 can also simulate _Infinite_Loop to correctly determine that it never halts, so the fact that Ha can do it means nothing.

--
Copyright 2022 Pete Olcott

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