Tuesday, March 2, 2021

Digest for comp.lang.c++@googlegroups.com - 18 updates in 3 topics

olcott <NoOne@NoWhere.com>: Mar 01 09:32PM -0600

On 3/1/2021 9:05 PM, olcott wrote:
>> 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.
 
int Simulate_3(u32 P, u32 I);
Same as Simulate_2() except examines the saved execution trace
immediately after emulating each x86 language instruction to determine
whether or not this input specifies infinite recursion.
 
It should be self-evident that whenever any of these versions is
substituted into the body of H_Hat() that H_Hat() remains infinitely
recursive.
 
It should be self-evident that Simulate_3() can easily determine the
infinite recursion of H_Hat() on the basis its execution trace.
 
 
 
--
Copyright 2021 Pete Olcott
 
"Great spirits have always encountered violent opposition from mediocre
minds." Einstein
olcott <NoOne@NoWhere.com>: Mar 02 09:29AM -0600

On 3/2/2021 6:02 AM, Ben Bacarisse wrote:
 
> You can find your mistake simply by finding the first of those steps
> where you move from something boring to something you'd like to boast
> about. That is the step at which you introduce the trick.
 
#include <stdint.h>
#define u8 uint8_t
#define u32 uint32_t
#define u16 uint16_t
 
u32 Halts(u32 P, u32 I)
{
((void(*)(int))P)(I);
return 1;
}
 
void H_Hat(u32 P)
{
u32 Input_Halts = Halts(P, P);
if (Input_Halts)
HERE: goto HERE;
return;
}
 
int main()
{
u32 Input_Would_Halt = Halts((u32)H_Hat, (u32)H_Hat);
Output("Input_Would_Halt = ", Input_Would_Halt);
}
 
Because the execution trace shown below shows that H_Hat() invokes
Halts() with the same data two times in sequence we can conclude that
H_Hat() is invoked in infinite recursion entirely based on the execution
trace of H_Hat() and the assumption that Halts() does nothing besides
execute or emulate its input.
 
When Halts() is augmented so that it can see that H_Hat() invokes it two
times in sequence with the same data then Halts() can determine that
H_Hat() is infinitely recursive.
 
_Halts()
[000004af](01) 55 push ebp
[000004b0](02) 8bec mov ebp,esp
[000004b2](03) 8b450c mov eax,[ebp+0c]
[000004b5](01) 50 push eax
[000004b6](03) ff5508 call dword [ebp+08]
[000004b9](03) 83c404 add esp,+04
[000004bc](05) b801000000 mov eax,00000001
[000004c1](01) 5d pop ebp
[000004c2](01) c3 ret
 
_H_Hat()
[0000088f](01) 55 push ebp
[00000890](02) 8bec mov ebp,esp
[00000892](01) 51 push ecx
[00000893](03) 8b4508 mov eax,[ebp+08]
[00000896](01) 50 push eax ; 2nd Param
[00000897](03) 8b4d08 mov ecx,[ebp+08]
[0000089a](01) 51 push ecx ; 1st Param
[0000089b](05) e80ffcffff call 000004af ; Halts(P,P)
[000008a0](03) 83c408 add esp,+08
[000008a3](03) 8945fc mov [ebp-04],eax
[000008a6](04) 837dfc00 cmp dword [ebp-04],+00
[000008aa](02) 7402 jz 000008ae
[000008ac](02) ebfe jmp 000008ac
[000008ae](02) 8be5 mov esp,ebp
[000008b0](01) 5d pop ebp
[000008b1](01) c3 ret
 
_main()
[000008bf](01) 55 push ebp
[000008c0](02) 8bec mov ebp,esp
[000008c2](01) 51 push ecx
[000008c3](05) 688f080000 push 0000088f
[000008c8](05) 688f080000 push 0000088f
[000008cd](05) e8ddfbffff call 000004af
[000008d2](03) 83c408 add esp,+08
[000008d5](03) 8945fc mov [ebp-04],eax
[000008d8](03) 8b45fc mov eax,[ebp-04]
[000008db](01) 50 push eax
[000008dc](05) 680b030000 push 0000030b
[000008e1](05) e869faffff call 0000034f
[000008e6](03) 83c408 add esp,+08
[000008e9](02) 33c0 xor eax,eax
[000008eb](02) 8be5 mov esp,ebp
[000008ed](01) 5d pop ebp
[000008ee](01) c3 ret
 
 
Push instructions have already pushed the value shown in their in the
third column. The two push instructions preceding the call to Simulate()
are its second and first parameters respectively.
 
