Sunday, March 14, 2021

Digest for comp.lang.c++@googlegroups.com - 5 updates in 4 topics

Nikki Locke <nikki@trumphurst.com>: Mar 14 11:23PM

Available C++ Libraries FAQ
 
URL: http://www.trumphurst.com/cpplibs/
 
This is a searchable list of libraries and utilities (both free
and commercial) available to C++ programmers.
 
If you know of a library which is not in the list, why not fill
in the form at http://www.trumphurst.com/cpplibs/cppsub.php
 
Maintainer: Nikki Locke - if you wish to contact me, please use the form on the website.
olcott <polcott2@gmail.com>: Mar 14 09:55AM -0500

On 3/14/2021 5:29 AM, Malcolm McLean wrote:
> system. In order to get round Linz's proof you have to change Linz's system
> somehow, as PO acknowledges. The solution he has chosen, based on
> what he has said recently, is to wrap main() in a supervisor.
 
We are not wrapping main() in a supervisor exactly.
More accurately the x86utm operating system is the master UTM that
applies its system level halt decider to every user computation.
 
The program under test:H_Hat() and the tester:Halts() are distinctly
different computations. It is the conflation of these two that creates
the pathological self-reference error.
 
The teacher does not share the students grade.
When the halt decider determines that the simulation of its input must
be aborted to prevent its infinite execution the input <is> a
non-halting computation. As Ben pointed out its ridiculous to construe
that a computation is a halting computation if the only reason that it
halts is that its exection was aborted.
 
--
Copyright 2021 Pete Olcott "Great spirits have always encountered
violent opposition from mediocre minds." Einstein
olcott <polcott2@gmail.com>: Mar 14 01:17PM -0500

On 3/14/2021 11:34 AM, Kaz Kylheku wrote:
 
> The decider is a function. H_Hat is a specific input, so Halts(H_Hat,
> H_Hat) returns exactly one value, just like Add(1, 3). It cannot
> return any other value. The opposite of that value is the correct one.
 
On Ben's excellent suggestion I have superseded all of this reasoning
and simply concluded that if the only reason an input program halts is
that its execution was aborted by the halt decider then this input
program <is> a non-halting computation.
 
 
On 3/13/2021 8:26 PM, Ben Bacarisse wrote:
> halt if not stopped, you'd have a conventional halt decider
> and you should be boasting about that, not hiding your light
> under a "redefining the criterion" bushel.
 
The linked paper shows exactly how an at least partial halt decider
 
> really could detect those computations** would not halt if not stopped,
 
** The conventional halting problem undecidability proof counter-examples
 
http://www.liarparadox.org/Halting_problem_undecidability_and_infinite_recursion.pdf
 
--
Copyright 2021 Pete Olcott "Great spirits have always encountered
violent opposition from mediocre minds." Einstein
olcott <NoOne@NoWhere.com>: Mar 14 12:46PM -0500

Halting problem undecidability and infinite recursion
 
The simplest way to define a halt decider is to make a program that runs its input to see what it does. In technical terms this would be a universal Turing machine (UTM) that has been adapted to become a halt decider. This UTM would simply simulate the execution of its input until its input halts on its own or the halt decider determines that its input would never halt on its own and stops simulating it. In order for the UTM to see what its input does it must keep track of an execution trace of its input.
 
Every (at least partial) halt decider that decides the halting status of its input on the basis of its examination of the execution trace of its own simulation of this input would correctly decide the conventional halting problem undecidability proof counter-examples would not halt. The fact that the only reason these input programs halted was that their execution was aborted proves that they are non-halting computations. Since the halt decider is the master UTM no computations can be defined that avoid being examined by the halt decider.
 
The x86utm operating system was created so that halt deciders written in the C programming language would be computationally equivalent to the execution of actual Turing machines. These (at least partial) halt deciders base their halting decision on examining the execution trace of the x86 machine language of their input. The input is the COFF object file output of a C compiler and is directly executed by the x86 emulator.
 
The halt decider Halts() determines that H_Hat() called it in infinite recursion, on the basis of the x86 machine language execution trace shown below, stop simulating its input, and decide not halting on the basis that its input would not halt.
 
void H_Hat(u32 P)
 
{
 
u32 Input_Would_Halt = Halts(P, P);
 
if (Input_Would_Halt)
 
HERE: goto HERE;
 
}
 
int main()
 
{
 
u32 Input_Would_Halt = Halts((u32)H_Hat, (u32)H_Hat);
 
Output("Input_Would_Halt = ", Input_Would_Halt);
 
}
 
_H_Hat()
 
[00000a63](01) 55 push ebp
 
[00000a64](02) 8bec mov ebp,esp
 
