Rocksolid Light

Welcome to novaBBS (click a section below)

mail  files  register  newsreader  groups  login

Message-ID:  

The sum of the Universe is zero.


devel / comp.lang.c++ / Termination Analyzer H correctly determines that its "impossible" input never halts

SubjectAuthor
o Termination Analyzer H correctly determines that its "impossible"olcott

1
Termination Analyzer H correctly determines that its "impossible" input never halts

<u61udt$2afih$3@dont-email.me>

  copy mid

https://www.novabbs.com/devel/article-flat.php?id=310&group=comp.lang.c%2B%2B#310

  copy link   Newsgroups: comp.lang.c++
Path: i2pn2.org!i2pn.org!eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: polco...@gmail.com (olcott)
Newsgroups: comp.lang.c++
Subject: Termination Analyzer H correctly determines that its "impossible"
input never halts
Date: Sat, 10 Jun 2023 08:39:08 -0500
Organization: A noiseless patient Spider
Lines: 39
Message-ID: <u61udt$2afih$3@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Injection-Date: Sat, 10 Jun 2023 13:39:09 -0000 (UTC)
Injection-Info: dont-email.me; posting-host="0645e05057d55a55fb9d2d60138c3ade";
logging-data="2440785"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1+iqVAlEJ8DkexChYOuOrUY"
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:102.0) Gecko/20100101
Thunderbird/102.11.2
Cancel-Lock: sha1:1DHHVAiR9wUTvCpgl8YW9jtsM4c=
Content-Language: en-US
 by: olcott - Sat, 10 Jun 2023 13:39 UTC

01 typedef int (*ptr)(); // pointer to int function
02 int H(ptr x, ptr y) // uses x86 emulator to simulate its input
03
04 int D(ptr x)
05 {
06 int Halt_Status = H(x, x);
07 if (Halt_Status)
08 HERE: goto HERE;
09 return Halt_Status;
10 }
11
12 void main()
13 {
14 H(D,D);
15 }

When H is a simulating termination analyzer based on an x86 emulator
within the x86utm operating system this is the execution trace of the
above code:

Line 14: main() calls H(D,D) that simulates D(D)

keeps repeating:
Line 06: simulated D(D) calls simulated H(D,D) that simulates D(D) ...

Simulation invariant:
D correctly simulated by H never reaches its own Line 09.

This enables H to abort its simulation of D and correctly report that
(its input) D correctly simulated by H never halts. The above is fully
operational code within the x86utm operating system.
https://github.com/plolcott/x86utm

*Broadening the Practical Scope of Software Termination Analysis*
https://www.researchgate.net/publication/369971402_Broadening_the_Practical_Scope_of_Software_Termination_Analysis

--
Copyright 2023 Olcott "Talent hits a target no one else can hit; Genius
hits a target no one else can see." Arthur Schopenhauer

1
server_pubkey.txt

rocksolid light 0.9.8
clearnet tor