Many of you think that it is possible to make/code a three-way decision
function that takes as arguments a description of a computation and
arguments for it; F(A) will be used t9 refer to the actual computation
with arguments. Three descriptive results shall be possible and the one
chosen depends on F(A). The three possibilities are
H if F(A) halts, L if F(A) is pathological, L if F(A) loops forever.
The assumption is that there is a decide, H, which given the arguments F
and A, always itself halts and determines the correct one of H, L, and
P. The following code, based on the disproof of the halting problem in
Linz, shows that this too is impossible:
------------------------------------------------------------------
Function h(tm,a)
;; Value is H if tm(a) halts;
;; Value is P if tm(a) is pathological;
;; Value is L if tm(a) simply loops forever.
Return correct value for tm(a)
End h;
Function h’(tm,a)
;; Inverts the meaning of H and L.
;; If tm(a) halts Then h’(tm,a) loops forever;
;; If tm(a) is pathological Then h’(tm,a) halts (returning H).
;; If tm(a) loops forever Then h’(tm,a) halts (returning H).
Select h(tm,a)
When H Then loop:Goto loop;
When P Then Return H;
when L Then Return H;
End h’;
Function hat(tm)
;; If tm(tm) halts Then hat(tm) loops forever;
;; If tm(tm) is pathological Then hat(tm) halts (returning H).
;; If tm(tm) loops forever Then hat(tm) halts (returning H).
Return h’(tm,tm);
End hat;
;; And we now learn that this doesn’t work either!
;; For hat(hat)
If hat(hat) halts Then hat(hat) loops forever
If hat(hat) is pathological Then hat(hat) halts (returning H).
If hat(hat) loops forever Then hat(hat) halts (returning H).
Evaluate hat(hat);
--------------------------------------------------------------------
A pdf of the code is available at https://notatt.com/halt3.pdf
Note that it makes little difference what is meant by "pathological", it
is what Hitchcock called a MacGuffin. It may give us something to talk
about but it has little to do with the problem at hand: namely whether a
halt decider could exist.
--
Jeff Barnett

On 03/08/2022 06:49, Jeff Barnett wrote:
> Many of you think that it is possible to make/code a three-way decision function that takes as
> arguments a description of a computation and arguments for it; F(A) will be used t9 refer to the
> actual computation with arguments. Three descriptive results shall be possible and the one chosen
> depends on F(A). The three possibilities are
>     H if F(A) halts, L if F(A) is pathological, L if F(A) loops forever.

You mean P if F(A) is pathelogical I think.

You need to say more about what pathelogical means - I know that below you say it hardly matters, so
fair enough, let's take it for now that EVERY computation is deemed pathelogical. That's certainly
a decidable property of a computation... Then a decider can just returns P straight away, which is
correct, it would seem!

Below you are suggesting this doesn't work, so let's see what's going on...

> The assumption is that there is a decide, H, which given the arguments F and A, always itself halts
> and determines the correct one of H, L, and P. The following code, based on the disproof of the
> halting problem in Linz, shows that this too is impossible:

Seems you make a big assumption: " *THE* correct one of H, L, and P", but a halting program could be
deemed pathelogical as could a non-halting program. In PO's case, he deems P(P) pathelogical (for
whatever reason), and P(P) halts.

If you insist only one of H,L,P can apply, then since EVERY computation is H or L, then P NEVER
applies. That's not going anywhere useful.

So h simply returning P (all computations are patherlogical) still seems reasonable...

>
> ------------------------------------------------------------------
> Function h(tm,a)
> ;; Value is H if tm(a) halts;
> ;; Value is P if tm(a) is pathological;
> ;; Value is L if tm(a) simply loops forever.
> Return correct value for tm(a)
> End h;

...so with my "pathelogical" h always returns P

> Function h’(tm,a)
> ;; Inverts the meaning of H and L.
> ;; If tm(a) halts Then h’(tm,a) loops forever;
> ;; If tm(a) is pathological Then h’(tm,a) halts (returning H).
> ;; If tm(a) loops forever Then h’(tm,a) halts (returning H).
> Select h(tm,a)
> When H Then loop:Goto loop;
> When P Then Return H;
> when L Then Return H;
> End h’;

...so with my "pathelogical" h' always returns H

> Function hat(tm)
> ;; If tm(tm) halts Then hat(tm) loops forever;
> ;; If tm(tm) is pathological Then hat(tm) halts (returning H).
> ;; If tm(tm) loops forever Then hat(tm) halts (returning H).
> Return h’(tm,tm);
> End hat;

...so with my "pathelogical" hat always returns H

> ;; And we now learn that this doesn’t work either!
> ;;     For hat(hat)
> If hat(hat) halts Then hat(hat) loops forever
> If hat(hat) is pathological Then hat(hat) halts (returning H).
> If hat(hat) loops forever Then hat(hat) halts (returning H).
> Evaluate hat(hat);

...so hat(hat) is both pathelogical, and halts (returning H). I don't see any contradiction here.
You say "If hat(hat) halts Then hat(hat) loops forever" but that's simply wrong - in my example it
halts.

A) hat(hat) is pathelogical, and
B) h(hat,hat) CORRECTLY returns P.

All good!

I think the problem is you've not covered what "pathelogical" actually means and how it is to be
used. Obviously it overlaps with halting and non-halting, but what should be returned by above
functions in these cases?

> --------------------------------------------------------------------
>
> A pdf of the code is available at https://notatt.com/halt3.pdf
>
> Note that it makes little difference what is meant by "pathological", it is what Hitchcock called a
> MacGuffin. It may give us something to talk about but it has little to do with the problem at hand:
> namely whether a halt decider could exist.

I agree that discussions of "pathelogical" without any concrete definition are fruitless.

PO in particular seems totally confused by the Wikipedia article he is always quoting which
describes P(P) as a "pathelogical" input [NOTE THE QUOTES, WHICH ARE IN THE WIKIPEDIA ARTICLE
ITSELF]. The quotes around the word show the Wikipedia author recognises that P(P) isn't actually
pathelogical in the normal sense of the word - there is nothing "wrong" with P(P) as an input, and
P(P) has a definite halting/non-halting status. It's just that H gets the answer wrong.

I think the use of the word "pathelogical" in the article is highly misleading, and I'm struggling
to think of what the author was actually thinking when he chose the word. (Given that I've never
heard anyone but PO speak of pathelogical anything (his PSR) in computer terms, it wouldn't surprise
me if we discovered that it was PO who edited the article to include the word!) Still, it's just a
word in a Wikipedia article I guess...

Mike.