[00000a66](01) 51 push ecx
 
[00000a67](03) 8b4508 mov eax,[ebp+08]
 
[00000a6a](01) 50 push eax
 
[00000a6b](03) 8b4d08 mov ecx,[ebp+08]
 
[00000a6e](01) 51 push ecx
 
[00000a6f](05) e80ffeffff call 00000883
 
[00000a74](03) 83c408 add esp,+08
 
[00000a77](03) 8945fc mov [ebp-04],eax
 
[00000a7a](04) 837dfc00 cmp dword [ebp-04],+00
 
[00000a7e](02) 7402 jz 00000a82
 
[00000a80](02) ebfe jmp 00000a80
 
[00000a82](02) 8be5 mov esp,ebp
 
[00000a84](01) 5d pop ebp
 
[00000a85](01) c3 ret
 
Size in bytes:(0035)
 
_main()
 
[00000a93](01) 55 push ebp
 
[00000a94](02) 8bec mov ebp,esp
 
[00000a96](01) 51 push ecx
 
[00000a97](05) 68630a0000 push 00000a63
 
[00000a9c](05) 68630a0000 push 00000a63
 
[00000aa1](05) e8ddfdffff call 00000883
 
[00000aa6](03) 83c408 add esp,+08
 
[00000aa9](03) 8945fc mov [ebp-04],eax
 
[00000aac](03) 8b45fc mov eax,[ebp-04]
 
[00000aaf](01) 50 push eax
 
[00000ab0](05) 681f030000 push 0000031f
 
[00000ab5](05) e8a9f8ffff call 00000363
 
[00000aba](03) 83c408 add esp,+08
 
[00000abd](02) 33c0 xor eax,eax
 
[00000abf](02) 8be5 mov esp,ebp
 
[00000ac1](01) 5d pop ebp
 
[00000ac2](01) c3 ret
 
Size in bytes:(0048)
 
Columns
 
(1) Execution trace 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)[00000a93][000114f7][00000000](01) 55 push ebp
 
(02)[00000a94][000114f7][00000000](02) 8bec mov ebp,esp
 
(03)[00000a96][000114f3][00000000](01) 51 push ecx
 
(04)[00000a97][000114ef][00000a63](05) 68630a0000 push 00000a63
 
(05)[00000a9c][000114eb][00000a63](05) 68630a0000 push 00000a63
 
(06)[00000aa1][000114e7][00000aa6](05) e8ddfdffff call 00000883
 
(07)[00000a63][00031577][0003157b](01) 55 push ebp
 
(08)[00000a64][00031577][0003157b](02) 8bec mov ebp,esp
 
(09)[00000a66][00031573][00021547](01) 51 push ecx
 
(10)[00000a67][00031573][00021547](03) 8b4508 mov eax,[ebp+08]
 
(11)[00000a6a][0003156f][00000a63](01) 50 push eax
 
(12)[00000a6b][0003156f][00000a63](03) 8b4d08 mov ecx,[ebp+08]
 
(13)[00000a6e][0003156b][00000a63](01) 51 push ecx
 
(14)[00000a6f][00031567][00000a74](05) e80ffeffff call 00000883
 
(15)[00000a63][0004271f][00042723](01) 55 push ebp
 
(16)[00000a64][0004271f][00042723](02) 8bec mov ebp,esp
 
(17)[00000a66][0004271b][000326ef](01) 51 push ecx
 
(18)[00000a67][0004271b][000326ef](03) 8b4508 mov eax,[ebp+08]
 
(19)[00000a6a][00042717][00000a63](01) 50 push eax
 
(20)[00000a6b][00042717][00000a63](03) 8b4d08 mov ecx,[ebp+08]
 
(21)[00000a6e][00042713][00000a63](01) 51 push ecx
 
(22)[00000a6f][0004270f][00000a74](05) e80ffeffff call 00000883
 
Infinite Recursion Detected Simulation Stopped
 
Halts() detected that is was called twice in the execution trace of H_Hat() from the same machine address without any conditional branch instructions inbetween.
 
(23)[00000aa6][000114f3][00000000](03) 83c408 add esp,+08
 
(24)[00000aa9][000114f3][00000000](03) 8945fc mov [ebp-04],eax
 
(25)[00000aac][000114f3][00000000](03) 8b45fc mov eax,[ebp-04]
 
(26)[00000aaf][000114ef][00000000](01) 50 push eax
 
(27)[00000ab0][000114eb][0000031f](05) 681f030000 push 0000031f
 
(28)[00000ab5][000114e7][00000aba](05) e8a9f8ffff call 00000363
 
Input_Would_Halt = 0
 
(29)[00000aba][000114f3][00000000](03) 83c408 add esp,+08
 
