*Simulating termination analyzer Principle*
It is always correct for any simulating termination
analyzer to stop simulating and reject any input that
would otherwise prevent its own termination.
On 4/5/2025 5:29 PM, olcott wrote:
On 4/5/2025 4:15 PM, dbush wrote:
On 4/5/2025 4:52 PM, olcott wrote:
*Simulating termination analyzer Principle*
It is always correct for any simulating termination
analyzer to stop simulating and reject any input that
would otherwise prevent its own termination.
void DDD()
{
HHH(DDD);
return;
}
Except when doing so would change the input, as is the case
with HHH and DDD.
Changing the input is not allowed.
You may disagree that the above definition
of simulating termination analyzer is correct.
It is self-evident that HHH must stop simulating
DDD to prevent its own non-termination.
Changing the input is not allowed.
On 4/5/2025 4:58 PM, Richard Heathfield wrote:
hp(arg candidate, arg testdata)
{
if(terminates(candidate(testdata)))
{
while(forever);
}
else
{
halt;
}
}
We then invoke the program:
hp(hp, hp)
and try to predict what terminates() will report, and of course
the answer is that we don't know, because neither does
terminates(). The function cannot be written.
Understanding my simpler example was a mandatory
prerequisite
int DD()
{
int Halt_Status = HHH(DD);
if (Halt_Status)
HERE: goto HERE;
return Halt_Status;
}
On 05/04/2025 23:20, olcott wrote:
...The difference between us is that I know it and you don't.
On 2025-04-05, Richard Heathfield <[email protected]> wrote:
On 05/04/2025 23:20, olcott wrote:
...The difference between us is that I know it and you don't.
Olcott resides in a fortress he built out of bricks that were
specially ordered from Dunning and Kruger's website.
You're not getting through.
On 4/5/2025 5:18 PM, Richard Heathfield wrote:<snip>
On 05/04/2025 22:31, dbush wrote:
Changing the input is not allowed.
You're right, but it doesn't matter very much as long as
terminates() *always* gets the answer right for any arbitrary
program tape and any data tape. Mr Olcott's fails to do that.
Termination analyzers are not required to be infallible.
Everyone else seems to think that the correct way
to handle a pathological relationship between an
input and a termination analyzer is to simply ignore
the differences that this makes. THAT CAN'T BE RIGHT !!!
Termination analyzers are not required to be infallible.
On 4/5/2025 6:20 PM, dbush wrote:
On 4/5/2025 7:18 PM, olcott wrote:
On 4/5/2025 5:18 PM, Richard Heathfield wrote:
On 05/04/2025 22:31, dbush wrote:
On 4/5/2025 5:29 PM, olcott wrote:
On 4/5/2025 4:15 PM, dbush wrote:
On 4/5/2025 4:52 PM, olcott wrote:
*Simulating termination analyzer Principle*
It is always correct for any simulating termination
analyzer to stop simulating and reject any input that
would otherwise prevent its own termination.
void DDD()
{
HHH(DDD);
return;
}
Except when doing so would change the input, as is the
case with HHH and DDD.
Changing the input is not allowed.
You may disagree that the above definition
of simulating termination analyzer is correct.
It is self-evident that HHH must stop simulating
DDD to prevent its own non-termination.
Changing the input is not allowed.
You're right, but it doesn't matter very much as long as
terminates() *always* gets the answer right for any arbitrary
program tape and any data tape. Mr Olcott's fails to do that.
Termination analyzers are not required to be infallible.
But they must still generate the required mapping for the input
they claim to answer correctly:
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
Exactly the opposite, they are only allowed to report
on what they see.
On 4/5/2025 5:31 PM, Richard Heathfield wrote:
On 05/04/2025 23:20, olcott wrote:
On 4/5/2025 4:58 PM, Richard Heathfield wrote:
<snip>
hp(arg candidate, arg testdata)
{
if(terminates(candidate(testdata)))
{
while(forever);
}
else
{
halt;
}
}
We then invoke the program:
hp(hp, hp)
and try to predict what terminates() will report, and of
course the answer is that we don't know, because neither does
terminates(). The function cannot be written.
Understanding my simpler example was a mandatory
prerequisite
No, it wasn't.
Understanding my example isn't mandatory either, which is just
as well where you're concerned.
int DD()
{
int Halt_Status = HHH(DD);
if (Halt_Status)
HERE: goto HERE;
return Halt_Status;
}
That's fine, but it does beg the HHH() question. You are
handwaving it for the same reason I am, which is that it can't
be written. The difference between us is that I know it and you
don't.
HHH(DDD) is isomorphic to HHH(DD),
yet failing
to understand that HHH(DDD) meets the
*Simulating termination analyzer Principle*
prevents the significance of this from being seen.
On 4/5/2025 7:34 PM, dbush wrote:
On 4/5/2025 8:30 PM, olcott wrote:
On 4/5/2025 5:27 PM, dbush wrote:
On 4/5/2025 6:18 PM, Richard Heathfield wrote:
On 05/04/2025 22:31, dbush wrote:
On 4/5/2025 5:29 PM, olcott wrote:
On 4/5/2025 4:15 PM, dbush wrote:
On 4/5/2025 4:52 PM, olcott wrote:
*Simulating termination analyzer Principle*
It is always correct for any simulating termination
analyzer to stop simulating and reject any input that
would otherwise prevent its own termination.
void DDD()
{
HHH(DDD);
return;
}
Except when doing so would change the input, as is the
case with HHH and DDD.
Changing the input is not allowed.
You may disagree that the above definition
of simulating termination analyzer is correct.
It is self-evident that HHH must stop simulating
DDD to prevent its own non-termination.
Changing the input is not allowed.
You're right, but it doesn't matter very much as long as
terminates() *always* gets the answer right for any
arbitrary program tape and any data tape. Mr Olcott's fails
to do that.
Of course you're correct. His criteria is basically what
happens if you replace the code of X with a pure simulator
and run X(Y) for some Y.
Everyone else seems to think that the correct way
to handle a pathological relationship between an
input and a termination analyzer is to simply ignore
the differences that this makes. THAT CAN'T BE RIGHT !!!
Ignoring the relationship is exactly what you do when you
change the code of HHH, thereby changing the input.
Changing the input is not allowed.
Ignoring the fact that the pathological
relationship between the input and the
termination analyzer changes the behavior
of the input is certainly incorrect.
Giving up and saying nothing can be done
also seems incorrect.
What else is left?
On 4/5/2025 7:54 PM, James Kuyper wrote:
On 06/04/2025 00:18, olcott wrote:
...
Termination analyzers are not required to be infallible.
The Halting Problem refers to the impossibility of an infallible
termination analyzer. Fallible termination analyzers are trivially
possible - the question's not worth thinking about.
typedef void (*ptr)();
int HHH(ptr P);
int DD()
{
int Halt_Status = HHH(DD);
if (Halt_Status)
HERE: goto HERE;
return Halt_Status;
}
int main()
{
HHH(DD);
}
They are not trivially possible for the above input.
The last step is validating that this principle is correct.
On 05/04/2025 23:42, Kaz Kylheku wrote:
On 2025-04-05, Richard Heathfield <[email protected]> wrote:
On 05/04/2025 23:20, olcott wrote:
...
The difference between us is that I know it and you don't.
Olcott resides in a fortress he built out of bricks that were
specially ordered from Dunning and Kruger's website.
You're not getting through.
Well, no. On the other hand, the discussion has in places driven
me to the literature and has thus in its own way been
educational. For example, I was surprised to discover that
although Turing's 1936 paper does deal with the Halting Problem,
he doesn't actually use that term, which didn't surface until
1952. I also stumbled on a 1972 paper on incomputability by Tony
Hoare and Donald Allison - well worth the read, and I was amused
by its somewhat prescient opening paragraph: "[...] programmers
have been known to attempt solutions to problems which are
probably unsolvable; the existence of such problems should be of
interest to all programmers." Clearly, 53 years ago, they already
had Olcott nailed.
Richard Heathfield <[email protected]> writes:
On 05/04/2025 23:42, Kaz Kylheku wrote:
On 2025-04-05, Richard Heathfield <[email protected]> wrote:
On 05/04/2025 23:20, olcott wrote:
...
The difference between us is that I know it and you don't.
Olcott resides in a fortress he built out of bricks that were
specially ordered from Dunning and Kruger's website.
You're not getting through.
Well, no. On the other hand, the discussion has in places driven
me to the literature and has thus in its own way been
educational. For example, I was surprised to discover that
although Turing's 1936 paper does deal with the Halting Problem,
he doesn't actually use that term, which didn't surface until
1952. I also stumbled on a 1972 paper on incomputability by Tony
Hoare and Donald Allison - well worth the read, and I was amused
by its somewhat prescient opening paragraph: "[...] programmers
have been known to attempt solutions to problems which are
probably unsolvable; the existence of such problems should be of
interest to all programmers." Clearly, 53 years ago, they already
had Olcott nailed.
I agree these discoveries are interesting, but the subject still
isn't one that is suitable for comp.lang.c.
On 4/6/2025 5:25 AM, Tim Rentsch wrote:
Richard Heathfield <[email protected]> writes:
On 05/04/2025 23:42, Kaz Kylheku wrote:
On 2025-04-05, Richard Heathfield <[email protected]> wrote:
On 05/04/2025 23:20, olcott wrote:
...
The difference between us is that I know it and you don't.
Olcott resides in a fortress he built out of bricks that were
specially ordered from Dunning and Kruger's website.
You're not getting through.
Well, no. On the other hand, the discussion has in places driven
me to the literature and has thus in its own way been
educational. For example, I was surprised to discover that
although Turing's 1936 paper does deal with the Halting Problem,
he doesn't actually use that term, which didn't surface until
1952. I also stumbled on a 1972 paper on incomputability by Tony
Hoare and Donald Allison - well worth the read, and I was amused
by its somewhat prescient opening paragraph: "[...] programmers
have been known to attempt solutions to problems which are
probably unsolvable; the existence of such problems should be of
interest to all programmers." Clearly, 53 years ago, they already
had Olcott nailed.
I agree these discoveries are interesting, but the subject still
isn't one that is suitable for comp.lang.c. A good way to avoid
these long pointless discussions is not to respond to postings
that are not suitable to comp.lang.c, except to point out that
they are not suitable to comp.lang.c. And for any given poster,
don't respond to unsuitable postings more often than once a month.
My intent was to focus on the semantics of a pair of C functions.
Digression into computer science seems inappropriate and never
was my intent. The comp.theory people refused to consider the
semantics of C aspects of these functions.
On 4/6/2025 9:37 PM, Tim Rentsch wrote:
olcott <[email protected]> writes:
On 4/6/2025 5:25 AM, Tim Rentsch wrote:
Richard Heathfield <[email protected]> writes:
On 05/04/2025 23:42, Kaz Kylheku wrote:
On 2025-04-05, Richard Heathfield <[email protected]> wrote:
On 05/04/2025 23:20, olcott wrote:
...
The difference between us is that I know it and you don't.
Olcott resides in a fortress he built out of bricks that were
specially ordered from Dunning and Kruger's website.
You're not getting through.
Well, no. On the other hand, the discussion has in places driven
me to the literature and has thus in its own way been
educational. For example, I was surprised to discover that
although Turing's 1936 paper does deal with the Halting Problem,
he doesn't actually use that term, which didn't surface until
1952. I also stumbled on a 1972 paper on incomputability by Tony
Hoare and Donald Allison - well worth the read, and I was amused
by its somewhat prescient opening paragraph: "[...] programmers
have been known to attempt solutions to problems which are
probably unsolvable; the existence of such problems should be of
interest to all programmers." Clearly, 53 years ago, they already
had Olcott nailed.
I agree these discoveries are interesting, but the subject still
isn't one that is suitable for comp.lang.c. A good way to avoid
these long pointless discussions is not to respond to postings
that are not suitable to comp.lang.c, except to point out that
they are not suitable to comp.lang.c. And for any given poster,
don't respond to unsuitable postings more often than once a month.
My intent was to focus on the semantics of a pair of C functions.
Digression into computer science seems inappropriate and never
was my intent. The comp.theory people refused to consider the
semantics of C aspects of these functions.
It seems the people who are responding to you have the impression
that you are convinced you have a solution to the halting problem,
and that your questions about code are in effect asking people to
convince you that you don't (or alternatively that you are offering
an argument that you have solved the halting problem).
If indeed your interest is only about how C defines the semantics of
some particular functions written in C, and having nothing to do
with solving the halting problem, then the burden is on you to
express that question well enough so that other people realize that.
So far it appears that you haven't succeeded with anyone who has
responded to your postings.
int DD()
{
int Halt_Status = HHH(DD);
if (Halt_Status)
HERE: goto HERE;
return Halt_Status;
}
The people responding to my posts have consistently
stonewalled my every attempt to:
(a) Show that DD correctly simulated by HHH could
never reach its own "return" instruction.
(b) We never got to (b) because of endless stonewalling.
The end goal (in this forum) that is empirically proven
by this fully operational code:
https://github.com/plolcott/x86utm/blob/master/Halt7.c
is to show that HHH is a correct termination analyzer for DD.
Tim Rentsch <[email protected]> writes:
olcott <[email protected]> writes:
[82 lines deleted]
I'm sorry my comments weren't more helpful for you.
Tim, *please* trim quoted text that isn't relevant to your followup.
Does your halt decider work or not?
| Sysop: | Keyop |
|---|---|
| Location: | Huddersfield, West Yorkshire, UK |
| Users: | 715 |
| Nodes: | 16 (2 / 14) |
| Uptime: | 154:21:41 |
| Calls: | 12,092 |
| Calls today: | 5 |
| Files: | 15,000 |
| Messages: | 6,517,679 |