Columns
(1) Machine address of instruction
(2) Machine address of top of stack
(3) Value of top of stack after instruction executed
(4) Number of bytes of machine code
(5) Machine language bytes
(6) Assembly language text
...[000008bf][00011208][00000000](01) 55 push ebp
...[000008c0][00011208][00000000](02) 8bec mov ebp,esp
...[000008c2][00011204][00000000](01) 51 push ecx
...[000008c3][00011200][0000088f](05) 688f080000 push 0000088f
...[000008c8][000111fc][0000088f](05) 688f080000 push 0000088f
...[000008cd][000111f8][000008d2](05) e8ddfbffff call 000004af
...[0000088f][000111e8][000111f4](01) 55 push ebp
...[00000890][000111e8][000111f4](02) 8bec mov ebp,esp
...[00000892][000111e4][00000000](01) 51 push ecx
...[00000893][000111e4][00000000](03) 8b4508 mov eax,[ebp+08]
...[00000896][000111e0][0000088f](01) 50 push eax ; 2nd Param
...[00000897][000111e0][0000088f](03) 8b4d08 mov ecx,[ebp+08]
...[0000089a][000111dc][0000088f](01) 51 push ecx ; 1st Param
 
Call Halts(0000088f, 0000088f);
...[0000089b][000111d8][000008a0](05) e80ffcffff call 000004af
...[0000088f][000111c8][000111d4](01) 55 push ebp
...[00000890][000111c8][000111d4](02) 8bec mov ebp,esp
...[00000892][000111c4][0000088f](01) 51 push ecx
...[00000893][000111c4][0000088f](03) 8b4508 mov eax,[ebp+08]
...[00000896][000111c0][0000088f](01) 50 push eax ; 2nd Param
...[00000897][000111c0][0000088f](03) 8b4d08 mov ecx,[ebp+08]
...[0000089a][000111bc][0000088f](01) 51 push ecx ;1st Param
 
Call Halts(0000088f, 0000088f);
...[0000089b][000111b8][000008a0](05) e80ffcffff call 000004af
 
It continues to execute the same portion of H_Hat() sequence above
 
--
Copyright 2021 Pete Olcott
 
"Great spirits have always encountered violent opposition from mediocre
minds." Einstein
om@iki.fi (Otto J. Makela): Mar 02 06:36PM +0200

I'm a bit late to the discussion, but this sounds a lot like you're
trying to overturn Turing's proof that that a general algorithm to solve
the halting problem for all possible program-input pairs cannot exist.
--
/* * * Otto J. Makela <om@iki.fi> * * * * * * * * * */
/* Phone: +358 40 765 5772, ICBM: N 60 10' E 24 55' */
/* Mail: Mechelininkatu 26 B 27, FI-00100 Helsinki */
/* * * Computers Rule 01001111 01001011 * * * * * * */
olcott <NoOne@NoWhere.com>: Mar 02 11:22AM -0600

On 3/2/2021 10:36 AM, Otto J. Makela wrote:
> I'm a bit late to the discussion, but this sounds a lot like you're
> trying to overturn Turing's proof that that a general algorithm to solve
> the halting problem for all possible program-input pairs cannot exist.
 
Yes. The key brand new insight that I had about this proof is that the
actual execution trace never reaches the undecidable portion, thus
making the conventional halting problem counter-examples {Linz, Sipser,
Kozen} decidable.
 
// P has the machine address of H_Hat()
void H_Hat(u32 P)
{
u32 Input_Halts = Halts(P, P);
if (Input_Halts)
HERE: goto HERE;
return;
}
 
"It looks like the original specification provided in
the Linz text may be infinitely recursive in that each
TM requires its own input."
 
Self Modifying Turing Machine (SMTM) Solution to the Halting Problem
(concrete example) August 2016
https://www.researchgate.net/publication/307509556_Self_Modifying_Turing_Machine_SMTM_Solution_to_the_Halting_Problem_concrete_example
 
 
Infinitely Recursive input on HP Proofs (March 11, 2017)
https://groups.google.com/g/comp.theory/c/NcFS02hKs1U/m/PlBF-1LRBAAJ
 
 
 
Linz, Peter 1990. An Introduction to Formal Languages and Automata.
Lexington/Toronto: D. C. Heath and Company (315-320)
 
Sipser, Michael 1997. Introduction to the Theory of Computation. Boston:
PWS Publishing Company (165-167)
 
Kozen, Dexter 1997. Automata and Computability. New York:
Springer-Verlag. (231-234).
 
 
--
Copyright 2021 Pete Olcott
 
