Monday, November 23, 2020

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

olcott <NoOne@NoWhere.com>: Nov 22 07:24PM -0600

The following shows exactly how the Peter Linz H would correctly decide
halting on the Peter Linz Ĥ. This is fully operational code that has
been executed in the x86utm operating system that I wrote.
 
To make the Linz counter-example conform to the standard halting problem
counter-examples the input is not copied as it is in Linz.
 
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.
 
x86 language ≡ von Neumann architecture ≡ UTM ≡ RASP Machine
The x86 language is computationally equivalent to a UTM for all
computations that do not require more memory than is available.
 
Recursion can be directly simulated by a UTM that simulates its own
Turing machine Description. Infinite recursion would repeat the same
state transitions every time the UTM simulates its own Turing machine
Description.
 
// Defined at the bottom of page 319 of Linz
void Ĥ(u32 P)
{
u32 Input_Halts = H(P, P);
if (!Input_Halts)
HALT
else
HERE: goto HERE;
}
 
 
int main()
{
u32 P = (u32)Ĥ;
H(P, P);
HALT;
}
 
 
Disassembled x86 machine language of the above pair of C functions.
 
Ĥ()
[000004f7](01) 55 push ebp
[000004f8](02) 8bec mov ebp,esp
[000004fa](01) 51 push ecx
[000004fb](03) 8b4508 mov eax,[ebp+08]
[000004fe](01) 50 push eax
[000004ff](03) 8b4d08 mov ecx,[ebp+08]
[00000502](01) 51 push ecx
[00000503](05) e86ffeffff call 00000377
[00000508](03) 83c408 add esp,+08
[0000050b](03) 8945fc mov [ebp-04],eax
[0000050e](04) 837dfc00 cmp dword [ebp-04],+00
[00000512](02) 7403 jz 00000517
[00000514](01) f4 hlt
[00000515](02) eb02 jmp 00000519
[00000517](02) ebfe jmp 00000517
[00000519](02) 8be5 mov esp,ebp
[0000051b](01) 5d pop ebp
[0000051c](01) c3 ret
 
_main()
[00000527](01) 55 push ebp
[00000528](02) 8bec mov ebp,esp
[0000052a](01) 51 push ecx
[0000052b](07) c745fcf7040000 mov [ebp-04],000004f7
[00000532](03) 8b45fc mov eax,[ebp-04]
[00000535](01) 50 push eax
[00000536](03) 8b4dfc mov ecx,[ebp-04]
[00000539](01) 51 push ecx
[0000053a](05) e838feffff call 00000377
[0000053f](03) 83c408 add esp,+08
[00000542](01) f4 hlt
[00000543](02) 8be5 mov esp,ebp
[00000545](01) 5d pop ebp
[00000546](01) c3 ret
 
 
 
Output_Debug_Trace() [00010abc] size(148) capacity(65536)
[00000527](01) 55 push ebp
[00000528](02) 8bec mov ebp,esp
[0000052a](01) 51 push ecx
[0000052b](07) c745fcf7040000 mov [ebp-04],000004f7
[00000532](03) 8b45fc mov eax,[ebp-04]
[00000535](01) 50 push eax
[00000536](03) 8b4dfc mov ecx,[ebp-04]
[00000539](01) 51 push ecx
[0000053a](05) e838feffff call 00000377
[000004f7](01) 55 push ebp
[000004f8](02) 8bec mov ebp,esp
[000004fa](01) 51 push ecx
[000004fb](03) 8b4508 mov eax,[ebp+08]
[000004fe](01) 50 push eax
[000004ff](03) 8b4d08 mov ecx,[ebp+08]
[00000502](01) 51 push ecx
[00000503](05) e86ffeffff call 00000377
[000004f7](01) 55 push ebp
[000004f8](02) 8bec mov ebp,esp
[000004fa](01) 51 push ecx
[000004fb](03) 8b4508 mov eax,[ebp+08]
[000004fe](01) 50 push eax
[000004ff](03) 8b4d08 mov ecx,[ebp+08]
[00000502](01) 51 push ecx
[00000503](05) e86ffeffff call 00000377
25 instructions
 
The above is where the halt decider aborts the whole Ĥ(Ĥ) invocation
sequence because the halt decider detects infinite recursion.
 
In this case infinite recursion is a function call to the same function
from the same machine address without any conditional branch
instructions that would terminate this recursion.
 
 
--
Copyright 2020 Pete Olcott
 
"Great spirits have always encountered violent opposition from mediocre
minds." Einstein
olcott <NoOne@NoWhere.com>: Nov 23 03:29PM -0600

On 11/23/2020 3:02 PM, Mike Terry wrote:
> intstructions, but you've just silently snipped them from the trace
> output you've shown.  There are HUGE gaps in your trace!!
 