(30)[00000abd][000114f3][00000000](02) 33c0 xor eax,eax
 
(31)[00000abf][000114f7][00000000](02) 8be5 mov esp,ebp
 
(32)[00000ac1][000114fb][00010000](01) 5d pop ebp
 
(33)[00000ac2][000114ff][00000080](01) c3 ret
 
Number_of_User_Instructions(33)
 
Number of Instructions Executed(13966)
 
When the halt decider is based on a UTM such that the only computations are simulations by this halt decider / UTM then no computations can bypass the halt decider's analysis.
 
01 int main()
 
02 {
 
03 HERE: goto HERE;
 
04 u32 Input_Would_Halt = Halts((u32)H_Hat, (u32)H_Hat);
 
05 Output("Input_Would_Halt = ", Input_Would_Halt);
 
06 }
 
Is terminated at line 03 by the x86utm operating system Halts()
 
01 int main()
 
02 {
 
03 H_Hat((u32)H_Hat);
 
04 u32 Input_Would_Halt = Halts((u32)H_Hat, (u32)H_Hat);
 
05 Output("Input_Would_Halt = ", Input_Would_Halt);
 
06 }
 
Is terminated at line 03 by the x86utm operating system Halts()
 
Copyright 2021 PL Olcott
 
-- Copyright 2021 Pete Olcott "Great spirits have always encountered violent opposition from mediocre minds." Einstein
olcott <NoOne@NoWhere.com>: Mar 14 12:25PM -0500

Halting problem undecidability and infinite recursion
 
The simplest way to define a halt decider is to make a program that runs
its input to see what it does. In technical terms this would be a
universal Turing machine (UTM) that has been adapted to become a halt
decider. This UTM would simply simulate the execution of its input until
its input halts on its own or the halt decider determines that its input
would never halt on its own and stops simulating it. In order for the
UTM to see what its input does it must keep track of an execution trace
of its input.
 
Every (at least partial) halt decider that decides the halting status of
its input on the basis of its examination of the execution trace of its
own simulation of this input would correctly decide the conventional
halting problem undecidability proof counter-examples would not halt.
The fact that the only reason these input programs halted was that their
execution was aborted proves that they are non-halting computations.
Since the halt decider is the master UTM no computations can be defined
that avoid being examined by the halt decider.
 
The x86utm operating system was created so that halt deciders written in
the C programming language would be computationally equivalent to the
execution of actual Turing machines. These (at least partial) halt
deciders base their halting decision on examining the execution trace of
the x86 machine language of their input. The input is the COFF object
file output of a C compiler and is directly executed by the x86 emulator.
 
The halt decider Halts() determines that H_Hat() called it in infinite
recursion, on the basis of the x86 machine language execution trace
shown below, stop simulating its input, and decide not halting on the
basis that its input would not halt.
 
void H_Hat(u32 P)
{
u32 Input_Would_Halt = Halts(P, P);
if (Input_Would_Halt)
HERE: goto HERE;
}
 
 
int main()
{
u32 Input_Would_Halt = Halts((u32)H_Hat, (u32)H_Hat);
Output("Input_Would_Halt = ", Input_Would_Halt);
}
 
 
_H_Hat()
[00000a63](01) 55 push ebp
[00000a64](02) 8bec mov ebp,esp
[00000a66](01) 51 push ecx
[00000a67](03) 8b4508 mov eax,[ebp+08]
[00000a6a](01) 50 push eax
[00000a6b](03) 8b4d08 mov ecx,[ebp+08]
[00000a6e](01) 51 push ecx
[00000a6f](05) e80ffeffff call 00000883
[00000a74](03) 83c408 add esp,+08
[00000a77](03) 8945fc mov [ebp-04],eax
[00000a7a](04) 837dfc00 cmp dword [ebp-04],+00
[00000a7e](02) 7402 jz 00000a82
[00000a80](02) ebfe jmp 00000a80
[00000a82](02) 8be5 mov esp,ebp
[00000a84](01) 5d pop ebp
[00000a85](01) c3 ret
Size in bytes:(0035)
 
 
_main()
[00000a93](01) 55 push ebp
[00000a94](02) 8bec mov ebp,esp
[00000a96](01) 51 push ecx
[00000a97](05) 68630a0000 push 00000a63
[00000a9c](05) 68630a0000 push 00000a63
[00000aa1](05) e8ddfdffff call 00000883
[00000aa6](03) 83c408 add esp,+08
[00000aa9](03) 8945fc mov [ebp-04],eax
[00000aac](03) 8b45fc mov eax,[ebp-04]
[00000aaf](01) 50 push eax
[00000ab0](05) 681f030000 push 0000031f
[00000ab5](05) e8a9f8ffff call 00000363
[00000aba](03) 83c408 add esp,+08
[00000abd](02) 33c0 xor eax,eax
[00000abf](02) 8be5 mov esp,ebp
[00000ac1](01) 5d pop ebp
[00000ac2](01) c3 ret
Size in bytes:(0048)
 
 
Columns
(1) Execution trace 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)[00000a93][000114f7][00000000](01) 55 push ebp
(02)[00000a94][000114f7][00000000](02) 8bec mov ebp,esp
(03)[00000a96][000114f3][00000000](01) 51 push ecx
(04)[00000a97][000114ef][00000a63](05) 68630a0000 push 00000a63
(05)[00000a9c][000114eb][00000a63](05) 68630a0000 push 00000a63
(06)[00000aa1][000114e7][00000aa6](05) e8ddfdffff call 00000883
 