On 8/3/2022 10:49 AM, Mike Terry wrote:
> On 03/08/2022 06:49, Jeff Barnett wrote:
>> Many of you think that it is possible to make/code a three-way
>> decision function that takes as arguments a description of a
>> computation and arguments for it; F(A) will be used t9 refer to the
>> actual computation with arguments. Three descriptive results shall be
>> possible and the one chosen depends on F(A). The three possibilities are
>>      H if F(A) halts, L if F(A) is pathological, L if F(A) loops forever.
>
> You mean P if F(A) is pathelogical I think.
>
> You need to say more about what pathelogical means - I know that below
> you say it hardly matters, so fair enough, let's take it for now that
> EVERY computation is deemed pathelogical.  That's certainly a decidable
> property of a computation...  Then a decider can just returns P straight
> away, which is correct, it would seem!
>
> Below you are suggesting this doesn't work, so let's see what's going on...
>
>> The assumption is that there is a decide, H, which given the arguments
>> F and A, always itself halts and determines the correct one of H, L,
>> and P. The following code, based on the disproof of the halting
>> problem in Linz, shows that this too is impossible:
>
> Seems you make a big assumption: " *THE* correct one of H, L, and P",
> but a halting program could be deemed pathelogical as could a
> non-halting program.  In PO's case, he deems P(P) pathelogical (for
> whatever reason), and P(P) halts.
>
I never said anything like that. It seems that the reason that you don't
understand me is that you don't pay enough attention.

H and P have been defined to have a pathological relationship to each
other.

For any program H that might determine if programs halt, a
"pathological" program P, called with some input, can pass
its own source and its input to H and then specifically do the
opposite of what H predicts P will do.
*No H can exist that handles this case*
https://en.wikipedia.org/wiki/Halting_problem

typedef void (*ptr)();
int H(ptr p, ptr i); // simulating halt decider

void P(ptr x)
{ int Halt_Status = H(x, x);
if (Halt_Status)
HERE: goto HERE;
return;
}

int main()
{ Output("Input_Halts = ", H(P, P));
}

*THIS IS REALLY NOT THAT HARD*
Everyone knows that a software function can only return values based on
its actual input and cannot return values based on non-input.

When H(P,P) is invoked from main the full execution trace is
H(P,P) simulates P(P) calls simulated H(P,P)

When P(P) is invoked from main the full execution trace is
P(P) invokes H(P,P) simulates P(P) calls simulated H(P,P)

Because the executed P(P) depends on the return value of H(P,P) and the
simulated P(P) cannot possibly have this same dependency** their
behavior is not the same.

** It is stuck in what is essentially infinite recursion, thus cannot
receive any value from H(P,P). This prevents the simulated P from doing
the opposite of whatever H(P,P) returns to it because H(P,P) never
returns to it. No function called in what is essentially infinite
recursion ever returns to its caller.

int sum(int x, int y) { return x + y; }
For H(P,P) to return a value for a different sequence of instructions
than the one specified by its input would be the same as if sum(3,4)
returning the sum of 4+5.

--
Copyright 2022 Pete Olcott

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

On 03/08/2022 17:40, olcott wrote:
> On 8/3/2022 10:49 AM, Mike Terry wrote:
>> On 03/08/2022 06:49, Jeff Barnett wrote:
>>> Many of you think that it is possible to make/code a three-way decision function that takes as
>>> arguments a description of a computation and arguments for it; F(A) will be used t9 refer to the
>>> actual computation with arguments. Three descriptive results shall be possible and the one chosen
>>> depends on F(A). The three possibilities are
>>>      H if F(A) halts, L if F(A) is pathological, L if F(A) loops forever.
>>
>> You mean P if F(A) is pathelogical I think.
>>
>> You need to say more about what pathelogical means - I know that below you say it hardly matters,
>> so fair enough, let's take it for now that EVERY computation is deemed pathelogical.  That's
>> certainly a decidable property of a computation...  Then a decider can just returns P straight
>> away, which is correct, it would seem!
>>
>> Below you are suggesting this doesn't work, so let's see what's going on...
>>
>>> The assumption is that there is a decide, H, which given the arguments F and A, always itself
>>> halts and determines the correct one of H, L, and P. The following code, based on the disproof of
>>> the halting problem in Linz, shows that this too is impossible:
>>
>> Seems you make a big assumption: " *THE* correct one of H, L, and P", but a halting program could
>> be deemed pathelogical as could a non-halting program.  In PO's case, he deems P(P) pathelogical
>> (for whatever reason), and P(P) halts.
>>
> I never said anything like that. It seems that the reason that you don't understand me is that you
> don't pay enough attention.

I was replying to Jeff, not you.

Mike.

On 8/3/2022 12:12 PM, Mike Terry wrote:
> On 03/08/2022 17:40, olcott wrote:
>> On 8/3/2022 10:49 AM, Mike Terry wrote:
>>> On 03/08/2022 06:49, Jeff Barnett wrote:
>>>> Many of you think that it is possible to make/code a three-way
>>>> decision function that takes as arguments a description of a
>>>> computation and arguments for it; F(A) will be used t9 refer to the
>>>> actual computation with arguments. Three descriptive results shall
>>>> be possible and the one chosen depends on F(A). The three
>>>> possibilities are
>>>>      H if F(A) halts, L if F(A) is pathological, L if F(A) loops
>>>> forever.
>>>
>>> You mean P if F(A) is pathelogical I think.
>>>
>>> You need to say more about what pathelogical means - I know that
>>> below you say it hardly matters, so fair enough, let's take it for
>>> now that EVERY computation is deemed pathelogical.  That's certainly
>>> a decidable property of a computation...  Then a decider can just
>>> returns P straight away, which is correct, it would seem!
>>>
>>> Below you are suggesting this doesn't work, so let's see what's going
>>> on...
>>>
>>>> The assumption is that there is a decide, H, which given the
>>>> arguments F and A, always itself halts and determines the correct
>>>> one of H, L, and P. The following code, based on the disproof of the
>>>> halting problem in Linz, shows that this too is impossible:
>>>
>>> Seems you make a big assumption: " *THE* correct one of H, L, and P",
>>> but a halting program could be deemed pathelogical as could a
>>> non-halting program.  In PO's case, he deems P(P) pathelogical (for
>>> whatever reason), and P(P) halts.
>>>
>> I never said anything like that. It seems that the reason that you
>> don't understand me is that you don't pay enough attention.
>
> I was replying to Jeff, not you.
>
> Mike.

None-the-less you do not have permission to misrepresent what I said:
>>> In PO's case, he deems P(P) pathological (for
>>> whatever reason), and P(P) halts.

I never said anything like that. H and P have a pathological
relationship to each other. There is nothing pathological about P(P).

--
Copyright 2022 Pete Olcott

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

On Wednesday, 3 August 2022 at 19:46:58 UTC+2, olcott wrote:
> None-the-less you do not have permission to misrepresent what I said:
Nobody gave you permission to misrepresent Turing; or a 100 year old field of research, yet here you are.

Thousands of hours into it...

On 8/3/2022 12:51 PM, Skep Dick wrote:
> On Wednesday, 3 August 2022 at 19:46:58 UTC+2, olcott wrote:
>> None-the-less you do not have permission to misrepresent what I said:
> Nobody gave you permission to misrepresent Turing; or a 100 year old field of research, yet here you are.
>
> Thousands of hours into it...

I am not misrepresenting Turing.
I found a loophole in the HP proofs that negate them.

--
Copyright 2022 Pete Olcott

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

olcott <NoOne@NoWhere.com> writes:
[...]
> *THIS IS REALLY NOT THAT HARD*
> Everyone knows that a software function can only return values based
> on its actual input and cannot return values based on non-input.
[...]

What exactly do you mean by "input"?

