Wednesday, December 16, 2020

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

olcott <NoOne@NoWhere.com>: Dec 16 03:27PM -0600

If you have a good understanding of:
(a) software engineering,
(b) The C programming language
(c) The x86 programming language
 
You will be able to easily verify that Halts() does correctly decide the
halt status of H_Hat().
 
The x86utm operating system provides the operating environment to
execute virtual machines computationally equivalent to universal Turing
machines having the x86 language as their machine description language.
x86utm executes the COFF object file output of the Microsoft C compiler.
The x86utm operating system is based on a world class x86 emulator that
has been developed and tested for decades.
 
x86 language ≡ von Neumann architecture ≡ UTM ≡ RASP Machine
It is common knowledge that all x86 based programs are computationally
equivalent to UTMs for every computation that does not require more
memory than they have.
 
This is the generic halt deciding criteria:
On Saturday, November 28, 2020 at 2:00:28 PM UTC-8, olcott wrote:
> Every computation that would not halt if its simulation
> were not halted is by logical necessity a non-halting computation.
 
We can verify that the following execution trace of the computational
equivalent of:
(a) {Peter Linz: H, Michael Sipser: H, Dexter Kozen: K}
Correctly decides halting on the the computational equivalent of:
(b) {Peter Linz: Ĥ, Michael Sipser: D, Dexter Kozen: N}
 
The following execution trace can be verified as correctly deciding the
halting status of its input with only these three prerequisites and
nothing more:
 
(a) An elementary understanding of software engineering, such things as:
(a) infinite loops do not have a fixed number of iterations and (b)
infinitely recursive invocations never return any value to their caller.
 
(b) A basic understanding of how the C programming language maps to x86
instructions. This is used to verify that the translations of the "C"
functions into their x86 equivalents are correct. It is also used to
verifiy that the execution trace of these x86 functions is correct.
 
(c) An understanding of one very elementary infinite recursion detection
algorithm: Whenever an execution trace shows a second call to the same
function from the same machine address with no control flow instructions
in-between this second invocation is always an instance of infinite
recursion. From this it is very easy to see that the halt decider did
apply this simple criteria in its halt deciding decision, thus meeting
he generic criteria shown above.
 
Actual debug trace of Halts() deciding halting on H_Hat()
 
#define HALT __asm hlt
 
void H_Hat(u32 P)
{
u32 Input_Halts = Halts(P, P);
if (Input_Halts)
HERE: goto HERE;
else
HALT
}
 
int main()
{
u32 Input_Would_Halt = Halts((u32)H_Hat, (u32)H_Hat);
Output_Debug_Trace();
Output("Input_Would_Halt =", Input_Would_Halt);
HALT;
}
 
_H_Hat()
[000005e6](01) 55 push ebp
[000005e7](02) 8bec mov ebp,esp
[000005e9](01) 51 push ecx
[000005ea](03) 8b4508 mov eax,[ebp+08]
[000005ed](01) 50 push eax
[000005ee](03) 8b4d08 mov ecx,[ebp+08]
[000005f1](01) 51 push ecx
[000005f2](05) e8effdffff call 000003e6
[000005f7](03) 83c408 add esp,+08
[000005fa](03) 8945fc mov [ebp-04],eax
[000005fd](04) 837dfc00 cmp dword [ebp-04],+00
[00000601](02) 7404 jz 00000607
[00000603](02) ebfe jmp 00000603
[00000605](02) eb01 jmp 00000608
[00000607](01) f4 hlt
[00000608](02) 8be5 mov esp,ebp
[0000060a](01) 5d pop ebp
[0000060b](01) c3 ret
 
