Re: Incorrect requirements --- Computing the mapping from the input to HHH(DD)

On 5/9/25 12:49 AM, olcott wrote:

On 5/8/2025 11:11 PM, Keith Thompson wrote:

olcott <polcott333@gmail.com> writes:

On 5/8/2025 8:30 PM, Keith Thompson wrote:

olcott <polcott333@gmail.com> writes:

On 5/8/2025 6:49 PM, Keith Thompson wrote:

olcott <polcott333@gmail.com> writes:
[...]

void DDD()
{
     HHH(DDD);
     return;
}
>
If you are a competent C programmer then you
know that DDD correctly simulated by HHH cannot
possibly each its own "return" instruction.

"cannot possibly each"?
I am a competent C programmer (and I don't believe you can make
the same claim).  I don't know what HHH is.  The name "HHH" tells
me nothing about what it's supposed to do.  Without knowing what
HHH is, I can't say much about your code (or is it pseudo-code?).
>

>
For the purpose of this discussion HHH is exactly
what I said it is. It correctly simulates DDD.

Does HHH correctly simulate DDD *and do nothing else*?
Does HHH correctly simulate *every* function whose address is passed
to it?  Must the passed function be one that takes no arguments
and does not return a value?
Can HHH just *call* the function whose address is passed to it?
If it's a correct simulation, there should be no difference between
calling the function and "correctly simulating" it.
My knowledge of C tells me nothing about *how* HHH might simulate
DDD.

>
HHH can only simulate a function that take no arguments
and has no return value. HHH also simulates the entire
chain of functions that this function calls. These can
take arguments or not and have return values or not.
>
Thus HHH ends up simulating itself (and everything
that HHH calls) simulating DDD in an infinite
sequence of recursive emulation until OOM error.
>

We need not know anything else about HHH to
know that DDD correctly simulated by HHH cannot
possibly REACH its own "return" instruction.

Assuming that HHH(DDD) "correctly simulates" DDD, and assuming it
does nothing else, your code would be equivalent to this:
      void DDD(void) {
          DDD();
          return;
      }

>
Exactly. None of these people on comp.theory could
get that even after three years.

>
I find that difficult to believe.
>

Then the return statement (which is unnecessary anyway) will never be
reached.

>
It is only there to mark a final halt state.

>
The closing "}" does that equally well.
>

In practice, the program will likely crash due to a stack
overflow, unless the compiler implements tail-call optimization, in
which case the program might just run forever -- which also means the
unnecessary return statement will never be reached.
>

>
Yes you totally have this correctly.
None of the dozens of comp.theory people could
ever achieve that level of understanding even
after three years. That is why I needed to post
on comp.lang.c.

>
I'll note that I've posted in comp.theory, not in comp.lang.c.
I never see anything you post in comp.lang.c.
>

This conclusion relies on my understanding of what you've said about
your code, which I consider to be unreliable.

>
I am not even talking about my code. I am
talking about the purely hypothetical code
that you just agreed to.

>
Do not overestimate what I've agreed to.  I must still consider the
possibility that I've been led into a logical trap of some sort,
and that I've missed some subtle flaw.
>

No doubt you believe that there is some significance to the
apparent fact that the return statement will never be reached,
assuming that's a correct and relevant conclusion.  I don't know
what that significance might be.

>
I will tell you that later after you understand
some prerequisite ideas first.
>
int DD()
{
   int Halt_Status = HHH(DD);
   if (Halt_Status)
     HERE: goto HERE;
   return Halt_Status;
}

>
So now HHH returns an int result, and you store that result
in a variable named "Halt_Status".  You haven't said here what
the meaning of that result might be, and I decline to make any
assumptions based on what you've called it.  You could rename
"Halt_Status" to "Foo" and have effectively identical code.
>
Previously DDD would "correctly simulate" the function whose address is
passed to it.  Now it does that and returns an int result.
>
If you want to say anything about the meaning of the result returned
by HHH, feel free to say it.
>

The same thing that applied to DDD equally
applies to the more complicated DD.
>
When 1 or more instructions of DD are correctly
simulated by HHH the correctly simulated DD
cannot possibly get past its call to HHH(DD).
Thus DD also never reaches its "return" instruction.

>
Now you're talking about simulating "1 or more instructions"
of DD.  I thought that HHH was supposed to "accurately simulate"
the function whose argument is passed to it.  Emulating just "1 or
more instructions" is not accurate simulation.
>
If HHH *fully* simulates the execution of DD, then your code above
exhibits endless recursion,

 In computer science "halting" is not merely stopping running.
"Halting" is reaching a final halt state such as the "return"
instruction.

And "Non-Halting" isn't the program being aborted before reaching the final state, but never reaching a final state even after an unbounded number of instructions have been run.

 

which is not particularly interesting,
and it never reaches the "if (Halt_Status)".  (DD calls HHH, which
simulates DD; HHH, in simulating DD, must do the equivalent of
calling HHH, and so on.)
>

 It turns out to be very interesting you merely need
to grok a few details first.

No, it isn't interesting, because it is based on errors. You need to fix those errors, at which point you prove a statement you then can't use for your next step, as it clearly applies to a different input then your actual decider is given.

 

You've introduced the idea of simulating only some finite number
of instructions of the simulated functions, but you haven't really
said how that happens (except perhaps in some x86 code that I
don't understand).  You've implied that a sufficient knowledge of C
would let someone understand your arguments, but part of what you're
saying seems to depend on x86 assembly and/or machine code (which I'm
not going to learn for the sake of this discussion).
>
If I would need to understand x86 code to understand your claims, then
let's just stop here.
>
[SNIP]
>