(07)[00000a63][00031577][0003157b](01) 55 push ebp
(08)[00000a64][00031577][0003157b](02) 8bec mov ebp,esp
(09)[00000a66][00031573][00021547](01) 51 push ecx
(10)[00000a67][00031573][00021547](03) 8b4508 mov eax,[ebp+08]
(11)[00000a6a][0003156f][00000a63](01) 50 push eax
(12)[00000a6b][0003156f][00000a63](03) 8b4d08 mov ecx,[ebp+08]
(13)[00000a6e][0003156b][00000a63](01) 51 push ecx
(14)[00000a6f][00031567][00000a74](05) e80ffeffff call 00000883
(15)[00000a63][0004271f][00042723](01) 55 push ebp
(16)[00000a64][0004271f][00042723](02) 8bec mov ebp,esp
(17)[00000a66][0004271b][000326ef](01) 51 push ecx
(18)[00000a67][0004271b][000326ef](03) 8b4508 mov eax,[ebp+08]
(19)[00000a6a][00042717][00000a63](01) 50 push eax
(20)[00000a6b][00042717][00000a63](03) 8b4d08 mov ecx,[ebp+08]
(21)[00000a6e][00042713][00000a63](01) 51 push ecx
(22)[00000a6f][0004270f][00000a74](05) e80ffeffff call 00000883
Infinite Recursion Detected Simulation Stopped
 
Halts() detected that is was called twice in the execution trace of
H_Hat() from the same machine address without any conditional branch
instructions inbetween.
 
(23)[00000aa6][000114f3][00000000](03) 83c408 add esp,+08
(24)[00000aa9][000114f3][00000000](03) 8945fc mov [ebp-04],eax
(25)[00000aac][000114f3][00000000](03) 8b45fc mov eax,[ebp-04]
(26)[00000aaf][000114ef][00000000](01) 50 push eax
(27)[00000ab0][000114eb][0000031f](05) 681f030000 push 0000031f
(28)[00000ab5][000114e7][00000aba](05) e8a9f8ffff call 00000363
Input_Would_Halt = 0
(29)[00000aba][000114f3][00000000](03) 83c408 add esp,+08
(30)[00000abd][000114f3][00000000](02) 33c0 xor eax,eax
(31)[00000abf][000114f7][00000000](02) 8be5 mov esp,ebp
(32)[00000ac1][000114fb][00010000](01) 5d pop ebp
(33)[00000ac2][000114ff][00000080](01) c3 ret
Number_of_User_Instructions(33)
Number of Instructions Executed(13966)
 
When the halt decider is based on a UTM such that the only computations
are simulations by this halt decider / UTM then no computations can
bypass the halt decider's analysis.
 
01 int main()
02 {
03 HERE: goto HERE;
04 u32 Input_Would_Halt = Halts((u32)H_Hat, (u32)H_Hat);
05 Output("Input_Would_Halt = ", Input_Would_Halt);
06 }
Is terminated at line 03 by the x86utm operating system Halts()
 
 
01 int main()
02 {
03 H_Hat((u32)H_Hat);
04 u32 Input_Would_Halt = Halts((u32)H_Hat, (u32)H_Hat);
05 Output("Input_Would_Halt = ", Input_Would_Halt);
06 }
Is terminated at line 03 by the x86utm operating system Halts()
 
 
http://www.liarparadox.org/Halting_problem_undecidability_and_infinite_recursion.pdf
 
 
 
--
Copyright 2021 Pete Olcott
 
"Great spirits have always encountered violent opposition from mediocre
minds." Einstein
You received this digest because you're subscribed to updates for this group. You can change your settings on the group membership page.
To unsubscribe from this group and stop receiving emails from it send an email to comp.lang.c+++unsubscribe@googlegroups.com.
Posted by at

No comments:

Post a Comment

Subscribe to: Post Comments (Atom)