_main()
[00000616](01) 55 push ebp
[00000617](02) 8bec mov ebp,esp
[00000619](01) 51 push ecx
[0000061a](05) 68e6050000 push 000005e6
[0000061f](05) 68e6050000 push 000005e6
[00000624](05) e8bdfdffff call 000003e6
[00000629](03) 83c408 add esp,+08
[0000062c](03) 8945fc mov [ebp-04],eax
[0000062f](05) e8f2fcffff call 00000326
[00000634](03) 8b45fc mov eax,[ebp-04]
[00000637](01) 50 push eax
[00000638](05) 68a3020000 push 000002a3
[0000063d](05) e894fcffff call 000002d6
[00000642](03) 83c408 add esp,+08
[00000645](01) f4 hlt
[00000646](02) 8be5 mov esp,ebp
[00000648](01) 5d pop ebp
[00000649](01) c3 ret
 
Output_Debug_Trace() Trace_List.size(24)
---[00000616](01) 55 push ebp
---[00000617](02) 8bec mov ebp,esp
---[00000619](01) 51 push ecx
---[0000061a](05) 68e6050000 push 000005e6
---[0000061f](05) 68e6050000 push 000005e6
---[00000624](05) e8bdfdffff call 000003e6 --CALL [000003e6]
---[000005e6](01) 55 push ebp
---[000005e7](02) 8bec mov ebp,esp
---[000005e9](01) 51 push ecx
---[000005ea](03) 8b4508 mov eax,[ebp+08]
---[000005ed](01) 50 push eax
---[000005ee](03) 8b4d08 mov ecx,[ebp+08]
---[000005f1](01) 51 push ecx
---[000005f2](05) e8effdffff call 000003e6 --CALL [000003e6]
---[000005e6](01) 55 push ebp
---[000005e7](02) 8bec mov ebp,esp
---[000005e9](01) 51 push ecx
---[000005ea](03) 8b4508 mov eax,[ebp+08]
---[000005ed](01) 50 push eax
---[000005ee](03) 8b4d08 mov ecx,[ebp+08]
---[000005f1](01) 51 push ecx
---[000005f2](05) e8effdffff call 000003e6 --CALL [000003e6]
Input Aborted because of INFINITE RECURSION from [000005f2] to [000003e6]
---[00000629](03) 83c408 add esp,+08
---[0000062c](03) 8945fc mov [ebp-04],eax
===[0000062f](05) e8f2fcffff call 00000326
...[00000634](03) 8b45fc mov eax,[ebp-04]
...[00000637](01) 50 push eax
...[00000638](05) 68a3020000 push 000002a3
===[0000063d](05) e894fcffff call 000002d6
Input_Would_Halt = 0
...[00000642](03) 83c408 add esp,+08
...[00000645](01) f4 hlt
 
Every time that the same function is called from the same machine
address a second time without any control flow instructions in-between
is a case of infinite recursion.
This is shown at execution trace lines 14-22 above.
 
http://www.liarparadox.org/Peter_Linz_HP(Pages_315-320).pdf
 
Linz, Peter 1990. An Introduction to Formal Languages and Automata.
Lexington/Toronto: D. C. Heath and Company.
 
http://www.liarparadox.org/sipser_165.pdf
 
Sipser, Michael 1997. Introduction to the Theory of Computation. Boston:
PWS Publishing Company (165-167)
 
http://www.liarparadox.org/kozen_233.pdf
 
The Kozen computation is identical to the Peter Linz computation merely
swapping function names Linz.H is swapped for Kozen.K and Linz.Ĥ is
swapped for Kozen.N
 
Kozen, Dexter 1997. Automata and Computability. New York:
Springer-Verlag. (231-234).
 
 
 
--
Copyright 2020 Pete Olcott
 
"Great spirits have always encountered violent opposition from mediocre
minds." Einstein
"Rick C. Hodgin" <rick.c.hodgin@gmail.com>: Dec 16 04:43PM -0500

On 12/16/20 4:27 PM, olcott wrote:
>   u32 Input_Halts = Halts(P, P);
>   if (Input_Halts)
>     HERE: goto HERE;
 
