Path: news.eternal-september.org!eternal-september.org!.POSTED!not-for-mail
From: dbush <dbush.mobile@gmail.com>
Newsgroups: comp.theory
Subject: Re: Every sufficiently competent C programmer knows --- Semantic
 Property of Finite String
Date: Thu, 13 Mar 2025 10:02:07 -0400
Organization: A noiseless patient Spider
Lines: 117
Message-ID: <vquogu$39p4p$2@dont-email.me>
References: <vqntaq$1jut5$1@dont-email.me> <vqp388$1tvqa$1@dont-email.me>
 <vqpdv9$202b2$2@dont-email.me> <vqperb$20c9k$2@dont-email.me>
 <E6mcnWv3nMa66036nZ2dnZfqnPWdnZ2d@brightview.co.uk>
 <vqs2n8$2knng$1@dont-email.me>
 <5429f6c8b8a8a79e06b4aeefe677cc54a2a636bf@i2pn2.org>
 <vqt9jp$2spcd$6@dont-email.me> <vqtag4$2t2hb$2@dont-email.me>
 <vqtgl0$2u7fo$1@dont-email.me> <vqth3r$2t2hb$3@dont-email.me>
 <vqtliv$32on1$1@dont-email.me> <vquhj4$37tpi$1@dont-email.me>
 <vquo2g$392on$2@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Thu, 13 Mar 2025 15:02:06 +0100 (CET)
Injection-Info: dont-email.me; posting-host="416957debdcb20d9b566cd00245152da";
	logging-data="3466393"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX19AF2UXT8N+tmP+o8HT1tk6"
User-Agent: Mozilla Thunderbird
Cancel-Lock: sha1:APLAW7VPYpiD7n6/PNh4+kR7S8E=
Content-Language: en-US
In-Reply-To: <vquo2g$392on$2@dont-email.me>

On 3/13/2025 9:54 AM, olcott wrote:
> On 3/13/2025 7:03 AM, dbush wrote:
>> On 3/13/2025 12:05 AM, olcott wrote:
>>> On 3/12/2025 9:49 PM, dbush wrote:
>>>> On 3/12/2025 10:41 PM, olcott wrote:
>>>>> On 3/12/2025 7:56 PM, dbush wrote:
>>>>>> On 3/12/2025 8:41 PM, olcott wrote:>>
>>>>>>>
>>>>>>> NOT WHEN IT IS STIPULATED THAT THE BEHAVIOR BEING
>>>>>>> MEASURED IS 
>>>>>>
>>>>>>
>>>>>> The direct execution of DDD 
>>>>>
>>>>> is proven to be different than the behavior of DDD
>>>>> emulated by HHH according to the semantics of the
>>>>> x86 language.
>>>>>
>>>>
>>>> Which is not what a solution to the halting problem is stipulated to 
>>>> compute:
>>>>
>>>>
>>>
>>> Unless you look more deeply into these things and
>>> realize that it is the semantic property of the
>>> (computation encoded as a) finite string that Rice's
>>> Theorem is based on.
>>
>> And that semantic property is the direct execution of the program 
>> described by the input.
>>
>>
>>>
>>>> Given any algorithm (i.e. a fixed immutable sequence of 
>>>> instructions) X described as <X> with input Y:
>>>>
>>>
>>> The finite string pair DDD/HHH specifies a different
>>> computation than the finite string pair DDD/HHH1.
>>>
>>
>> False.  DDD is the description of the algorithm <DDD> 
> 
> There is no vague description of an algorithm when we examine
> these things concretely. We get rid of this vagueness when we
> switch from some unspecified Turing Machine description
> (not even knowing the details of the language) to actual x86
> machine code.
> 

There is no vaugeness.  DDD halts when executed directly, and that's 
what we want to know about as per the requirements:


Given any algorithm (i.e. a fixed immutable sequence of instructions) X 
described as <X> with input Y:

A solution to the halting problem is an algorithm H that computes the 
following mapping:

(<X>,Y) maps to 1 if and only if X(Y) halts when executed directly
(<X>,Y) maps to 0 if and only if X(Y) does not halt when executed directly


> With x86 machine code when N steps of DDD are emulated by
> HHH according to the semantics of the x86 language

And since the code in concrete, what is the fixed value of N that HHH 
simulates?  Based on that, we know that DDD halts after N+K steps.

> 
> _DDD()
> [00002172] 55         push ebp      ; housekeeping
> [00002173] 8bec       mov  ebp,esp  ; housekeeping
> [00002175] 6872210000 push 00002172 ; push DDD
> [0000217a] e853f4ffff call 000015d2 ; call HHH(DDD)
> [0000217f] 83c404     add  esp,+04
> [00002182] 5d         pop  ebp
> [00002183] c3         ret
> Size in bytes:(0018) [00002183]
> 
> We get a DDD that cannot possibly reach its own machine address
> 0000217f. There is no conditional code in DDD that prevents
> it from calling HHH(DDD) each time it is recursively emulated.
> 

False.  There is conditional code in HHH, which is part of DDD, that can 
and does eventually return.

>> which includes the fixed code of the function DDD, the fixed code of 
>> the function HHH (i.e. HHH is part of the input), and the fixed code 
>> of everything it calls down to the OS level.
>>
>> So HHH(DDD) and HHH1(DDD) are both being passed the same program 
>> description and are therefore required to both compute the same mapping:
>>
> 
> When you ignore the fact that DDD calls HHH in recursive
> emulation and does not call HHH1 in recursive emulation
> you are a liar.
> 


Irrelevant.  What's relevant is that DDD halts when executed directly, 
and that is the behavior that a solution to the halting problem is 
stipulated to report:


Given any algorithm (i.e. a fixed immutable sequence of instructions) X 
described as <X> with input Y:

A solution to the halting problem is an algorithm H that computes the 
following mapping:

(<X>,Y) maps to 1 if and only if X(Y) halts when executed directly
(<X>,Y) maps to 0 if and only if X(Y) does not halt when executed directly