In C, for example, a function does not have "input" (though it can
perform input, for example via a call to fgetc() or scanf()). The
values passed to a function are *arguments*, which copied to the
function's *parameters*.

For example:

int func(int n) { return n + 1; }
...
func(42);

`42` is an argument, an expression that's part of the function call
expression `func(42)`. `n` is a parameter, an object local to `func`
that its initialized to the value of the argument on each call. (Some
languages use the terms "actual parameter" and "formal parameter", but
since most of your examples are in C, I suggest sticking to C
terminology.)

When you say "a software function", do you mean a function in C? If so,
what exactly do you mean by "input"?

If you're saying that a C function can only return values based on its
parameters, that is clearly untrue. You might be describing a "pure
function", but you didn't say so.

int impure_func(int n) {
static int s;
s += n;
return n + rand() + time(NULL)%60 + foo + getchar();
}

This contrived but valid function returns a result based on its
parameter, on the value of a static object that retains its value across
calls, on the current time, on a random number, and on a character it
reads from standard input.

I'm trying to figure out just what you mean when you say
Everyone knows that a software function can only return values based
on its actual input and cannot return values based on non-input.

There may be a true statement in there somewhere, but with your odd
terminology I honestly don't know what it is. If you're talking about
software functions and you intend to restrict your statement to *pure*
functions, it would be helpful if you would use the phrase "pure
function" -- and if you would avoid using the word "input" to refer to a
function's arguments/parameters.

--
Keith Thompson (The_Other_Keith) Keith.S.Thompson+u@gmail.com
Working, but not speaking, for Philips
void Void(void) { Void(); } /* The recursive call of the void */

On 8/3/2022 1:35 PM, Keith Thompson wrote:
> olcott <NoOne@NoWhere.com> writes:
> [...]
>> *THIS IS REALLY NOT THAT HARD*
>> Everyone knows that a software function can only return values based
>> on its actual input and cannot return values based on non-input.
> [...]
>
> What exactly do you mean by "input"?
>

I really appreciate your review, thanks a lot.

For any program H that might determine if programs halt, a
"pathological" program P, called with some input, can pass
its own source and its input to H and then specifically do the
opposite of what H predicts P will do.
*No H can exist that handles this case*
https://en.wikipedia.org/wiki/Halting_problem

> In C, for example, a function does not have "input" (though it can
> perform input, for example via a call to fgetc() or scanf()). The
> values passed to a function are *arguments*, which copied to the
> function's *parameters*.
>

In my C implementation of H and P the "input" are arguments to the C
function H and the C function P.

> For example:
>
> int func(int n) { return n + 1; }
> ...
> func(42);
>
> `42` is an argument, an expression that's part of the function call
> expression `func(42)`. `n` is a parameter, an object local to `func`
> that its initialized to the value of the argument on each call. (Some
> languages use the terms "actual parameter" and "formal parameter", but
> since most of your examples are in C, I suggest sticking to C
> terminology.)
>
> When you say "a software function", do you mean a function in C? If so,
> what exactly do you mean by "input"?
>

The arguments to H and P.

> If you're saying that a C function can only return values based on its
> parameters, that is clearly untrue. You might be describing a "pure
> function", but you didn't say so.
>

Yes everyone here knows that H is assumed to be a pure function.

> int impure_func(int n) {
> static int s;
> s += n;
> return n + rand() + time(NULL)%60 + foo + getchar();
> }
>
> This contrived but valid function returns a result based on its
> parameter, on the value of a static object that retains its value across
> calls, on the current time, on a random number, and on a character it
> reads from standard input.
>
> I'm trying to figure out just what you mean when you say
> Everyone knows that a software function can only return values based
> on its actual input and cannot return values based on non-input.
>

H is assumed to be a pure function. I can't state that directly
otherwise people get get off track of the point at hand and endlessly
argue that they do not believe that H is a pure function. Hypothetically
if H is a pure function then its return value must be based only on its
input.

> There may be a true statement in there somewhere, but with your odd
> terminology I honestly don't know what it is. If you're talking about
> software functions and you intend to restrict your statement to *pure*
> functions, it would be helpful if you would use the phrase "pure
> function" -- and if you would avoid using the word "input" to refer to a
> function's arguments/parameters.
>

I want my words to map the the Wikipedia article that refers to inputs.

To get us on the same page I rephrased my statement based on your critique:

*THIS IS REALLY NOT THAT HARD*
Everyone knows that a pure function can only return values based on its
actual arguments and cannot return values on any other basis.

When H is a simulating halt decider it must base it halt status decision
on the actual behavior actually specified by its arguments (pointers to
the machine code of P) as measured by the correct x86 emulation of this
machine code performed by H.

Everyone here believes that H must compute the halt status of a
different sequence of instructions than the one specified by its arguments.

*It seems that you and I both agree that a pure function cannot do that*
*Thanks for you review, I really appreciate your technical competence*

https://en.wikipedia.org/wiki/Pure_function

--
Copyright 2022 Pete Olcott

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

On Tue, 2 Aug 2022 23:49:40 -0600
Jeff Barnett <jbb@notatt.com> wrote:

> Many of you think that it is possible to make/code a three-way
> decision function that takes as arguments a description of a
> computation and arguments for it; F(A) will be used t9 refer to the
> actual computation with arguments. Three descriptive results shall be
> possible and the one chosen depends on F(A). The three possibilities
> are H if F(A) halts, L if F(A) is pathological, L if F(A) loops
> forever. The assumption is that there is a decide, H, which given the
> arguments F and A, always itself halts and determines the correct one
> of H, L, and P. The following code, based on the disproof of the
> halting problem in Linz, shows that this too is impossible:
>
> ------------------------------------------------------------------
> Function h(tm,a)
> ;; Value is H if tm(a) halts;
> ;; Value is P if tm(a) is pathological;
> ;; Value is L if tm(a) simply loops forever.
> Return correct value for tm(a)
> End h;
> Function h’(tm,a)
> ;; Inverts the meaning of H and L.
> ;; If tm(a) halts Then h’(tm,a) loops forever;
> ;; If tm(a) is pathological Then h’(tm,a) halts (returning H).
> ;; If tm(a) loops forever Then h’(tm,a) halts (returning H).
> Select h(tm,a)
> When H Then loop:Goto loop;
> When P Then Return H;
> when L Then Return H;
> End h’;
> Function hat(tm)
> ;; If tm(tm) halts Then hat(tm) loops forever;
> ;; If tm(tm) is pathological Then hat(tm) halts (returning H).
> ;; If tm(tm) loops forever Then hat(tm) halts (returning H).
> Return h’(tm,tm);
> End hat;
> ;; And we now learn that this doesn’t work either!
> ;; For hat(hat)
> If hat(hat) halts Then hat(hat) loops forever
> If hat(hat) is pathological Then hat(hat) halts (returning H).
> If hat(hat) loops forever Then hat(hat) halts (returning H).
> Evaluate hat(hat);
> --------------------------------------------------------------------
>
> A pdf of the code is available at https://notatt.com/halt3.pdf
>
> Note that it makes little difference what is meant by "pathological",
> it is what Hitchcock called a MacGuffin. It may give us something to
> talk about but it has little to do with the problem at hand: namely
> whether a halt decider could exist.

