Re: Every sufficiently competent C programmer knows --- Semantic Property of Finite String

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