This terminating spin-loop will sit there and consume power and generate
heat as fast as possible and unnecessarily. You'd be better off to
write it as:
 
if (Input_Halts)
{
HERE:
HALT;
goto HERE;
}
 
The HLT instruction causes the CPU to wait for an external interrupt to
signal before proceeding. It slows down the spin-loop, consuming less
power, and generating less heat.
 
BTW, using HLT in your main kernel OS code when you've exhausted every
current task that's demanding CPU time for this time slice can reduce
your CPU's idle temperature down to about 22C in my experience.
 
HLT is one of the most under-utilized instructions IMO. Especially in
scheduler code because the clock will signal an interrupt when the next
test of anything that needs to fire off at a specific time is ready to go.
 
>   else
>     HALT
> }
 
Philosophy is important in understanding what's going on inside a CPU,
and especially when you get into multi-thread / multi-core programming.
 
You are on a good path IMO. Keep going.
 
--
Rick C. Hodgin
Mr Flibble <flibble@i42.REMOVETHISBIT.co.uk>: Dec 16 10:07PM

On 16/12/2020 21:27, olcott wrote:
 
> (a) An elementary understanding of software engineering, such things as: (a) infinite loops do not have a fixed number of iterations and (b) infinitely recursive invocations never return any value to their caller.
 
However to refute Turing and "solve" the Halting Problem any halt decider has to consider loops and recursions that contain conditionals (i.e. branching logic) which your "solution" doesn't.
 
You still have failed to add anything of substance regarding the Halting Problem due to your bloody minded obsession with corner case "counter examples" in some "proofs" that nobody cares about.
 
/Flibble
 
--
😎
Kaz Kylheku <563-365-8930@kylheku.com>: Dec 16 10:21PM


> The HLT instruction causes the CPU to wait for an external interrupt to
> signal before proceeding. It slows down the spin-loop, consuming less
> power, and generating less heat.
 