GIGO I'm afraid. Pathological input has to reported as a signal
(i.e. not by returning a value from a function) that is
unobservable/uncatchable by the input; this is my key insight and is
core to my signaling halt decider:

https://github.com/i42output/halting-problem#readme

/Flibble

Mr Flibble <flibble@reddwarf.jmc.corp> writes:

> On Tue, 2 Aug 2022 23:49:40 -0600
> Jeff Barnett <jbb@notatt.com> wrote:

>> Note that it makes little difference what is meant by "pathological",
>> it is what Hitchcock called a MacGuffin. It may give us something to
>> talk about but it has little to do with the problem at hand: namely
>> whether a halt decider could exist.
>
> GIGO I'm afraid.

Also sane input in, garbage out. A three-state quasi-decider must
report "pathological" for an infinite number of cases, all of which
either halt or don't halt. Many of which have nothing to do with any
particular kind of "pathological". Any attempt to pin down
"pathological" beyond simply being the cases about which the
quasi-decider declines to commit itself is doomed.

It would help, I am sure, if people who want to jump into long-solved
problems like this, knew just a little bit more. For example, what are
the "pathological" inputs for other undecidable sets? Given strings
that represent context-free grammars (in, say, BNF), the subset that
represent ambiguous grammars is undecidable. What are the
"pathological" cases now?

And then there are simple-looking programming puzzles like Post's
correspondence problem. Any attempt at a solution must report "yes",
"no" or "pathological" because the "yes" and "no" sets are undecidable.
So what's does a pathological instance of the this trivial problem look
like?

In the end, "pathological" is just "those cases that this algorithm
refuses to commit to". And note it depends on the algorithm. Other
programs will most likely commit to an answer for different sets of
cases. There are no intrinsically "hard" cases.

--
Ben.

olcott <NoOne@NoWhere.com> writes:
[...]
> To get us on the same page I rephrased my statement based on your critique:
>
> *THIS IS REALLY NOT THAT HARD*
> Everyone knows that a pure function can only return values based on
> its actual arguments and cannot return values on any other basis.

Better. In fact that's nearly tautological; that's part of the
definition of "pure function". (Not all of it; a function that returns
a result based only on its arguments but also has side effects is not
pure.)

If you're going to talk about functions in some programming language, I
strongly suggest not assuming that such functions are pure. If you want
to talk about pure functions, that's fine; even if a language has no
such concept (C doesn't mention it), the meaning is clear enough.

More generally, if you're going to talk about code in some programming
language, use that language's terminology if you want to be understood.
The word "input" is well defined in C, and it has nothing to do with a
function's arguments/parameters.

[...]

> *It seems that you and I both agree that a pure function cannot do that*
> *Thanks for you review, I really appreciate your technical competence*

Again, I agree with your statement simply because that's (part of) the
definition of a pure function.

Do not assume that I agree with you about anything else.

> https://en.wikipedia.org/wiki/Pure_function

--
Keith Thompson (The_Other_Keith) Keith.S.Thompson+u@gmail.com
Working, but not speaking, for Philips
void Void(void) { Void(); } /* The recursive call of the void */

On 8/3/2022 9:49 AM, Mike Terry wrote:
> On 03/08/2022 06:49, Jeff Barnett wrote:
>> Many of you think that it is possible to make/code a three-way
>> decision function that takes as arguments a description of a
>> computation and arguments for it; F(A) will be used t9 refer to the
>> actual computation with arguments. Three descriptive results shall be
>> possible and the one chosen depends on F(A). The three possibilities are
>>      H if F(A) halts, L if F(A) is pathological, L if F(A) loops forever.
>
> You mean P if F(A) is pathelogical I think.
Of course.
> You need to say more about what pathelogical means - I know that below
> you say it hardly matters, so fair enough, let's take it for now that
> EVERY computation is deemed pathelogical.  That's certainly a decidable
> property of a computation...  Then a decider can just returns P straight
> away, which is correct, it would seem!
>
> Below you are suggesting this doesn't work, so let's see what's going on...
>
>> The assumption is that there is a decide, H, which given the arguments
>> F and A, always itself halts and determines the correct one of H, L,
>> and P. The following code, based on the disproof of the halting
>> problem in Linz, shows that this too is impossible:
>
> Seems you make a big assumption: " *THE* correct one of H, L, and P",
> but a halting program could be deemed pathelogical as could a
> non-halting program.  In PO's case, he deems P(P) pathelogical (for
> whatever reason), and P(P) halts.
We could say that P is some "Rice" property but almost anything will do.
For started, ask PO. He'll tell you I suppose. Of course P can overlap
L or H and I suppose we could shrink these appropriately. Probably a
slightly better way to do this is to say that P is a non null subset of L.
> If you insist only one of H,L,P can apply, then since EVERY computation
> is H or L, then P NEVER applies.  That's not going anywhere useful.
Did you try substituting your H for mine and trace the consequences?
> So h simply returning P (all computations are patherlogical) still seems
> reasonable...
You will still find a problem. In the first place isn't a three way
decider and it still has the problems derived below. The idea, if you
recall, is that h', hat, and the self application don't depend on h,
rather, they depend on what h is supposed to do.
>>
>> ------------------------------------------------------------------
>> Function h(tm,a)
>> ;; Value is H if tm(a) halts;
>> ;; Value is P if tm(a) is pathological;
>> ;; Value is L if tm(a) simply loops forever.
>> Return correct value for tm(a)
>> End h;
>
> ..so with my "pathelogical" h always returns P
>
>> Function h’(tm,a)
>> ;; Inverts the meaning of H and L.
>> ;; If tm(a) halts Then h’(tm,a) loops forever;
>> ;; If tm(a) is pathological Then h’(tm,a) halts (returning H).
>> ;; If tm(a) loops forever Then h’(tm,a) halts (returning H).
>> Select h(tm,a)
>> When H Then loop:Goto loop;
>> When P Then Return H;
>> when L Then Return H;
>> End h’;
>
> ..so with my "pathelogical" h' always returns H
>
>> Function hat(tm)
>> ;; If tm(tm) halts Then hat(tm) loops forever;
>> ;; If tm(tm) is pathological Then hat(tm) halts (returning H).
>> ;; If tm(tm) loops forever Then hat(tm) halts (returning H).
>> Return h’(tm,tm);
>> End hat;
>
> ..so with my "pathelogical" hat always returns H
It doesn't make any difference what it returns; its the contradiction
that follows that is the key that something is wrong. hat(hat) does not
purport to make a halting decision. However, if you follow the trace you
will run into a contradiction. I thought about this a little bit about
h' do other permutations of the value/behavior it keys on the value of h
but that got boring. It's a fun exercise but doesn't buy much.
>> ;; And we now learn that this doesn’t work either!
>> ;;     For hat(hat)
>> If hat(hat) halts Then hat(hat) loops forever
>> If hat(hat) is pathological Then hat(hat) halts (returning H).
>> If hat(hat) loops forever Then hat(hat) halts (returning H).
>> Evaluate hat(hat);
>
> ..so hat(hat) is both pathelogical, and halts (returning H).  I don't
> see any contradiction here. You say "If hat(hat) halts Then hat(hat)
> loops forever" but that's simply wrong - in my example it halts.
Once again, hat is not a decider of anything, Together with h' its a
test case builder component that shows h doesn't work. Said another way,
the value of hat is pretty much meaningless. Where it returns something,
we could just say halt.
> A)  hat(hat) is pathelogical, and
> B)  h(hat,hat) CORRECTLY returns P.
Once again hat is not a decider and its value signifies little.
> All good!
>
> I think the problem is you've not covered what "pathelogical" actually
> means and how it is to be used.  Obviously it overlaps with halting and
> non-halting, but what should be returned by above functions in these cases?
>
>> --------------------------------------------------------------------
>>
>> A pdf of the code is available at https://notatt.com/halt3.pdf
>>
>> Note that it makes little difference what is meant by "pathological",
>> it is what Hitchcock called a MacGuffin. It may give us something to
>> talk about but it has little to do with the problem at hand: namely
>> whether a halt decider could exist.
>
> I agree that discussions of "pathelogical" without any concrete
> definition are fruitless.
And I'm saying that any "Rice" like property is probably adequate.
> PO in particular seems totally confused by the Wikipedia article he is
> always quoting which describes P(P) as a "pathelogical" input [NOTE THE
> QUOTES, WHICH ARE IN THE WIKIPEDIA ARTICLE ITSELF].  The quotes around
> the word show the Wikipedia author recognises that P(P) isn't actually
> pathelogical in the normal sense of the word - there is nothing "wrong"
> with P(P) as an input, and P(P) has a definite halting/non-halting
> status.  It's just that H gets the answer wrong.
>
> I think the use of the word "pathelogical" in the article is highly
> misleading, and I'm struggling to think of what the author was actually
> thinking when he chose the word.  (Given that I've never heard anyone
> but PO speak of pathelogical anything (his PSR) in computer terms, it
> wouldn't surprise me if we discovered that it was PO who edited the
> article to include the word!)  Still, it's just a word in a Wikipedia
> article I guess...
A reason to mistrust many Wiki articles. I could image a Freshmen
English professor assigning the class members to write and post a Wiki
article on a topic of their choice. This, in lieu of the term ending
essay assignment.
--
Jeff Barnett