> Mike.
 
Unless we maintain a line-of-demarcation between the halt decider and
its input pathological self-reference(Olcott 2004) makes the halting
problem have undecidable inputs in the same way that the Liar Paradox is
neither true nor false.
 
https://groups.google.com/g/comp.theory/c/RO9Z9eCabeE/m/Ka8-xS2rdEEJ
 
Instead of asking the question: Does the input halt on its input?
that is subject to pathological self-reference.
 
We ask the question: Does the execution of the input have to be aborted
to prevent its infinite execution?
 
When we ask this latter question then we can ignore all of the
conditional branch instructions that are in the halt decider and only
pay attention to the ones that are in the input.
 
The input to H will be the description (encoded in some form)
of M, say WM, as well as the input w. The requirement is then
that, given any (WM, w), the Turing machine H will halt with
either a yes or no answer.
 
H.q0 wMw ⊢* H.yes if M applied to w halts, and
H.q0 wMw ⊢* H.no if M applied to w does not halt.
(Linz 1990:318)
 
Any input TMD that would never halt unless a UTM stopped simulating it
expresses behavior that is not halting behavior.
 
Linz, Peter 1990. An Introduction to Formal Languages and Automata.
Lexington/Toronto: D. C. Heath and Company.
 
http://www.liarparadox.org/Peter_Linz_HP(Pages_315-320).pdf
 
 
--
Copyright 2020 Pete Olcott
 
"Great spirits have always encountered violent opposition from mediocre
minds." Einstein
olcott <NoOne@NoWhere.com>: Nov 23 07:52AM -0600

On 11/20/2020 9:30 PM, Mike Terry wrote:
> stuff...]
 
> Regards,
> Mike.
 
Machines of the pattern of H_Hat can be generally decided to be
infinitely recursive whenever they invoke the same function from the
same machine address and there are no intervening condition branch
instructions in-between that would break this cycle of infinite recursion:
 
// call to Halts from H_Hat
[00000503](05) e86ffeffff call 00000377
[000004f7](01) 55 push ebp
[000004f8](02) 8bec mov ebp,esp
[000004fa](01) 51 push ecx
[000004fb](03) 8b4508 mov eax,[ebp+08]
[000004fe](01) 50 push eax
[000004ff](03) 8b4d08 mov ecx,[ebp+08]
[00000502](01) 51 push ecx
 
// call to Halts from H_Hat
[00000503](05) e86ffeffff call 00000377
 
All of the details of this analysis are shown here:
 
On Sunday, November 22, 2020 at 7:24:48 PM UTC-6, olcott wrote:
[It is known that a correct halt decider must return false (in this
case)[V4](Linz)]
https://groups.google.com/g/comp.theory/c/aiXoRwqxJgE/m/2GlNMjitAAAJ
 
--
Copyright 2020 Pete Olcott
 
"Great spirits have always encountered violent opposition from mediocre
minds." Einstein
"Öö Tiib" <ootiib@hot.ee>: Nov 22 10:50PM -0800

On Friday, 20 November 2020 at 20:11:49 UTC+2, Tim Rentsch wrote:
> setting it to NULL, which means the starting check needs to check
> two different conditions. So thank you for the idea, and kudos
> for discovering this nice improvement.
 
Great. It can reduce moves to minimum when moves are pricey.
I have so far kept such complex data in memory non-movable.
Even when initially there is only one order then later there other
ways to order are often needed. Then sorted external arrays of
indexes or pointers or intrusive lists and sets can be used instead
of actual physical sorting. Keeping expensive to move
values at one place forever makes usage of several indexing
ways cheaper to keep and less error-prone.
But that may be also preliminary pessimization and
violation of YAGNI when applied too generally.
Christian Gollwitzer <auriocus@gmx.de>: Nov 23 07:34AM +0100

Am 21.11.20 um 12:34 schrieb Bonita Montero:
> I want an API to list the supproted locales of my implementation.
 
If it is "locale -a" as suggested by others, then why not checking the
source code of the locale command to see what this does?
 
Christian
"Öö Tiib" <ootiib@hot.ee>: Nov 22 09:22PM -0800

> On Sunday, November 22, 2020 at 3:46:28 PM UTC-6, Mr Flibble wrote:
 
> Either try to be helpful or go back to your threads.
 
When you need help then post description of problem that you have,
and/or concrete article or whatever. Such duckduckgo searches of videos
of whole conference in YouTube are too out of focus wide.
 
About your middleware writer lot of questions have raised over the
years but have any ended as issues in some issue tracker? It seems
that you just want to advertise it.
Take that <https://isocpp.org/wiki/faq/serialization> and at least write
down somewhere what kind of problems raised there your library
resolves and how. It has been around all that time.
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)