Peter Olcott has redefined the halt instruction in his emulator
framework to perform a final halt. (As "THe The Halting Problem"
definition of "halt" not "wait in a power-efficient way until an
interrupt occcurs" definition.)
 
> BTW, using HLT in your main kernel OS code when you've exhausted every
> current task that's demanding CPU time for this time slice can reduce
> your CPU's idle temperature down to about 22C in my experience.
 
The usual OS 101 trick is to implement a scheduler in which at least one
task is always runnable. When there is nothing else to do, an idle task
is executed. That idle task does this:
 
for (;;)
relax(); // macro that calls HALT on x86 or whatever
 
There is no reason for the HALT instruction to appear anywhere
else in the system.
 
If there are muliple cores, each one gets its own instance of this idle
task, pinned to that core.
 
--
TXR Programming Language: http://nongnu.org/txr
red floyd <no.spam.here@its.invalid>: Dec 15 04:12PM -0800

On 12/15/2020 2:39 AM, Bonita Montero wrote:
 
> That's true for a pure-virtual destructor because it is called
> for every object which is destructed. But that's not true for
> objects whose pure virtual methods aren't called.
 
I misread your original. I thought you said you had a pure virtual
destructor.
Bonita Montero <Bonita.Montero@gmail.com>: Dec 16 07:54AM +0100

>          --m_nThreads;
> ___________________
 
> Where is the the mutex locked here? What did I miss?
 
Before byeBye is called.
Juha Nieminen <nospam@thanks.invalid>: Dec 16 07:05AM


> This thread is about calling member functions of an object from another
> thread while the destructor of the object has already started in the
> first thread.
 
I see now.
 
So essentially mutual exclusion is needed to guard against the object
being destroyed while another thread is calling some member function of it,
and the solution you suggest is that every thread only accesses the
object through a shared_ptr, which guarantees that the object will not
be destroyed until the last shared_ptr pointing to it is destroyed
(and that two threads destroying their own shared_ptr instance pointing
to that object at the same time is thread-safe.)
Juha Nieminen <nospam@thanks.invalid>: Dec 16 07:09AM

> _ptr<> is slow. Within a thread you simply extract normal pointers
> of a shared_ptr<>-object which live shorter than the shared_ptr<>
> object itself.
 
It sounds like you need mutual exclusion on the object anyway, so whatever
you do it's going to be slower than a mere pointer assignment.
 
The only exception I can think of is if, within the same thread, you keep
a shared_ptr instance pointing to the managed object and then use raw
pointers pointing to it elsewhere within the thread, making absolutely
sure that no such raw pointer is accessed after the shared_ptr has been
destroyed.
Juha Nieminen <nospam@thanks.invalid>: Dec 16 07:11AM

>> for you.
 
> My code is not cryptic.
> The parts that are not easy to understand are documented.
 
But copy-pasting 400+ lines of code without reducing it to the absolute
minimum that reproduces the problem shows that you didn't do any work
to make the problem easier to discern, and are expecting others to do
that work for you.
Bonita Montero <Bonita.Montero@gmail.com>: Dec 16 08:14AM +0100

> It sounds like you need mutual exclusion on the object anyway, so
> whatever you do it's going to be slower than a mere pointer assignment.
 
I was discussing shared_ptr<> in general but not in relation to
what I did.
 
> pointers pointing to it elsewhere within the thread, making absolutely
> sure that no such raw pointer is accessed after the shared_ptr has been
> destroyed.
 
Then use unique_ptr<>.
Bonita Montero <Bonita.Montero@gmail.com>: Dec 16 08:15AM +0100

> minimum that reproduces the problem shows that you didn't do any work
> to make the problem easier to discern, and are expecting others to do
> that work for you.
 
The code doesn't show my problem.
I just wanted to show an elegant implementation of a thread-pool.
Paavo Helde <myfirstname@osa.pri.ee>: Dec 16 10:03AM +0200

16.12.2020 09:05 Juha Nieminen kirjutas:
> be destroyed until the last shared_ptr pointing to it is destroyed
> (and that two threads destroying their own shared_ptr instance pointing
> to that object at the same time is thread-safe.)
 
Right. The desired goal is that as now the destructor would not be
reached while any shared pointer to the object is alive, Bonita would be
forced to move her thread synchronization code out of there and place it
in a more appropriate place.
Bonita Montero <Bonita.Montero@gmail.com>: Dec 16 09:26AM +0100

> reached while any shared pointer to the object is alive, Bonita would be
> forced to move her thread synchronization code out of there and place it
> in a more appropriate place.
 
The thread-pool-objects are destructed after the destructor of the con-
taining object is called. The issue here is that the threads indirectly
call a virtual method of the containing object while destrucor waits
for their termination in the destructor and the VMT-pointer has been
adjusted to null. So the simplest solution was to use a function pointer
instead of a virtual function and everything works as intended now.
Richard Damon <Richard@Damon-Family.org>: Dec 16 07:32AM -0500

On 12/15/20 10:21 AM, Bonita Montero wrote:
 
> If the thread would be the last to have a shared_ptr<> it would call
> the destructor which would wait for the termination of the thread.
> So this wouldn't work.
 
Except tha with the modified design, the destructor wouldn't be waiting
for the termination of the threads, because it would know that all the
threads were ended or are in the process of ending.
Bonita Montero <Bonita.Montero@gmail.com>: Dec 16 02:02PM +0100


> Except tha with the modified design, the destructor wouldn't be waiting
> for the termination of the threads, because it would know that all the
> threads were ended or are in the process of ending.
 
Sorry, that's stupid. I need a proper cleanup since the threads will
usually terminate before the process ends.
Brian Wood <woodbrian77@gmail.com>: Dec 15 03:28PM -0800

On Tuesday, December 15, 2020 at 11:07:09 AM UTC-6, Scott Lurndal wrote:
> Actually, for less than 70 years. It was added to counter the
> "godless communists" during the height of the cold war by
> religious nutcakes.
 
For many years before that it has been on our money.
I guess it's nutty now to work on a free service written in C++.
I'm proud to associate with religious nutcakes like Ben Shapiro
of Dailywire. If only there were more friendly, honest people like
him. In saner times, 40 plus years ago, there were.
 
 
> >I don't know if you're prying, but am thinking about
> >Samson and Delilah.
> A fairy tale from a collection of fireside stories.
 
Disagree.
 
 
Brian
Ebenezer Enterprises
https://webEbenezer.net
scott@slp53.sl.home (Scott Lurndal): Dec 16 12:07AM

>> "godless communists" during the height of the cold war by
>> religious nutcakes.
 
>For many years before that it has been on our money.
 
Again, you display your ignorance. July 30, 1956. 64 years ago.
 
 
https://www.politico.com/story/2018/07/30/in-god-we-trust-becomes-nations-motto-july-30-1956-741016
Brian Wood <woodbrian77@gmail.com>: Dec 15 04:47PM -0800

On Tuesday, December 15, 2020 at 11:32:41 AM UTC-6, Öö Tiib wrote:
> > before there was a drop of rain.
> Did God tell you that you should build serialization library to
> save the world?
 
I didn't say that He did.
 
> plenty of time to study and find some cure or vaccine to
> those viruses. No one did bother and now it is fault of
> evil Chinese government?
 
I don't dispute the part about 2002-2004. For all I know
that's true.
 
> These have good documentation, lot of examples, plenty
> of tools, free to use and enough people online who can help
> even if they are poor.
 
One thing is my offer to help someone who is willing
to use the software:
https://webEbenezer.net/about.html
 
. I'll spend 16 hours/week for 6 months on a project
that uses my software. There's also a referral bonus
described on that page. The page doesn't mention it,
but you can refer yourself and get both the time spent
on your project and the bonus.

> > job though of pretending to be objective.
> Why that online is good and offline is bad or that
> there is some kind of controversy whatsoever?
 
My partially closed source approach is rare in
this space. Is it part of a plan? "A fool with a plan
can beat a genius with no plan" as T. Boone Pickens
said. There are many open source libraries that are
in the "genius with no plan" category imo. If you want
a company that will outlive your company as a partner,
a plan matters.
 
 
> You should stop implying that you are God-directed
> prophet of Online who saves world from evil Offline
> Chinese.
 
I referred to the Chinese government not the
Chinese people in general. And I'm an entrepreneur.
 
Can we focus on the software and documentation?
 
 
Brian
Ebenezer Enterprises - "The fear of the L-RD is the
beginning of wisdom." Proverbs 9:10
 
https://webEbenezer.net
Keith Thompson <Keith.S.Thompson+u@gmail.com>: Dec 15 06:42PM -0800


>>For many years before that it has been on our money.
 
> Again, you display your ignorance. July 30, 1956. 64 years ago.
 
> https://www.politico.com/story/2018/07/30/in-god-we-trust-becomes-nations-motto-july-30-1956-741016
 
Neither the date when it became the US national motto nor the date
when it first appeared on US money has anything to do with C++.
 
--
Keith Thompson (The_Other_Keith) Keith.S.Thompson+u@gmail.com
Working, but not speaking, for Philips Healthcare
void Void(void) { Void(); } /* The recursive call of the void */
Brian Wood <woodbrian77@gmail.com>: Dec 15 07:48PM -0800

On Tuesday, December 15, 2020 at 6:07:52 PM UTC-6, Scott Lurndal wrote:
 
> >For many years before that it has been on our money.
> Again, you display your ignorance. July 30, 1956. 64 years ago.
 
> https://www.politico.com/story/2018/07/30/in-god-we-trust-becomes-nations-motto-july-30-1956-741016
 
I'm looking at a 1923 silver dollar. On the front it says:
LIBERTY and "IN GOD WE TRVST". The 'v' has something to do
with Latin.
"Chris M. Thomasson" <chris.m.thomasson.1@gmail.com>: Dec 15 08:07PM -0800

On 12/15/2020 7:48 PM, Brian Wood wrote:
 
> I'm looking at a 1923 silver dollar. On the front it says:
> LIBERTY and "IN GOD WE TRVST". The 'v' has something to do
> with Latin.
 
Out of many, one?
David Brown <david.brown@hesbynett.no>: Dec 16 09:08AM +0100

On 16/12/2020 01:47, Brian Wood wrote:
 
> Can we focus on the software and documentation?
 
Please do (with the emphasis on the software).
 
That means /you/ need to drop the politics, conspiracy theories, hero
worship of nutcakes (your own term), religion, megalomania fantasies,
adverts for your company, adverts for your software, begging, wild and
unsubstantiated claims about software models, complaints about language,
and so on.
 
Stick to technical posts about /specific/ points in software and C++,
without getting side-tracked, and perhaps you'll get a little of the
help you want.
olcott <NoOne@NoWhere.com>: Dec 15 06:23PM -0600

On 12/15/2020 5:59 PM, Ben Bacarisse wrote:
> arguments in both cases. I'm discounting that because it's obviously
> not allowed by the challenge wording, and you confirmed that no such
> trickery is taking place long ago in the reply to, IIRC, Mike Terry.
 
Here is the architecture that I am working on physically implementing in
the x86utm (x86 based universal Turing machine equivalent) operating
system.
 
Whenever a function is called by Halts() and it would not halt Halts()
returns 0. This is like wrapping a possible divide by zero error with a
try-catch block, the otherwise abnormal termination is caught.
 
// This part is fully operational
int main()
{
u32 Input_Halts = Halts((u32)Confound_Halts, (u32)Confound_Halts);
Output("Input_Halts = ", Input_Halts);
}
 
Whenever a function is not called by Halts() and it would not halt the
halt deciding operating system reports a "non-halting" error. This is
like divide by zero error that is NOT wrapped with a try-catch block,
the program abnormally terminates:
 
int main()
{
HERE: goto HERE;
}
 
int main()
{
Confound_Halts((u32)Confound_Halts);
}
 
This is the universal not-halting decision criteria:
 
On 11/27/2020 9:02 PM, Ben Bacarisse wrote:
> A computation that would not halt if its simulation were not
> halted is indeed a non-halting computation.
 
On Saturday, November 28, 2020 at 2:00:28 PM UTC-8, olcott wrote:
> Every computation that would not halt if its simulation
> were not halted is by logical necessity a non-halting computation.
 
The halting decision criteria is simply that the input has actually halted.
 
--
Copyright 2020 Pete Olcott
 
"Great spirits have always encountered violent opposition from mediocre
minds." Einstein
olcott <NoOne@NoWhere.com>: Dec 15 07:46PM -0600

On 12/15/2020 7:11 PM, Ben Bacarisse wrote:
>>> the above function; or
 
>>> (2) Halts(Confound_Halts, Confound_Halts) does not return when called in
>>> the above function.
 
(3) When Halts(Confound_Halts, Confound_Halts) is called by main() this
is similar to wrapping a divide by zero error with a try catch block.
Halts() returns a value of 0 or 1.
 
When Confound_Halts(Confound_Halts) is called by main() this is similar
to divide by zero error that has not been caught by a try-catch block.
The operating system abnormally terminates the application with an
[infinite execution] @ machine address fatal error.
 
 
> I'm not interested in that. Can I take it that you agree you have not
> met the challenge? I'm sure everyone else will take your non-reply in
> that way but I'd rather you were explicit about it.
 
Your challenge was a false dichotomy as pointed out above.
 
 
--
Copyright 2020 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)