"Great spirits have always encountered violent opposition from mediocre
minds." Einstein
Kaz Kylheku <563-365-8930@kylheku.com>: Mar 02 05:46PM

>> the halting problem for all possible program-input pairs cannot exist.
 
> Yes. The key brand new insight that I had about this proof is that the
> actual execution trace never reaches the undecidable portion, thus
 
The program has no "undecidable portion". We know perfectly well
whether it terminates or not, because it is trivial.
 
All that is undecidable, in the context of computability, is the problem
of determining whether any program whatsoever on any input terminates.
 
"Undecidable
 
> making the conventional halting problem counter-examples {Linz, Sipser,
> Kozen} decidable.
 
Each such example is individually decidable, and everybody knows this.
 
No example of anything even moderately hard to decide is ever presented
in the proofs.
 
> HERE: goto HERE;
> return;
> }
 
Everyone, including probably most CS undergrads by the time they reach
senior year, that if Halts decides that it's a good idea to "decide"
halting by simply running the code, runaway recursion will occur.
 
When I first encountered the halting problem concept, I remember that
the text I was reading mentioned this: if the decision function jus
executes the function, it precipitates into infinite regress, and
therefore does not terminate, in which case there is no decision.
 
You have not discovered anything.
 
Also, the idea of an insruction stream that has no branches corresponds
to the well-known concept of a basic block in program control flow
analysis, used in compilers. Again, something even CS undergrads know by
the time they graduate.
 
--
TXR Programming Language: http://nongnu.org/txr
Cygna: Cygwin Native Application Library: http://kylheku.com/cygnal
olcott <NoOne@NoWhere.com>: Mar 02 01:00PM -0600

On 3/2/2021 11:46 AM, Kaz Kylheku wrote:
>> actual execution trace never reaches the undecidable portion, thus
 
> The program has no "undecidable portion". We know perfectly well
> whether it terminates or not, because it is trivial.
 
Daryl McCullough
https://groups.google.com/g/comp.theory/c/wgJjJR78FaU/m/_eWPqsSS8bEJ
I can finally give credit where credit is due. Daryl McCullough was the
one that originally came up with this analogy in March of 2012.
 
When we ask Bill: Is your answer to this question "no" ?
Bill cannot possibly provide a correct answer because both answers of
"yes" and "no" form a contradiction.
 
In this same way Halts() cannot possibly provide a correct return value
indicating halting / non halting to H_Hat().
 
// P has the machine address of H_Hat()
void H_Hat(u32 P)
{
u32 Input_Halts = Halts2(P, P);
if (Input_Halts)
HERE: goto HERE;
return;
}
 
The brand new insight that I documented that I came up with in 2016 was
that a halt decider that examines the simulation of its input as the
basis for its halting decision would never reach the point where it
returns any value to H_Hat().
 
 
--
Copyright 2021 Pete Olcott
 
"Great spirits have always encountered violent opposition from mediocre
minds." Einstein
Kaz Kylheku <563-365-8930@kylheku.com>: Mar 02 07:35PM

["Followup-To:" header set to comp.lang.c.]
 
> When we ask Bill: Is your answer to this question "no" ?
> Bill cannot possibly provide a correct answer because both answers of
> "yes" and "no" form a contradiction.
 
Since we are not part of the program, there is no contradiction in our
answer when we decide whether the example terminates or not.
 
If the example terminates and gives a result, that result may have
the interpretation that it is wrong; i.e. a contradiction.
 
If the program's is taken to mean "I do not halt", than that is wrong;
That has no bearing on the fact that the program has halted, and
that our own answer "it has halted" is right.
 
The decider is only shown wrong on that one example, not that it's
on all inputs. The decider is not absolutely contradicted.
 
> that a halt decider that examines the simulation of its input as the
> basis for its halting decision would never reach the point where it
> returns any value to H_Hat().
 
This is undergrad-level obvious that if the decider, instead of
implementing some actual decision algorithm, simply executes the input,
then if that input does not terminate, that "decision" will also not
terminate, and that it is victim to infinite regress.
 
The first time I learned about the halting problem, it was in a textbook
which noted this obvious fact.
 
You should be more humble in your claims that you have some brand new
result.
 
--
TXR Programming Language: http://nongnu.org/txr
Cygna: Cygwin Native Application Library: http://kylheku.com/cygnal
olcott <NoOne@NoWhere.com>: Mar 02 01:50PM -0600

On 3/2/2021 1:00 PM, olcott wrote:
>>> actual execution trace never reaches the undecidable portion, thus
 