On 8/3/2022 2:49 PM, Ben Bacarisse wrote:
> Mr Flibble <flibble@reddwarf.jmc.corp> writes:
>
>> On Tue, 2 Aug 2022 23:49:40 -0600
>> Jeff Barnett <jbb@notatt.com> wrote:
>
>>> Note that it makes little difference what is meant by "pathological",
>>> it is what Hitchcock called a MacGuffin. It may give us something to
>>> talk about but it has little to do with the problem at hand: namely
>>> whether a halt decider could exist.
>>
>> GIGO I'm afraid.
>
> Also sane input in, garbage out. A three-state quasi-decider must
> report "pathological" for an infinite number of cases, all of which
> either halt or don't halt. Many of which have nothing to do with any
> particular kind of "pathological". Any attempt to pin down
> "pathological" beyond simply being the cases about which the
> quasi-decider declines to commit itself is doomed.
>
> It would help, I am sure, if people who want to jump into long-solved
> problems like this, knew just a little bit more. For example, what are
> the "pathological" inputs for other undecidable sets? Given strings
> that represent context-free grammars (in, say, BNF), the subset that
> represent ambiguous grammars is undecidable. What are the
> "pathological" cases now?
>
> And then there are simple-looking programming puzzles like Post's
> correspondence problem. Any attempt at a solution must report "yes",
> "no" or "pathological" because the "yes" and "no" sets are undecidable.
> So what's does a pathological instance of the this trivial problem look
> like?
>
> In the end, "pathological" is just "those cases that this algorithm
> refuses to commit to". And note it depends on the algorithm. Other
> programs will most likely commit to an answer for different sets of
> cases. There are no intrinsically "hard" cases.
I agree. However almost any "Rice" like will do. It's hopeless whatever
the definition is as long as it occurs sometimes but not always.

Some corespondents seem enamored by introducing a mysticism category to
the halting problem and believing they have escaped earthly shackles. I
am trying to dispel this idea with one blow.
--
Jeff Barnett

On Wed, 3 Aug 2022 15:09:15 -0600
Jeff Barnett <jbb@notatt.com> wrote:

> On 8/3/2022 2:49 PM, Ben Bacarisse wrote:
> > Mr Flibble <flibble@reddwarf.jmc.corp> writes:
> >
> >> On Tue, 2 Aug 2022 23:49:40 -0600
> >> Jeff Barnett <jbb@notatt.com> wrote:
> >
> >>> Note that it makes little difference what is meant by
> >>> "pathological", it is what Hitchcock called a MacGuffin. It may
> >>> give us something to talk about but it has little to do with the
> >>> problem at hand: namely whether a halt decider could exist.
> >>
> >> GIGO I'm afraid.
> >
> > Also sane input in, garbage out. A three-state quasi-decider must
> > report "pathological" for an infinite number of cases, all of which
> > either halt or don't halt. Many of which have nothing to do with
> > any particular kind of "pathological". Any attempt to pin down
> > "pathological" beyond simply being the cases about which the
> > quasi-decider declines to commit itself is doomed.
> >
> > It would help, I am sure, if people who want to jump into
> > long-solved problems like this, knew just a little bit more. For
> > example, what are the "pathological" inputs for other undecidable
> > sets? Given strings that represent context-free grammars (in, say,
> > BNF), the subset that represent ambiguous grammars is undecidable.
> > What are the "pathological" cases now?
> >
> > And then there are simple-looking programming puzzles like Post's
> > correspondence problem. Any attempt at a solution must report
> > "yes", "no" or "pathological" because the "yes" and "no" sets are
> > undecidable. So what's does a pathological instance of the this
> > trivial problem look like?
> >
> > In the end, "pathological" is just "those cases that this algorithm
> > refuses to commit to". And note it depends on the algorithm. Other
> > programs will most likely commit to an answer for different sets of
> > cases. There are no intrinsically "hard" cases.
> I agree. However almost any "Rice" like will do. It's hopeless
> whatever the definition is as long as it occurs sometimes but not
> always.
>
> Some corespondents seem enamored by introducing a mysticism category
> to the halting problem and believing they have escaped earthly
> shackles. I am trying to dispel this idea with one blow.

Which you have failed to do (see my reply).

/Flibble

On Wed, 03 Aug 2022 21:49:34 +0100
Ben Bacarisse <ben.usenet@bsb.me.uk> wrote:

> Mr Flibble <flibble@reddwarf.jmc.corp> writes:
>
> > On Tue, 2 Aug 2022 23:49:40 -0600
> > Jeff Barnett <jbb@notatt.com> wrote:
>
> >> Note that it makes little difference what is meant by
> >> "pathological", it is what Hitchcock called a MacGuffin. It may
> >> give us something to talk about but it has little to do with the
> >> problem at hand: namely whether a halt decider could exist.
> >
> > GIGO I'm afraid.
>
> Also sane input in, garbage out. A three-state quasi-decider must
> report "pathological" for an infinite number of cases, all of which
> either halt or don't halt. Many of which have nothing to do with any
> particular kind of "pathological". Any attempt to pin down
> "pathological" beyond simply being the cases about which the
> quasi-decider declines to commit itself is doomed.
>
> It would help, I am sure, if people who want to jump into long-solved
> problems like this, knew just a little bit more. For example, what
> are the "pathological" inputs for other undecidable sets? Given
> strings that represent context-free grammars (in, say, BNF), the
> subset that represent ambiguous grammars is undecidable. What are the
> "pathological" cases now?
>
> And then there are simple-looking programming puzzles like Post's
> correspondence problem. Any attempt at a solution must report "yes",
> "no" or "pathological" because the "yes" and "no" sets are
> undecidable. So what's does a pathological instance of the this
> trivial problem look like?
>
> In the end, "pathological" is just "those cases that this algorithm
> refuses to commit to". And note it depends on the algorithm. Other
> programs will most likely commit to an answer for different sets of
> cases. There are no intrinsically "hard" cases.
There is only ONE case of pathological input: the contradiction of
[Strachey 1965]; my signaling halt decider detects this ONE AND ONLY
case.

/Flibble

On 8/3/2022 3:56 PM, Keith Thompson wrote:
> olcott <NoOne@NoWhere.com> writes:
> [...]
>> To get us on the same page I rephrased my statement based on your critique:
>>
>> *THIS IS REALLY NOT THAT HARD*
>> Everyone knows that a pure function can only return values based on
>> its actual arguments and cannot return values on any other basis.
>
> Better. In fact that's nearly tautological; that's part of the
> definition of "pure function". (Not all of it; a function that returns
> a result based only on its arguments but also has side effects is not
> pure.)
>
> If you're going to talk about functions in some programming language, I
> strongly suggest not assuming that such functions are pure. If you want
> to talk about pure functions, that's fine; even if a language has no
> such concept (C doesn't mention it), the meaning is clear enough.
>
> More generally, if you're going to talk about code in some programming
> language, use that language's terminology if you want to be understood.
> The word "input" is well defined in C, and it has nothing to do with a
> function's arguments/parameters.
>
> [...]
>
>> *It seems that you and I both agree that a pure function cannot do that*
>> *Thanks for you review, I really appreciate your technical competence*
>
> Again, I agree with your statement simply because that's (part of) the
> definition of a pure function.
>
> Do not assume that I agree with you about anything else.
>

I am not. Your one review by itself was very very helpful. I had
forgotten where I got the idea from until you mentioned pure function.
Your critique of my terminology was also very helpful I will convert my
paper to use this terminology.

*DOES THIS SEEM TO MAKE SENSE TO YOU FROM A SOFTWARE ENGINEERING POV*?
When H is a simulating halt decider it must base it halt status decision
on the actual behavior actually specified by its arguments (pointers to
the machine code of P) as measured by the correct x86 emulation of this
machine code performed by H.

--
Copyright 2022 Pete Olcott

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

On 8/3/2022 3:49 PM, Ben Bacarisse wrote:
> Mr Flibble <flibble@reddwarf.jmc.corp> writes:
>
>> On Tue, 2 Aug 2022 23:49:40 -0600
>> Jeff Barnett <jbb@notatt.com> wrote:
>
>>> Note that it makes little difference what is meant by "pathological",
>>> it is what Hitchcock called a MacGuffin. It may give us something to
>>> talk about but it has little to do with the problem at hand: namely
>>> whether a halt decider could exist.
>>
>> GIGO I'm afraid.
>
> Also sane input in, garbage out. A three-state quasi-decider must
> report "pathological" for an infinite number of cases, all of which
> either halt or don't halt. Many of which have nothing to do with any
> particular kind of "pathological". Any attempt to pin down
> "pathological" beyond simply being the cases about which the
> quasi-decider declines to commit itself is doomed.
>
> It would help, I am sure, if people who want to jump into long-solved
> problems like this, knew just a little bit more. For example, what are
> the "pathological" inputs for other undecidable sets? Given strings
> that represent context-free grammars (in, say, BNF), the subset that
> represent ambiguous grammars is undecidable. What are the
> "pathological" cases now?
>
> And then there are simple-looking programming puzzles like Post's
> correspondence problem. Any attempt at a solution must report "yes",
> "no" or "pathological" because the "yes" and "no" sets are undecidable.
> So what's does a pathological instance of the this trivial problem look
> like?
>
> In the end, "pathological" is just "those cases that this algorithm
> refuses to commit to". And note it depends on the algorithm. Other
> programs will most likely commit to an answer for different sets of
> cases. There are no intrinsically "hard" cases.
>

Pathological self-reference cases are generally isomorphic to the liar
paradox and have the form that both YES and NO answers result in a
contradiction. The liar paradox sentence: "This sentence is not true."
is simply not a truth bearer thus asking whether or not it is true or
false is like asking is 10::00 PM true or false?

--
Copyright 2022 Pete Olcott

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

On 8/3/22 12:40 PM, olcott wrote:
> On 8/3/2022 10:49 AM, Mike Terry wrote:
>> On 03/08/2022 06:49, Jeff Barnett wrote:
>>> Many of you think that it is possible to make/code a three-way
>>> decision function that takes as arguments a description of a
>>> computation and arguments for it; F(A) will be used t9 refer to the
>>> actual computation with arguments. Three descriptive results shall be
>>> possible and the one chosen depends on F(A). The three possibilities are
>>>      H if F(A) halts, L if F(A) is pathological, L if F(A) loops
>>> forever.
>>
>> You mean P if F(A) is pathelogical I think.
>>
>> You need to say more about what pathelogical means - I know that below
>> you say it hardly matters, so fair enough, let's take it for now that
>> EVERY computation is deemed pathelogical.  That's certainly a
>> decidable property of a computation...  Then a decider can just
>> returns P straight away, which is correct, it would seem!
>>
>> Below you are suggesting this doesn't work, so let's see what's going
>> on...
>>
>>> The assumption is that there is a decide, H, which given the
>>> arguments F and A, always itself halts and determines the correct one
>>> of H, L, and P. The following code, based on the disproof of the
>>> halting problem in Linz, shows that this too is impossible:
>>
>> Seems you make a big assumption: " *THE* correct one of H, L, and P",
>> but a halting program could be deemed pathelogical as could a
>> non-halting program.  In PO's case, he deems P(P) pathelogical (for
>> whatever reason), and P(P) halts.
>>
> I never said anything like that. It seems that the reason that you don't
> understand me is that you don't pay enough attention.
>
> H and P have been defined to have a pathological relationship to each
> other.

Except that you seemed to have missed the " " because the relationship
is commonly CALLED pathological, but it not technically pathological, as
the relationship between P and H if fully defined by the rules of
Computaton, so there isn't any "patho" in the relationship.

The only "disease" that is there is the fatal damage it inflect on the
idea that it might be possible to create an actual universally correct
halt decider.

