XPost: comp.theory
On 3/3/2021 3:13 PM, Mike Terry wrote:
On 03/03/2021 18:41, olcott wrote:
On 3/3/2021 8:54 AM, Mike Terry wrote:
On 02/03/2021 03:32, olcott wrote:
On 3/1/2021 9:05 PM, olcott wrote:
On 3/1/2021 8:22 PM, Mike Terry wrote:
On 02/03/2021 01:31, olcott wrote:
On 3/1/2021 7:00 PM, Mike Terry wrote:
On 01/03/2021 23:00, olcott wrote:
On 3/1/2021 4:42 PM, Mike Terry wrote:
On 01/03/2021 20:22, olcott wrote:
On 3/1/2021 1:39 PM, Kaz Kylheku wrote:
On 2021-03-01, olcott <NoOne@NoWhere.com> wrote:
On 3/1/2021 12:25 PM, Kaz Kylheku wrote:
On 2021-03-01, olcott <NoOne@NoWhere.com> wrote:
On 3/1/2021 10:52 AM, Kaz Kylheku wrote:
I already acknowledged this. When an equivalent
computation is run on a
machine without resource limits (such as a TM) then this >>>>>>>>>>>>>>> computation is
infinitely recursive.
That depends on what you mean by "equivalent". Since you >>>>>>>>>>>>>> have tied the
validity your work to the x86 representation, a Turing >>>>>>>>>>>>>> Machine version
of your program, to be equivalent, has to contain the x86 >>>>>>>>>>>>>> program, and
the simulator, faithfully reproducing the same resource >>>>>>>>>>>>>> limitations.
A RASP machine is known to be equivalent to a UTM.
Thus the RASP is to the RAM as the Universal Turing machine >>>>>>>>>>>>> is to the
Turing machine. The RASP is an example of the von Neumann >>>>>>>>>>>>> architecture.
https://en.wikipedia.org/wiki/Random-access_stored-program_machine
The x86 language is another exapmle of the von Neumann >>>>>>>>>>>>> architecture.
All computations implemented using the von Neumann
architecture are
equivalent to one another as long as they do not require >>>>>>>>>>>>> more memory
than is available.
Thus all computations implemented using the von Neumann >>>>>>>>>>>>> architecture are
equivalent UTM computations as long as they do not require >>>>>>>>>>>>> more memory
than is available.
That is true; but an infinite recursion does require
When I say that the x86 emulator: Simulate() is
functionally equivalent
to this code:
int Simulate(u32 P, u32 I)
{
((void(*)(int))P)(I);
return 1;
}
That is all that need be said about the capabilities of >>>>>>>>>>>>>>> the x86 emulator.
Yes; then clearly, the H_Hat(P, P) call (with the right >>>>>>>>>>>>>> casts put in)
denotes a runaway recursive call.
So we agree on this point?
Why wouldn't we? It's obviously a runaway recursive call. >>>>>>>>>>>>
When we know that Simulate() is an x86 emulator that is >>>>>>>>>>>>> functionally
equivalent to direct execution of its input then from the >>>>>>>>>>>>> execution
trace of the execution of this input (including the inputs >>>>>>>>>>>>> to functions
stored on the stack) alone we can decide that H_Hat() is >>>>>>>>>>>>> infinitely
recursive.
Yes.
In a static call graph of a program, we can spot loops. >>>>>>>>>>>>
For instance a simple infinite loop occurs when a basic >>>>>>>>>>>> block jumps to
itself.
A basic block has no branching instructions anywhere, except >>>>>>>>>>>> as possibly
the last instruction. If that last instruction is an
unconditional jump
back to that block, that is an infinite loop.
Compilers do this kind of control flow analysis to find loops, >>>>>>>>>>>> where certain optimizations can be concentrated (e.g. giving >>>>>>>>>>>> more
registers to variables in nested loops).
If we monitor the execution dynamically, we can likewise >>>>>>>>>>>> identify
"dynamic basic blocks" sequences of unconditionally executed >>>>>>>>>>>> instructions with no branches, and we can detect infinite >>>>>>>>>>>> loops.
(Possibly ones that contain a stack push, if the jump is >>>>>>>>>>>> actually
a subroutine call.)
If we simply identify the situation, but don't interfere in >>>>>>>>>>>> it, then the
situation persists: there is runaway recursion.
When this same simulator monitors its own simulation it could >>>>>>>>>>> figure out that the H_Hat() invocation of itself is
infinitely recursive.
I'm afraid that's "wrong-headed" thinking, because Simulate >>>>>>>>>> simply DOES NOT monitor its own simulation, so you can't talk >>>>>>>>>> about when it does something IT DOESN'T DO. :) The same
mental confusion underlies your ".. /would/ fail to terminate >>>>>>>>>> /if/ ABNHBD() didn't abort the emulation", and other
anthropomorphisms you make for TMs.
So in other words you cannot possibly begin to imagine that a >>>>>>>>> software function could be adapted to add functionality.
/We/ can figure out that the above H_Hat is infinitely
recursive, but /we/ are not Simulate, so H_Hat is not our
"We_hat", and this says nothing about the Linz proof.
The /Simulate/ as you've described it (pure emulation)
/cannot/ "figure it out", because it fails to return and so >>>>>>>>>> doesn't "figure" anything. Again, nothing much to say re HP >>>>>>>>>> proof.
We could code a /new/ emulator routine Simulate2 (distinct >>>>>>>>>> from H_Hat and Simulate above) which has monitoring logic, and >>>>>>>>>> use it to examine a simulation of the H_Hat above calling
Simulate(H_Hat) (note: NOT calling Simulate2...), and this >>>>>>>>>> Simulate2 could correctly decide that H_Hat(H_Hat) does not >>>>>>>>>> terminate.
But H_Hat is not the "hatted" machine for Simulate2, so this >>>>>>>>>> also is of little interest. Nobody claims that "no decider >>>>>>>>>> can correctly decide halting for H_Hat", only that H does not >>>>>>>>>> correctly decide halting for its own H_Hat.
If we "update" H_Hat so that instead of calling Simulate, it >>>>>>>>>> calls the new Simulate2, then we have a /new/ program H_Hat2, >>>>>>>>>> and a /new/ calculation to consider. When H_Hat2 examines the >>>>>>>>>> calculation H_Hat2(H_Hat2), with H_Hat2 calling Simulate2
etc., then H_Hat2 /*cannot*/ "figure out" that the calculation >>>>>>>>>> has infinite recursion, BECAUSE IT DOESN'T. It can certainly >>>>>>>>>> /decide/ that H_Hat2 is infinitely recursive, but that would >>>>>>>>>> just be Simulate2 deciding incorrectly. All in line with Linz >>>>>>>>>> proof.
Remember, Simulate2 is not a "pure emulator" like Simulate, so >>>>>>>>>> the fact that there may be two nested emulated calls to
Simulate2 with the same argument IS NOT PROOF OF INFINITE
RECURSION.
When Simulate2() is identical to Simulate() in every way except >>>>>>>>> that it also examines the execution trace of its input to
figure out that its input is calling Simulate2() in infinite >>>>>>>>> recursion then by logical necessity H_Hat() is still infinitely >>>>>>>>> recursive.
?
H_Hat doesn't call Simulate2. Maybe you mean H_Hat2 ?
Obviously the /H_Hat/ calculation is "still" infinitely
recursive, because that calculation has never changed - by
definition it calls Simulate (not Simulate2).
Hmm, your phrase "figuring out" isn't a standard CS term - I've >>>>>>>> guessed it to mean that Simulate2 returns some different rc (not >>>>>>>> 1) when it detects the nested calls to Simulate2 with the same >>>>>>>> input data, thus making a different decision to the rc=1 [halts] >>>>>>>> decision. Maybe you mean something else?
Mike.
An x86 emulator could keep track of all of the details of the
execution trace of any input. If the original Simulate() was
adapted to have this feature and the names remain the same then
H_Hat() would invoke this updated version of Simulate() and still >>>>>>> be infinitely recursive.
So was my guess right? Does "figuring out" mean that Simulate2
returns some different rc (not 1) when it detects the nested calls >>>>>> to Simulate2 with the same input data, thus making a different
decision to the rc=1 [halts] decision? All you've done is replace >>>>>> "figuring out" with "keep track of" which is no better.
When software engineers add features to existing functions they
do not change the names.
What they do is change the versions. But you are not a software
engineer, so maybe you don't know about version numbers.
Software engineers use version control systems so that if required >>>>>> they can recreate the software at whatever point in the
development cycle is required, so there will not be confusion over >>>>>> what code is being used/discussed at any time.
This is the version number of the whole system at that point in
time. I worked on defense projects using version control. The
function almost always keep their original names and merely acquire
additional functionality.
In contrast, /you/ habitually use the same name for different
programs, and different names for the same programs. I suspect
this is because in part your arguments rely on confusing different >>>>>> programs as being the same thing, in various ways. So it seems to >>>>>> me that you do this deliberately. This is the exact opposite to
how a software engineer or professional programmer would behave.
There are only three programs that I will be talking about:
// P has the machine address of H_Hat()
void H_Hat(u32 P)
{
u32 Input_Halts = Simulate(P, P);
if (Input_Halts)
HERE: goto HERE;
return;
}
That calls Simulate(P, P) and as the conversation progresses will
gradually be adapted step-by-step until it becomes Halts(P, P).
There will not be any version numbers for Simulate() because
Simulate() is merely a conversational convention used to construct
complete understanding of Halts() in small incremental steps.
If it is not deliberate, I suggest you just affix versions to the
end of your programs e.g. "H_Hat2" when they change. That's
easier than full versions, e.g. "H_Hat (V2.1.0.0)" and more
appropriate for newsgroup discussions.
Mike.
int Simulate_1(u32 P, u32 I);
Emulates the x86 code pointed to by machine address P with data at
machine address I.
int Simulate_2(u32 P, u32 I);
Same as Simulate_1() except keeps track of the execution trace of
its input including the data passed to any function invocations.
What does "keeps track of" mean? Does Simulate_2 "do" anything with
this tracked data, or is it just (in this version at least) ignored?
I provide every single detail of exactly what keeps track of means and
you simply ignore it.
It would have probably been easier if I separated out the "keeps track
of" portion so you could see this separately. I have done that now.
This is every single detail that the simulator / halt decider keeps
track of for the computation shown below.
Columns
(1) Sequence number
(2) Machine address of instruction
(3) Machine address of top of stack
(4) Value of top of stack after instruction executed
(5) Number of bytes of machine code
(6) Machine language bytes
(7) Assembly language text
(01)[00000888][00011194][00000000](01) 55 push ebp (02)[00000889][00011194][00000000](02) 8bec mov ebp,esp (03)[0000088b][00011190][00000868](05) 6868080000 push 00000868 (04)[00000890][0001118c][00000868](05) 6868080000 push 00000868 (05)[00000895][00011188][0000089a](05) e8defbffff call 00000478 (06)[00000868][00011178][00011184](01) 55 push ebp (07)[00000869][00011178][00011184](02) 8bec mov ebp,esp (08)[0000086b][00011178][00011184](03) 8b4508 mov eax,[ebp+08] (09)[0000086e][00011174][00000868](01) 50 push eax (10)[0000086f][00011174][00000868](03) 8b4d08 mov ecx,[ebp+08] (11)[00000872][00011170][00000868](01) 51 push ecx (12)[00000873][0001116c][00000878](05) e800fcffff call 00000478 (13)[00000868][0001115c][00011168](01) 55 push ebp (14)[00000869][0001115c][00011168](02) 8bec mov ebp,esp (15)[0000086b][0001115c][00011168](03) 8b4508 mov eax,[ebp+08] (16)[0000086e][00011158][00000868](01) 50 push eax (17)[0000086f][00011158][00000868](03) 8b4d08 mov ecx,[ebp+08] (18)[00000872][00011154][00000868](01) 51 push ecx (19)[00000873][00011150][00000878](05) e800fcffff call 00000478 (20)[00000868][00011140][0001114c](01) 55 push ebp (21)[00000869][00011140][0001114c](02) 8bec mov ebp,esp (22)[0000086b][00011140][0001114c](03) 8b4508 mov eax,[ebp+08] (23)[0000086e][0001113c][00000868](01) 50 push eax (24)[0000086f][0001113c][00000868](03) 8b4d08 mov ecx,[ebp+08] (25)[00000872][00011138][00000868](01) 51 push ecx (26)[00000873][00011134][00000878](05) e800fcffff call 00000478
The Simulator / Halt Decider only needs to keep track of the data shown
in the above table. It decodes the machine language and thus ignores the assembly language. I show all of the details of how it analyzes this
data below.
Minimal criteria for deciding that H_Hat() calls Simulate() in infinite recursion.
(1) The execution trace of H_Hat() shows that it calls Simulate() from
the same machine address two times in sequence with the same data.
(2) It is assumed that Simulate() either directly invokes its input (as
shown below) or Simulate() emulates the execution of the x86 machine
language of its input (functionally equivalent to the direct execution
shown below).
Does everyone agree that the above criteria is sufficient to definitely
decide that H_Hat() is infinitely recursive?
#include <stdint.h>
#define u32 uint32_t
int Simulate(u32 P, u32 I)
{
((void(*)(u32))P)(I);
}
void H_Hat(u32 P)
{
Simulate(P, P);
}
int main()
{
Simulate((u32)H_Hat, (u32)H_Hat);
}
_Simulate()
[00000478](01) 55 push ebp
[00000479](02) 8bec mov ebp,esp
[0000047b](03) 8b450c mov eax,[ebp+0c]
[0000047e](01) 50 push eax
[0000047f](03) ff5508 call dword [ebp+08]
[00000482](03) 83c404 add esp,+04
[00000485](01) 5d pop ebp
[00000486](01) c3 ret
_H_Hat()
[00000868](01) 55 push ebp
[00000869](02) 8bec mov ebp,esp
[0000086b](03) 8b4508 mov eax,[ebp+08]
[0000086e](01) 50 push eax
[0000086f](03) 8b4d08 mov ecx,[ebp+08]
[00000872](01) 51 push ecx
[00000873](05) e800fcffff call 00000478
[00000878](03) 83c408 add esp,+08
[0000087b](01) 5d pop ebp
[0000087c](01) c3 ret
_main()
[00000888](01) 55 push ebp
[00000889](02) 8bec mov ebp,esp
[0000088b](05) 6868080000 push 00000868
[00000890](05) 6868080000 push 00000868
[00000895](05) e8defbffff call 00000478
[0000089a](03) 83c408 add esp,+08
[0000089d](02) 33c0 xor eax,eax
[0000089f](01) 5d pop ebp
[000008a0](01) c3 ret
Columns
(1) Sequence number
(2) Machine address of instruction
(3) Machine address of top of stack
(4) Value of top of stack after instruction executed
(5) Number of bytes of machine code
(6) Machine language bytes
(7) Assembly language text
(01)[00000888][00011194][00000000](01) 55 push ebp (02)[00000889][00011194][00000000](02) 8bec mov ebp,esp (03)[0000088b][00011190][00000868](05) 6868080000 push 00000868 (04)[00000890][0001118c][00000868](05) 6868080000 push 00000868 (05)[00000895][00011188][0000089a](05) e8defbffff call 00000478 (06)[00000868][00011178][00011184](01) 55 push ebp (07)[00000869][00011178][00011184](02) 8bec mov ebp,esp (08)[0000086b][00011178][00011184](03) 8b4508 mov eax,[ebp+08] (09)[0000086e][00011174][00000868](01) 50 push eax (10)[0000086f][00011174][00000868](03) 8b4d08 mov ecx,[ebp+08] (11)[00000872][00011170][00000868](01) 51 push ecx (12)[00000873][0001116c][00000878](05) e800fcffff call 00000478
Line (09) pushes second parameter to Simulate() machine address 0x878
Line (11) pushes first parameter to Simulate() machine address 0x878
Line (12) Calls Simulate(0x878, 0x878);
(13)[00000868][0001115c][00011168](01) 55 push ebp (14)[00000869][0001115c][00011168](02) 8bec mov ebp,esp (15)[0000086b][0001115c][00011168](03) 8b4508 mov eax,[ebp+08] (16)[0000086e][00011158][00000868](01) 50 push eax (17)[0000086f][00011158][00000868](03) 8b4d08 mov ecx,[ebp+08] (18)[00000872][00011154][00000868](01) 51 push ecx (19)[00000873][00011150][00000878](05) e800fcffff call 00000478
Line (16) pushes second parameter to Simulate() machine address 0x878
Line (18) pushes first parameter to Simulate() machine address 0x878
Line (19) Calls Simulate(0x878, 0x878);
(20)[00000868][00011140][0001114c](01) 55 push ebp (21)[00000869][00011140][0001114c](02) 8bec mov ebp,esp (22)[0000086b][00011140][0001114c](03) 8b4508 mov eax,[ebp+08] (23)[0000086e][0001113c][00000868](01) 50 push eax (24)[0000086f][0001113c][00000868](03) 8b4d08 mov ecx,[ebp+08] (25)[00000872][00011138][00000868](01) 51 push ecx (26)[00000873][00011134][00000878](05) e800fcffff call 00000478
Line (23) pushes second parameter to Simulate() machine address 0x878
Line (25) pushes first parameter to Simulate() machine address 0x878
Line (26) Calls Simulate(0x878, 0x878);
Now we have seen that Simulate() is invoked two times from the same
machine address of H_Hat() with the same data. We also know that
Simulate() either executes or emulates the machine language of its input
and nothing more. This seems to provide a sufficient basis for deciding
that H_Hat() is infinitely recursive, thus non-halting.
--
Copyright 2021 Pete Olcott
"Great spirits have always encountered violent opposition from mediocre
minds." Einstein
--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)