>> The program has no "undecidable portion". We know perfectly well
>> whether it terminates or not, because it is trivial.
 
There is a much earlier attribution to the same person:
 
sci.logic Daryl McCullough June 25, 2004
On Friday, June 25, 2004 at 6:30:39 PM UTC-5, Daryl McCullough wrote:
> yes/no answer to the following question:
> Will Jack's answer to this question be no?
> Jack can't possibly give a correct yes/no answer to the question.
 
https://groups.google.com/g/sci.logic/c/4kIXI1kxmsI/m/hRroMoQZx2IJ
 
Jack cannot possibly provide a correct answer because both answers of
"yes" and "no" form a contradiction.
 
 
--
Copyright 2021 Pete Olcott
 
"Great spirits have always encountered violent opposition from mediocre
minds." Einstein
Kaz Kylheku <563-365-8930@kylheku.com>: Mar 02 07:57PM


> https://groups.google.com/g/sci.logic/c/4kIXI1kxmsI/m/hRroMoQZx2IJ
 
> Jack cannot possibly provide a correct answer because both answers of
> "yes" and "no" form a contradiction.
 
What you're perpetually missing is that a mathematical or
computatational function isn't Jack. If it gives a "yes" answer for some
input, it can give no other answer. Functions don't have the choice of
re-evaluating their answer and changing it.
 
Much of your rhetoric in this direction is laced with
anthropomorphic fallacy.
 
If we edit a function to give a different answer for the same input,
we are creating a different function. Since the input is the function
itself, the input has changed too!
 
You continue to be confused by this point; your work history consists
of producing different versions of code under the same names, taking
different inputs under the same name, and speaking about it in terms as
if they are all one thing.
olcott <NoOne@NoWhere.com>: Mar 02 02:20PM -0600

On 3/2/2021 1:57 PM, Kaz Kylheku wrote:
> of producing different versions of code under the same names, taking
> different inputs under the same name, and speaking about it in terms as
> if they are all one thing.
 
// P has the machine address of H_Hat()
void H_Hat(u32 P)
{
u32 Input_Halts = Halts(P, P);
if (Input_Halts)
HERE: goto HERE;
return;
}
 
Although you may endlessly dodge this point it remains perfectly true
that both possible Boolean return values from Halts() to H_Hat() would
be made incorrect on the basis that they are contradicted.
 
It is also a verified fact that these return values are contradicted in
the exact same pathological self-reference(Olcott 2004) way that makes
it impossible for Jack to provide a correct answer to this question:
Is the answer to this question no?
 
 
 
 
 
--
Copyright 2021 Pete Olcott
 
"Great spirits have always encountered violent opposition from mediocre
minds." Einstein
Keith Thompson <Keith.S.Thompson+u@gmail.com>: Mar 02 12:57PM -0800

> On 2021-03-02, olcott <NoOne@NoWhere.com> wrote:
[more of the same]
 
Kaz, olcott's article to which you replied was posted to
comp.theory, comp.lang.c, comp.lang.c++, and comp.software-eng,
with followups directed to comp.lang.c. Your followup ignored the
"Followup-To: comp.theory" header line and cross-posted to all
four newsgroups.
 
Is your newsreader buggy, or are you deliberately making
inappropriate cross-posts, or is something else going on?
 
I've cross-posted this article and set followups to comp.theory only.
 
--
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 */
"Chris M. Thomasson" <chris.m.thomasson.1@gmail.com>: Mar 01 06:52PM -0800

Fwiw, here is a simple implementation of a seqlock under Relacy Race
Detector. Now, this needs std::memory_order_seq_cst in order to get it
to work, however, I am trying to find a way around that nasty membar.
However, the ct_seqlock::read_enter/read_try_leave functions only does
loads, but uses that damn seq_cst. The idea is to use this for a
distributed poor mans RCU where there would be a seqlock per thread. It
is crucial that a reader does not mutate state on a remote thread. So,
loads are very important here.
 
 
Here is the Relacy code:
__________________________________
// Chris M. Thomassons SeqLock Test
 
 
//#define RL_DEBUGBREAK_ON_ASSERT
//#define RL_MSVC_OUTPUT
//#define RL_FORCE_SEQ_CST
#include <relacy/relacy_std.hpp>
#include <cstdio>
#include <cstddef>
 
 
 
#if ! defined (NDEBUG)
# define DBG_PRINTF(e) std::printf e
#else
# define DBG_PRINTF(e) ((void)0)
Posted by at

No comments:

Post a Comment

Subscribe to: Post Comments (Atom)