>
>    For any program H that might determine if programs halt, a
>    "pathological" program P, called    with some input, can pass
>    its own source and its input to H and then  specifically do the
>    opposite of what H predicts P will do.
>    *No H can exist that handles this case*
>    https://en.wikipedia.org/wiki/Halting_problem
>
> typedef void (*ptr)();
> int H(ptr p, ptr i); // simulating halt decider
>
> void P(ptr x)
> {
>   int Halt_Status = H(x, x);
>   if (Halt_Status)
>     HERE: goto HERE;
>   return;
> }
>
> int main()
> {
>   Output("Input_Halts = ", H(P, P));
> }
>
>
> *THIS IS REALLY NOT THAT HARD*
> Everyone knows that a software function can only return values based on
> its actual input and cannot return values based on non-input.

Right, and the input to H(P,P) is the x86 code of the program P, and the
input to that code, which is the x86 code of the program P.

That is how H has been defined to give it the question to decide on the
behavior of P(P), so that IS the input.

>
> When H(P,P) is invoked from main the full execution trace is
> H(P,P) simulates P(P) calls simulated H(P,P)
>
> When P(P) is invoked from main the full execution trace is
> P(P) invokes H(P,P) simulates P(P) calls simulated H(P,P)

Nope, not as far as H is concerned. Are you admitting that H isn't a
Pure function?

When P(P) calls H(P,P) the execution trace that affects H is :

H(P,P) simulated P(P) which calls a simulated H(P,P).

Exactly the same.

>
> Because the executed P(P) depends on the return value of H(P,P) and the
> simulated P(P) cannot possibly have this same dependency** their
> behavior is not the same.

Why can't the simulated P(P) have that dependency?

Is it because H can't figure it out?

Why is that P's problem?

Of COURSE the simulated P(P) can depend on the return value of the
simulate H(P,P), which needs to match the actual call to H(P,P) or the
simulation is incorrect.

Don't you understand how simulations work?

>
> ** It is stuck in what is essentially infinite recursion, thus cannot
> receive any value from H(P,P). This prevents the simulated P from doing
> the opposite of whatever H(P,P) returns to it because H(P,P) never
> returns to it. No function called in what is essentially infinite
> recursion ever returns to its caller.

It maybe be "essentially" infinite recursion because H can't resolve
what it does, but it isn't ACTUAL infinite recursion because the defined
H DOES abort its simulation and return 0, which breaks the apparant
infinite recursion and make P(P) a Halting Computation.

>
> int sum(int x, int y) { return x + y; }
> For H(P,P) to return a value for a different sequence of instructions
> than the one specified by its input would be the same as if sum(3,4)
> returning the sum of 4+5.
>
>

What is the diffence in the sequence of instructions given to it
compared to the actual instructuctions of P?

If they are, doesn't that mean that P was defined wrong, since P was
DEFINED to call H to ask how it will decide on P(P).

Also, if ONE call to H(P,P) refers to P(P), so H can be "correct" on
deciding about this, then ALL calls must to. Or, are you admitting that
H can't ACTUALLY answer about the Turing Machine P(P), and thus fails to
be the needed halt decider. Remember, Halting is DEFINED based on the
Machines, and Halt Deciders decide on the Machines, not their own
simulations thereof.

On 8/3/22 2:04 PM, olcott wrote:
> On 8/3/2022 12:51 PM, Skep Dick wrote:
>> On Wednesday, 3 August 2022 at 19:46:58 UTC+2, olcott wrote:
>>> None-the-less you do not have permission to misrepresent what I said:
>> Nobody gave you permission to misrepresent Turing; or a 100 year old
>> field of research, yet here you are.
>>
>> Thousands of hours into it...
>
> I am not misrepresenting Turing.
> I found a loophole in the HP proofs that negate them.
>

Nope, you are just showing you don't understand Turing.

The fact that you look at the PARTIAL simulation done by H(P,P) to show
halting and then quote the definition that Halting is based on the
Turing Machine reaching a final state just shows that you don't
understand what a Turing Machine is.

You also don't seem to understand what a Computation, Representation,
Universal Turing Machine, Halting, Proof, Truth, Formal Logic, or any of
a number of other terms actually mean.

In other words, you have proved yourself to be IGNORANT of the field you
are making grand schemes about.

Note, you have show that you can't even write 1st year student Turing
Machines because you dropped out of your training when it got to the
point of actually trying to actually code one.

On 8/3/22 5:09 PM, Jeff Barnett wrote:
> I agree. However almost any "Rice" like will do. It's hopeless whatever
> the definition is as long as it occurs sometimes but not always.
>
> Some corespondents seem enamored by introducing a mysticism category to
> the halting problem and believing they have escaped earthly shackles. I
> am trying to dispel this idea with one blow.

I think the key here is that the Halting Problem was the first such
problem shown to be non-solvable (I think). Once that was shown, then a
number of other problems where showable to have the same attribute,
sometimes using a similar proof (related but not directly based on), and
sometimes a new more novel method was found.

This is common for many perceived barriers. They seem big untill the
first person breaks it, then others, knowing that the barrier wasn't
insurmountable, find other holes in it.

On 8/3/22 6:44 PM, olcott wrote:
> On 8/3/2022 3:49 PM, Ben Bacarisse wrote:
>> Mr Flibble <flibble@reddwarf.jmc.corp> writes:
>>
>>> On Tue, 2 Aug 2022 23:49:40 -0600
>>> Jeff Barnett <jbb@notatt.com> wrote:
>>
>>>> Note that it makes little difference what is meant by "pathological",
>>>> it is what Hitchcock called a MacGuffin. It may give us something to
>>>> talk about but it has little to do with the problem at hand: namely
>>>> whether a halt decider could exist.
>>>
>>> GIGO I'm afraid.
>>
>> Also sane input in, garbage out.  A three-state quasi-decider must
>> report "pathological" for an infinite number of cases, all of which
>> either halt or don't halt.  Many of which have nothing to do with any
>> particular kind of "pathological".  Any attempt to pin down
>> "pathological" beyond simply being the cases about which the
>> quasi-decider declines to commit itself is doomed.
>>
>> It would help, I am sure, if people who want to jump into long-solved
>> problems like this, knew just a little bit more.  For example, what are
>> the "pathological" inputs for other undecidable sets?  Given strings
>> that represent context-free grammars (in, say, BNF), the subset that
>> represent ambiguous grammars is undecidable.  What are the
>> "pathological" cases now?
>>
>> And then there are simple-looking programming puzzles like Post's
>> correspondence problem.  Any attempt at a solution must report "yes",
>> "no" or "pathological" because the "yes" and "no" sets are undecidable.
>> So what's does a pathological instance of the this trivial problem look
>> like?
>>
>> In the end, "pathological" is just "those cases that this algorithm
>> refuses to commit to".  And note it depends on the algorithm.  Other
>> programs will most likely commit to an answer for different sets of
>> cases.  There are no intrinsically "hard" cases.
>>
>
> Pathological self-reference cases are generally isomorphic to the liar
> paradox and have the form that both YES and NO answers result in a
> contradiction. The liar paradox sentence: "This sentence is not true."
> is simply not a truth bearer thus asking whether or not it is true or
> false is like asking is 10::00 PM true or false?
>

Except that isomorphism isn't correct.

It is a fact that the machine M(x) WILL or WILL NOT Halt, so the
statement M(x) Halts, WILL be true or false. So the Sentence has a Truth
Value, and thus the Question "Does H(x) Halt?" ALWAYS has an answer.

