Path: ...!weretis.net!feeder9.news.weretis.net!feeder8.news.weretis.net!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: olcott <polcott333@gmail.com>
Newsgroups: comp.lang.c++,comp.lang.c
Subject: D correctly simulated by pure function H cannot possibly reach its
 own line 06---TOC divergence
Followup-To: comp.theory
Date: Sat, 25 May 2024 14:41:07 -0500
Organization: A noiseless patient Spider
Lines: 115
Message-ID: <v2tesk$30u1r$1@dont-email.me>
References: <v2ns85$1rd65$1@dont-email.me> <v2s46t$2pj9q$2@dont-email.me>
 <HOGdnVr9MpKtlc_7nZ2dnZfqn_qdnZ2d@brightview.co.uk>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Sat, 25 May 2024 21:41:09 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="010db72b80f31f696ef17c51994f71bb";
	logging-data="3176507"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1/gNNwmFsFLJ9N46V3+SdXx"
User-Agent: Mozilla Thunderbird
Cancel-Lock: sha1:W0VNyRFRdHRQu6PYCZU58CRdMFU=
Content-Language: en-US
In-Reply-To: <HOGdnVr9MpKtlc_7nZ2dnZfqn_qdnZ2d@brightview.co.uk>
Bytes: 6196

On 5/25/2024 10:48 AM, Mike Terry wrote:
> On 25/05/2024 08:32, Fred. Zwarts wrote:
>> Op 23.mei.2024 om 18:52 schreef olcott:
>>> typedef int (*ptr)();  // ptr is pointer to int function in C
>>> 00       int H(ptr p, ptr i);
>>> 01       int D(ptr p)
>>> 02       {
>>> 03         int Halt_Status = H(p, p);
>>> 04         if (Halt_Status)
>>> 05           HERE: goto HERE;
>>> 06         return Halt_Status;
>>> 07       }
>>> 08
>>> 09       int main()
>>> 10       {
>>> 11         H(D,D);
>>> 12         return 0;
>>> 13       }
>>>
>>> The above template refers to an infinite set of H/D pairs where D is
>>> correctly simulated by pure function H. This was done because many
>>> reviewers used the shell game ploy to endlessly switch which H/D was
>>> being referred to.
>>>
>>> *Correct Simulation Defined*
>>> This is provided because every reviewer had a different notion of
>>> correct simulation that diverges from this notion.
>>>
>>> In the above case a simulator is an x86 emulator that correctly emulates
>>> at least one of the x86 instructions of D in the order specified by the
>>> x86 instructions of D.
>>>
>>> This may include correctly emulating the x86 instructions of H in the
>>> order specified by the x86 instructions of H thus calling H(D,D) in
>>> recursive simulation.
>>>
>>> *Execution Trace*
>>> Line 11: main() invokes H(D,D); H(D,D) simulates lines 01, 02, and 03 of
>>> D. This invokes H(D,D) again to repeat the process in endless recursive
>>> simulation.
>>>
>>
>> Olcott's own words are that the simulation of D never reaches past 
>> line 03. So the lines following line 03 do not play a role and, 
>> therefore, can be removed without changing the claim. This leads to:
>>
>> typedef int (*ptr)();  // ptr is pointer to int function in C
>> 00       int H(ptr p, ptr i);
>> 01       int D(ptr p)
>> 02       {
>> 03         return H(p, p);
>> 04       }
>> 05
>> 06       int main()
>> 07       {
>> 08         H(D,D);
>> 09         return 0;
>> 10       }
>>
> 
> Correct - as far as this specific thread is concerned.  But PO's H and P 
> are intended to be part of a larger argument supposedly refuting the 
> standard halting problem (HP) proof (that no TM is a halt decider), e.g. 
> as covered in the Linz book.  PO has created an extract of that proof as 
> a PDF that he sometimes links to.
> 
> Also note that PO's claim (in this specific thread) is that the 
> *simulation* of D never reaches past line 03.  That is not saying that 
> the *computation* D(D) never proceeds past line 3 or that D(D) never 
> halts.  (This is important in the wider HP proof context.  PO is deeply 
> confused on this point.)

I read and reread what is said several times to make sure that I
get the exact meaning of exactly what is said. *I missed it this time*

Since *Mike is my most important reviewer* and this one key point
has been the only basis for any rebuttal in the last two years I
am addressing it here. *Followups have been sent to comp.theory*

I must diverge a tad bit from the pure semantics of the c programming
language to address an error by my reviewers regarding the theory of
computation notion of computable function.

*Computable functions* are the basic objects of study in computability
theory. Computable functions are the formalized analogue of the
intuitive notion of algorithms, in the sense that a function is
computable if there exists an algorithm that can do the job of the
function, i.e. given an input of the function domain it can return the
corresponding output. https://en.wikipedia.org/wiki/Computable_function

When computable function H reports on the behavior of its input it must
report on:

D correctly simulated by pure function H cannot possibly reach its own 
line 06

Computable functions ARE STRICTLY NOT ALLOWED TO REPORT ON THE BEHAVIOR
NON-INPUTS. Computable functions ARE NEVER ALLOWED TO REPORT ON THE
BEHAVIOR OF THE COMPUTATION THAT THEY THEMSELVES ARE CONTAINED WITHIN.

In technical terms this means that Turing machines are never allowed
to report on the behavior of Turing machines. They are only allowed
to report on the behavior specified by a finite string Turing machine
description.

Crucially this is one level of indirect reference away from the behavior
of the actual Turing machine. This never makes any difference except
in the case of pathological self-reference such as D correctly simulated
by pure function H. No one ever noticed this before because simulating
termination analyzers were always rejected out-of-hand without review.

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