XPost: comp.theory
From: polcott333@gmail.com

On 11/24/2025 12:12 PM, Mike Terry wrote:
> On 24/11/2025 16:32, Kaz Kylheku wrote:
>> On 2025-11-24, olcott  wrote:
>>> On 11/22/2025 11:24 PM, Kaz Kylheku wrote:
>>>> That's just the thing! If this were correctly implemented then in fact
>>>> DD /wold be/ calling HHH1, using the name HHH.
>>>>
>>>
>>> You are trying to get away with this lie
>>> about the semantics of C?
>>>
>>> int main()
>>> {
>>>     HHH(DD);
>>>     HHH1(DD);
>>>     return 0;
>>> }
>>>
>>> _main()
>>> [000022c4] 55             push ebp
>>> [000022c5] 8bec           mov ebp,esp
>>> [000022c7] 6834220000     push 00002234 ; push DD
>>> [000022cc] e833f3ffff     call 00001604 ; call HHH
>>> [000022d1] 83c404         add esp,+04
>>> [000022d4] 6834220000     push 00002234 ; push DD
>>> [000022d9] e856f2ffff     call 00001534 ; call HHH1
>>> [000022de] 83c404         add esp,+04
>>> [000022e1] 33c0           xor eax,eax
>>> [000022e3] 5d             pop ebp
>>> [000022e4] c3             ret
>>> Size in bytes:(0033) [000022e4]
>>
>> That's right; even if HHH and HHH1 are separately realized and given
>> different adddresses, not recognized as identical by the compiler and
>> not folded into one copy, in a correct implementation of your software,
>> HHH(DD) and HHH1(DD) would behave as indistinguishable, mutually
>> interchangeable operations.
>
> Right - in terms of their results when called.
>
> But TM-descriptions can legitimately contain multiple distinct copies of
> "the same algorithm", and there's no reason that an emulator emulating
> the TM is required to identify such copies as being copies - an emulator
> just has to mimic what the TM would do and the TM doesn't know that it
> has multiple copies of the same algorithm with different state
> labels...  Your point that the /results/ of those copied algorithms must
> be the same is spot on though.
>>
>> The problem is that you have logic which concludes that HHH1 != HHH (low
>> level pointer comparison), they are different functions.
>
> If we were talking about H and H1, this would be a reasonable
> explanation.  Your approach of changing pointer comparison to consider
> H/H1 the same would fix the problem.  Another way of looking at things
> would be that H and H1 use different global constants in their
> algorithms (viz H uses H [address of function H] and H1 uses H1 [address
> of function H1].  No surprise they give different results!  If instead
> say H used literal 17, and H1 used literal 19, this explanation would be
> obvious, but H/H1/17/19 are all examples of "global constants".  Looked
> at this way, we can fix the problem by changing H1 to make it "a proper
> copy of H", that would require changing the H1 in H1's body to H, and
> then behaviour of H/H1 would be the same.   [Which fix approach is
> better depends on what you consider the essential problem to be.]
>
> For HHH/HHH1 the issue is different - they are clearly different
> algorithms since they give different results,

He disagrees with this verified fact. He thinks that the
different results prove that they are incorrect.

> but it's not pointer
> comparison that is the problem - it's the use of mutable global data:
> HHH and HHH1 each use /their own/ global variable [viz their global
> trace tables] within their algorithms.  It so happens that in this case,

You know that calling this global is inaccurate so don't do it.
It is local static data.

https://chatgpt.com/share/691e0ea1-423c-8011-b3ad-20e2371d9496
Says that this doesn't make a difference. It says that a
TM can do something equivalent.

I cannot verify that ChatGPT is correct on this point because
I do not 100% totally understand every nuance of its reasoning
as I do on almost all of my conversations with LLMs.

> the global data is a static variable, and so it /appears/ at first
> glance as though they are the same - they have the same name in both
> HHH/HHH1, but behind the scenes they are scoped to HHH/HHH1
> respectively, and are different data items.  I imagine the compiler
> qualifies the storage label with the function name somehow behind the
> scenes, but don't know the details.  Meanwhile PO gets to claim "they
> are the same -

The key difference is that DD calls HHH(DD) in recursive
simulation and does not call HHH1(DD) in recursive simulation.
When HHH(DD) correctly sees the repeating pattern then HHH1(DD)
would see no repeating pattern.

> just compare the function bodies!".  [The effect of all
> this, is that HHH only sees trace entries "delivered" from nested HHH's,
> and HHH1 only sees trace entries "delivered" from nested HHH1's (of
> which there are none!) - no surprise that they produce different results.]
>

That is not quite accurate. HHH sees all of the instructions
of DD that are simulated by any instance of itself and HHH1
sees all of the instructions of DD that are simulated by any
instance of itself and these are not the same.

> One way to fix this [akin to my H/H1 fix], would be to make HHH1
> processing match HHH, e.g. change both HHH/HHH1 to use a common global-
> scope variable rather than a static-cope ones.  This leaves the
> underlying problems of invalid global data use, but at least HHH/HHH1
> are now equivalent.  The proper way of fixing the problem would be to
> get rid of the improper use of global data in both HHH/HHH1.  With
> either of these fixes HHH and HHH1 would produce the same result
> [neverhalts].
>
> Changing the function pointer address comparison in HHH/HHH1 would not
> fix the problem.  [I suppose I should confirm this at some point, as
> I've claimed it several times!]
>
> Coming back to my first remark about /results/ of copied algorithms
> being the same, with either of my proposed fixes this becomes true -
> HHH/HHH1 produce the same result for DD.  They would also produce the
> same result for DD_HHH1.  That's not to say that a decider /emulating/
> HHH or HHH1 must identify HHH/HHH1 within the emulation as the same -
> sure, it's /allowed/ to try and do that, but not required to; the
> decider can do as it pleases.  Just as a TM decider could spot a loop
> while emulating its input TM-desc, where the emulation is stuck on state
> q_13, without caring whether q13 is part of some algorithm with multiple
> copies throughout the TM-description, making q_13 "equivalent" to say
> q_39 and to q_72.
>
>
> Mike.
>


--
Copyright 2025 Olcott


[continued in next message]

--- SoupGate-Win32 v1.05
 * Origin: you cannot sedate... all the things you hate (1:229/2)