That is NOT true of the Liars Paradox, the basic sentence doesn't have a
truth value.

You run into the paradox with the Halting Problem when you ask a
DIFFERENT question, What Should H return to give the correct answer for
H(P,P)?

The problem is that isn't a question about AN algorithm, but of
algorithm design, and thus not actually part of the halting problem.

The Halting problem says that ANY H that you think might be an actual
Halt Decider, can be proved to not be one, because it will get H(P,P)
wrong. The problem STARTS with a definite algorithm being proposed as a
solution.

When we look at the design question, the fact that we hit the paradox
doesn't say the quesiton is incorrect, but that it is impossible to
answer the question under the speciried restrictions (needing to make a
COMPUTATION to answer the question).

Jeff Barnett <jbb@notatt.com> writes:

> On 8/3/2022 2:49 PM, Ben Bacarisse wrote:
>> Mr Flibble <flibble@reddwarf.jmc.corp> writes:
>>
>>> On Tue, 2 Aug 2022 23:49:40 -0600
>>> Jeff Barnett <jbb@notatt.com> wrote:
>>
>>>> Note that it makes little difference what is meant by "pathological",
>>>> it is what Hitchcock called a MacGuffin. It may give us something to
>>>> talk about but it has little to do with the problem at hand: namely
>>>> whether a halt decider could exist.
>>>
>>> GIGO I'm afraid.
>> Also sane input in, garbage out. A three-state quasi-decider must
>> report "pathological" for an infinite number of cases, all of which
>> either halt or don't halt. Many of which have nothing to do with any
>> particular kind of "pathological". Any attempt to pin down
>> "pathological" beyond simply being the cases about which the
>> quasi-decider declines to commit itself is doomed.
>> It would help, I am sure, if people who want to jump into long-solved
>> problems like this, knew just a little bit more. For example, what are
>> the "pathological" inputs for other undecidable sets? Given strings
>> that represent context-free grammars (in, say, BNF), the subset that
>> represent ambiguous grammars is undecidable. What are the
>> "pathological" cases now?
>> And then there are simple-looking programming puzzles like Post's
>> correspondence problem. Any attempt at a solution must report "yes",
>> "no" or "pathological" because the "yes" and "no" sets are undecidable.
>> So what's does a pathological instance of the this trivial problem look
>> like?
>> In the end, "pathological" is just "those cases that this algorithm
>> refuses to commit to". And note it depends on the algorithm. Other
>> programs will most likely commit to an answer for different sets of
>> cases. There are no intrinsically "hard" cases.
>
> I agree. However almost any "Rice" like will do. It's hopeless
> whatever the definition is as long as it occurs sometimes but not
> always.

I don't know what you are getting at here. The property labelled
"pathological" does not have to be Rice-like. Of course it's more
interesting when the discussion heads off in that direction, but there's
no reason the third category has to be undecidable.

> Some corespondents seem enamored by introducing a mysticism category
> to the halting problem and believing they have escaped earthly
> shackles. I am trying to dispel this idea with one blow.

I think it's better to avoid it altogether, but it easy to get sucked
in. A decider halts on, and accepts or rejects, every input, and
although Mr Flibble has been quite clear that he's not talking about a
halt decider, he still wants to keep posting. It's just what cranks do.

--
Ben.

On 8/3/2022 6:17 PM, Ben Bacarisse wrote:
> Jeff Barnett <jbb@notatt.com> writes:
>
>> On 8/3/2022 2:49 PM, Ben Bacarisse wrote:
>>> Mr Flibble <flibble@reddwarf.jmc.corp> writes:
>>>
>>>> On Tue, 2 Aug 2022 23:49:40 -0600
>>>> Jeff Barnett <jbb@notatt.com> wrote:
>>>
>>>>> Note that it makes little difference what is meant by "pathological",
>>>>> it is what Hitchcock called a MacGuffin. It may give us something to
>>>>> talk about but it has little to do with the problem at hand: namely
>>>>> whether a halt decider could exist.
>>>>
>>>> GIGO I'm afraid.
>>> Also sane input in, garbage out. A three-state quasi-decider must
>>> report "pathological" for an infinite number of cases, all of which
>>> either halt or don't halt. Many of which have nothing to do with any
>>> particular kind of "pathological". Any attempt to pin down
>>> "pathological" beyond simply being the cases about which the
>>> quasi-decider declines to commit itself is doomed.
>>> It would help, I am sure, if people who want to jump into long-solved
>>> problems like this, knew just a little bit more. For example, what are
>>> the "pathological" inputs for other undecidable sets? Given strings
>>> that represent context-free grammars (in, say, BNF), the subset that
>>> represent ambiguous grammars is undecidable. What are the
>>> "pathological" cases now?
>>> And then there are simple-looking programming puzzles like Post's
>>> correspondence problem. Any attempt at a solution must report "yes",
>>> "no" or "pathological" because the "yes" and "no" sets are undecidable.
>>> So what's does a pathological instance of the this trivial problem look
>>> like?
>>> In the end, "pathological" is just "those cases that this algorithm
>>> refuses to commit to". And note it depends on the algorithm. Other
>>> programs will most likely commit to an answer for different sets of
>>> cases. There are no intrinsically "hard" cases.
>>
>> I agree. However almost any "Rice" like will do. It's hopeless
>> whatever the definition is as long as it occurs sometimes but not
>> always.
>
> I don't know what you are getting at here. The property labelled
> "pathological" does not have to be Rice-like. Of course it's more
> interesting when the discussion heads off in that direction, but there's
> no reason the third category has to be undecidable.

Rice-like meant to me a property that some but not all instances had. It
makes little difference to my original post whether that property can be
effectively detected.

>> Some corespondents seem enamored by introducing a mysticism category
>> to the halting problem and believing they have escaped earthly
>> shackles. I am trying to dispel this idea with one blow.
>
> I think it's better to avoid it altogether, but it easy to get sucked
> in. A decider halts on, and accepts or rejects, every input, and
> although Mr Flibble has been quite clear that he's not talking about a
> halt decider, he still wants to keep posting. It's just what cranks do.
--
Jeff Barnett

olcott <NoOne@NoWhere.com> writes:
> On 8/3/2022 3:56 PM, Keith Thompson wrote:
[...]
>> Again, I agree with your statement simply because that's (part of)
>> the
>> definition of a pure function.
>> Do not assume that I agree with you about anything else.
>>
>
> I am not. Your one review by itself was very very helpful. I had
> forgotten where I got the idea from until you mentioned pure
> function. Your critique of my terminology was also very helpful I will
> convert my paper to use this terminology.
>
> *DOES THIS SEEM TO MAKE SENSE TO YOU FROM A SOFTWARE ENGINEERING POV*?
> When H is a simulating halt decider it must base it halt status
> decision on the actual behavior actually specified by its arguments
> (pointers to the machine code of P) as measured by the correct x86
> emulation of this machine code performed by H.

I'm not sufficiently interested to take the time to determine what it
means or whether it refers to anything that can actually exist.

--
Keith Thompson (The_Other_Keith) Keith.S.Thompson+u@gmail.com
Working, but not speaking, for Philips
void Void(void) { Void(); } /* The recursive call of the void */