A decider that can detect "pathological" cases as well as halting.

[Jeff Barnett]

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

[Mike Terry]

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.

[olcott]

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

[Mike Terry]

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.

[olcott]

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).

[Skep Dick]

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...

[olcott]

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

[Keith Thompson]

olcott <No...@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.T...@gmail.com
Working, but not speaking, for Philips
void Void(void) { Void(); } /* The recursive call of the void */

[olcott]

On 8/3/2022 1:35 PM, Keith Thompson wrote:
> olcott <No...@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

[Mr Flibble]

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

[Ben Bacarisse]

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

> On Tue, 2 Aug 2022 23:49:40 -0600
> Jeff Barnett <j...@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.

[Keith Thompson]

olcott <No...@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

[Jeff Barnett]

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.

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

[Jeff Barnett]

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

[Mr Flibble]

On Wed, 3 Aug 2022 15:09:15 -0600

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

/Flibble

[Mr Flibble]

There is only ONE case of pathological input: the contradiction of
[Strachey 1965]; my signaling halt decider detects this ONE AND ONLY
case.

/Flibble

[olcott]

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.

[olcott]

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?

[Richard Damon]

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.

[Richard Damon]

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.

[Richard Damon]

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.

[Richard Damon]

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).

[Ben Bacarisse]

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.

[Jeff Barnett]

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

[Keith Thompson]

olcott <No...@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.

[olcott]

On 8/3/2022 9:18 PM, Keith Thompson wrote:
> olcott <No...@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.
>

You wouldn't be interested if someone correctly refuted the most
important computer science theorem that exists?

Anyway great thanks for your critique it was very excellent and very
helpful.

[Ben Bacarisse]

Jeff Barnett <j...@notatt.com> writes:

> On 8/3/2022 6:17 PM, Ben Bacarisse wrote:
>> Jeff Barnett <j...@notatt.com> writes:
>>
>>> On 8/3/2022 2:49 PM, Ben Bacarisse wrote:

>>>> 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.

OK. Strange to reference Rice then.

--
Ben.

[Richard Damon]

On 8/3/22 10:45 PM, olcott wrote:
> On 8/3/2022 9:18 PM, Keith Thompson wrote:
>> olcott <No...@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.
>>
>
> You wouldn't be interested if someone correctly refuted the most
> important computer science theorem that exists?

We would be, but you haven't done it.

Your "Proof" has so many errors that you just refuse to look at and try
to fix, that it is clear that you are incapable of even coming close to it.

[Jeff Barnett]

Not so strange. The (main?) assumption in the Rice's theorem is that the
property that is to be decided pertains in some but not all instances of
the domain. And that's about all I'm assuming here.
--
Jeff Barnett

[Skep Dick]

Function self-application leads to unsound logic.
In Lambda calculus it leads to non-terminating behaviour.

We know this. It is a fact about computation. Why is this fact “pathological” to you?

https://math.stackexchange.com/questions/1316377/self-application-in-churchs-untyped-lambda-calculus

[Ben Bacarisse]

Oh, sorry. I thought you were claiming something interesting. Why you
do need three results to report on one case? Why does it have to be so
complicated to report on just one case? A one-liner that just "signals"
is all yo need.

--
Ben.

[Ben Bacarisse]

The properties referred to in Rice's theorem are those of the languages
of TMs, but "pathological" /might/ be defined to be a decidable property
of TMs themselves or, indeed, of TM/input pairs. It just seems weird to
reference his name at all in this context.

--
Ben.

[Skep Dick]

On Thursday, 4 August 2022 at 11:10:20 UTC+2, Ben Bacarisse wrote:
> The properties referred to in Rice's theorem are those of the languages
> of TMs

Yes. Those are all the "trivial" (syntactic) properties (of programs) the theorem speaks about.

> but "pathological" /might/ be defined to be a decidable property
> of TMs themselves or, indeed, of TM/input pairs. It just seems weird to
> reference his name at all in this context.

Yes. Those are all the non-trivial (semantic) properties (of programs) the theorem speaks about.

You can look at it from another perspective really. Intensional vs extensional definitions of TMs.

What does a TM return if its tape contains just three symbols: x=x? What does this expression evaluate to?

Well, in some Turing Machines it may evaluate to True, and in other Turing Machines it may evaluate to False.

[olcott]

It is the basis of undecidability.

[Andy Walker]

On 04/08/2022 03:45, olcott wrote:
> You wouldn't be interested if someone correctly refuted the most
> important computer science theorem that exists?

Every man and his dog would be interested if someone did. But
the only possible /refutation/ of the theorem [as opposed to finding
some flaw in one of the many proofs] would be an actual working "H"
that is an actual working halt decider, and if someone claims to have
provided such an "H", then every man and his dog knows how to provide
an actual "program+data" that "H" cannot handle. Please don't rely
on finding an "H" that handles the "impossible program" of the Wiki
entry you are so keen to keep on repeating; as I wrote yesterday,
that entry is misleading and you have been misled.

Do instead learn about Busy Beavers, which are [IMNSHO] the
simplest route into understanding /why/ emulators don't/can't solve
the HP, and note how BBs and the HP inter-relate. You are much,
/much/, *much* more likely to find out something new and interesting
about BBs, still an active area of investigation, than about the HP,
long since dead and buried. Despite occasional misguided attempts
here to resurrect it.

--
Andy Walker, Nottingham.
Andy's music pages: www.cuboid.me.uk/andy/Music
Composer of the day: www.cuboid.me.uk/andy/Music/Composers/Peerson

[Skep Dick]

Yes. And?

Why is undecidability pathological to you?

It's just a fact of life.

[Malcolm McLean]

On Thursday, 4 August 2022 at 12:54:11 UTC+1, Andy Walker wrote:
>
> Do instead learn about Busy Beavers, which are [IMNSHO] the
> simplest route into understanding /why/ emulators don't/can't solve
> the HP, and note how BBs and the HP inter-relate. You are much,
> /much/, *much* more likely to find out something new and interesting
> about BBs, still an active area of investigation, than about the HP,
> long since dead and buried. Despite occasional misguided attempts
> here to resurrect it.
>

Busy Beavers are fun as well.You get a lot of output for a small
amount of programming effort.

[Ben Bacarisse]

Skep Dick <skepd...@gmail.com> writes:

> On Thursday, 4 August 2022 at 11:10:20 UTC+2, Ben Bacarisse wrote:
>> The properties referred to in Rice's theorem are those of the languages
>> of TMs
>
> Yes. Those are all the "trivial" (syntactic) properties (of programs)
> the theorem speaks about.

I was talking about the non-trivial properties which are the only ones
the Rice's theorem talks about. It may be that the phrase "the
languages of TMs" is unfamiliar. Rice's theorem is about deciding sets
of (index numbers of) TMs whose languages have some non-trivial property
(i.e. one possessed by at least one and not shared by all).

>> but "pathological" /might/ be defined to be a decidable property
>> of TMs themselves or, indeed, of TM/input pairs. It just seems weird to
>> reference his name at all in this context.
>
> Yes. Those are all the non-trivial (semantic) properties (of programs)
> the theorem speaks about.

Again, it's the other way round. Referencing Rice seems to me mistaken
because a quasi halt decider can signal as "pathological" a trivial,
decidable, set of TM/input pairs.

> You can look at it from another perspective really. Intensional vs
> extensional definitions of TMs.

Can you say more? That's a distinction I've not come across.

> What does a TM return if its tape contains just three symbols: x=x?
> What does this expression evaluate to?
>
> Well, in some Turing Machines it may evaluate to True, and in other
> Turing Machines it may evaluate to False.

Yes, and depending on what you mean by "evaluate to" there may be many
other possibilities as well!

A TM that halts on every initial tape, by definition, decides (or is a
decider for) a subset of Σ*. If M is the set of all TMs, we can define
injective functions

e: M -> Σ*
p: Σ* x Σ* -> Σ*

and then prove that no decider has the language

{ p(e(m),i) | m(i) halts }

The alphabet and the "encoding" functions are part of the theorem. Is
that, in part, what you are getting at?

--
Ben.

[Ben Bacarisse]

Yes, and it's been suggested that PO lean about them many times in the
last couple of decades. I see no reason for him to change direction
now. The very fact that they have been suggested as a way for him to
grasp his mistake is likely to put him off altogether.

--
Ben.

[Newberry]

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.

> 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.

#include <stdio.h>
#define DEPTH (1000)
#define INITIALIZE level = 0; k = (unsigned int)C_k; \
s = (unsigned int)C_s;

static int level = 0;
unsigned int s, k;

A(unsigned int n, unsigned int m); // Forward declaration

int checkStack(void) {
level++;
if (level >= DEPTH){
printf("Almost got there. Have run out of stack.\n\n");
level--;
return 1;
}
return 0;
}

C_k(unsigned int n) {
A(n,n);
}

C_s() {
C_k(s);
}

// If A(n,m) halts then C_n(m) does NOT halt.
A(unsigned int n, unsigned int m) {
if ( checkStack() ) return;
// . . . . .
if (n == s) C_s();
// . . . . .
if (n == k && m == s) {
// Analyze what happens when A() calls C_s()
// Does C_s() have a base case?
printf("Program C_%u( %u ) does NOT halt.\n\n", n, m);
}
// . . . . .
level--;
}

Getting Around the Halting Problem
https://www.researchgate.net/publication/316562253_Getting_around_the_Halting_Problem

[olcott]

Rice’s theorem states that no nontrivial semantic property of a given
Turing Machine can be decidable. A semantic property of a Turing Machine
is one that concerns its behavior, like whether or it halts on all
inputs or its runtime. It can be seen as a more general version of the
Halting Problem, but the proof relies on a reduction to the Halting
Problem.

Some examples of such numbers are Chaitin’s Constant and the Busy Beaver
Numbers. We present proofs on their uncomputability using reductions to
the Halting Problem, similar to what was done previously with
decidability problems.
https://mathcsr.org/articles/computerscience/Vol2_No2/turing-machines

If the HP proof is refuted then when we reduce Rice and Busy Beaver to
the refuted HP proof they would seem to be refuted too.

[olcott]

On 8/4/2022 6:54 AM, Andy Walker wrote:
> On 04/08/2022 03:45, olcott wrote:
>> You wouldn't be interested if someone correctly refuted the most
>> important computer science theorem that exists?
>
>     Every man and his dog would be interested if someone did.  But
> the only possible /refutation/ of the theorem [as opposed to finding
> some flaw in one of the many proofs] would be an actual working "H"
> that is an actual working halt decider, and if someone claims to have
> provided such an "H", then every man and his dog knows how to provide
> an actual "program+data" that "H" cannot handle.  Please don't rely
> on finding an "H" that handles the "impossible program" of the Wiki
> entry you are so keen to keep on repeating;  as I wrote yesterday,
> that entry is misleading and you have been misled.
>
>     Do instead learn about Busy Beavers, which are [IMNSHO] the
> simplest route into understanding /why/ emulators don't/can't solve
> the HP, and note how BBs and the HP inter-relate.  You are much,
> /much/, *much* more likely to find out something new and interesting
> about BBs, still an active area of investigation, than about the HP,
> long since dead and buried.  Despite occasional misguided attempts
> here to resurrect it.
>

*MOST EVERYONE HERE CAN VERIFY THIS IS LESS THAN FIVE MINUTES*
It is the case that every HP counter-example P including Linz does
present infinitely recursive simulation to its simulating halt decider
H. This prevents prevents P from doing the opposite of whatever H
decides and gives H a basis to decide that P never halts.

Rice’s theorem states that no nontrivial semantic property of a given
Turing Machine can be decidable. A semantic property of a Turing Machine
is one that concerns its behavior, like whether or it halts on all
inputs or its runtime. It can be seen as a more general version of the
Halting Problem, but the proof relies on a reduction to the Halting Problem.

Some examples of such numbers are Chaitin’s Constant and the Busy Beaver
Numbers. We present proofs on their uncomputability using reductions to
the Halting Problem, similar to what was done previously with
decidability problems.
https://mathcsr.org/articles/computerscience/Vol2_No2/turing-machines

If the HP proof is refuted then when we reduce Rice and Busy Beaver to
the refuted HP proof they would seem to be refuted too.

[olcott]

The false notion of undecidability seems to prove that the concept of
truth itself is broken.

[Mr Flibble]

On Thu, 04 Aug 2022 09:42:01 +0100

Stop being so obtuse: by single case I am referring to any attempt to
contradict the halt decision from within the simulation; obviously
normal halting and non-halting are also reported normally (not as a
signal).

/Flibble

[Mike Terry]

On 03/08/2022 22:01, Jeff Barnett wrote:
> 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.

Your responses have a strong element of bluff about them. I understand you wanted to point out that
inventing a 3rd category of response "pathelogical" wont help avoid the HP conclusion - the new
3-way decider will still be impossible due to a similar argument.

This isn't really correct, at least not without considerable restrictions on what "pathelogical" can
mean. Perhaps you could instead have made post about how inventing a new category of response does
has no effect on the status (and fundamental interest) of the HP results - that would have been fair
enough, although nothing new.

(I won't reply to each of your responses.)


Regards,
Mike.

[Andy Walker]

On 04/08/2022 16:00, olcott wrote:
> It is the case that every HP counter-example P [...]

There is, and can be, no "HP counter-example". You have misled
yourself about what Linz, Sipser and the Wiki paragraph you quote are
saying.

> If the HP proof is refuted then when we reduce Rice and Busy Beaver
> to the refuted HP proof they would seem to be refuted too.

It's not enough to refute an "HP proof". Compare the 4-colour
theorem, where all the early proofs were refuted, but the only way to
refute the /theorem/ would have been to produce a suitable map that
could not be 4-coloured. Further, the other side of your coin is that
since the BB function is manifestly uncomputable [there is an easy
proof that has no connexion with the HP, see Wiki], the HP result is
thereby established. Of course, as Ben points out from time to time,
there are several other HP proofs, inc Linz's preferred proof, given
in the pages you used to quote.

It really would help you if you tried to understand the above
before repeating your previous posts.

[Skep Dick]

On Thursday, 4 August 2022 at 17:02:42 UTC+2, olcott wrote:
> The false notion of undecidability seems to prove that the concept of
> truth itself is broken.

Why?

Either it's true that a particualr function halts;
or it's true that a particular function doesn't halt;
or it's true that you don't know whether it halts or not.

[Ben Bacarisse]

Newberry <newbe...@gmail.com> writes:

> C_k(unsigned int n) {
> A(n,n);
> }
>
> C_s() {
> C_k(s);
> }
>
> // If A(n,m) halts then C_n(m) does NOT halt.
> A(unsigned int n, unsigned int m) {

You need to change programming language. The comment refers to C_n in
the context of n being an unsigned int. That is, C_n is talked about as
if it is a family of functions, but the two you written out are just
functions with an underscore in the name (and they have different types
so C_k and C_s can not both be the same kind of function as the C_n).

In a language with higher-order function you would, I think, be able to
say what you want to say.

--
Ben.

[Skep Dick]

On Thursday, 4 August 2022 at 22:40:18 UTC+2, Ben Bacarisse wrote:
> In a language with higher-order function you would, I think, be able to
> say what you want to say.

This is the crux of it, in this part of the woods.

Turing computability only concerns itself with functions from N -> N. For higher order functions not all models of computations are Turing-equivalent - questions of representation/encoding become relevant. Some models of computation (programming languages) are more equal than others.

Which is why all the software engineers on this thread are outraged. They are intuitively using their favourite programming language as their default model of computation. That language happens to be strictly-evaluated (whereas all of Mathematics is lazy-evaluated) and they can't resolve the semantic gap between the two.

[olcott]

On 8/4/2022 3:05 PM, Andy Walker wrote:
> On 04/08/2022 16:00, olcott wrote:
>> It is the case that every HP counter-example P [...]
>
>     There is, and can be, no "HP counter-example".  You have misled
> yourself about what Linz, Sipser and the Wiki paragraph you quote are
> saying.
>
>> If the HP proof is refuted then when we reduce Rice and Busy Beaver
>> to the refuted HP proof they would seem to be refuted too.
>
>     It's not enough to refute an "HP proof".  Compare the 4-colour
> theorem, where all the early proofs were refuted, but the only way to
> refute the /theorem/ would have been to produce a suitable map that
> could not be 4-coloured.  Further, the other side of your coin is that
> since the BB function is manifestly uncomputable [there is an easy
> proof that has no connexion with the HP, see Wiki],

It would seem intuitively true that if BB reduces to HP and HP is
refuted that BB is thus refuted. You seem to be saying this this
intuition is wrong and that may be true.

What I have refuted is the common undecidable template as referenced by
Sipser and many others where program under test P does the opposite of
whatever the halt decider H decides.

These templates always present the decidable infinitely recursive
simulation behavior pattern to every simulating halt decider.

> the HP result is
> thereby established.  Of course, as Ben points out from time to time,
> there are several other HP proofs, inc Linz's preferred proof, given
> in the pages you used to quote.
>
>     It really would help you if you tried to understand the above
> before repeating your previous posts.
>

Until this agreed to (there has not been a sufficient honest dialogue)
so there is no sense changing the subject:

What I have refuted is the common undecidable template as referenced by
Sipser and many others where program under test P does the opposite of
whatever the halt decider H decides.

These templates always present the decidable infinitely recursive
simulation behavior pattern to every simulating halt decider.

[olcott]

Apparently every C function that is a pure function is Turing
equivalent. https://en.wikipedia.org/wiki/Pure_function

[olcott]

*The Tarski Undefinability Theorem shows this more directly*
https://liarparadox.org/Tarski_275_276.pdf

Tarski, the HP proof, the Liar Paradox, and the 1931 Incompleteness
theorem all have the same basic form (are isomorphic to each other).

[Ben Bacarisse]

Skep Dick <skepd...@gmail.com> writes:

> On Thursday, 4 August 2022 at 22:40:18 UTC+2, Ben Bacarisse wrote:
>> In a language with higher-order function you would, I think, be able to
>> say what you want to say.
>
> This is the crux of it, in this part of the woods.
>
> Turing computability only concerns itself with functions from N ->
> N. For higher order functions not all models of computations are
> Turing-equivalent - questions of representation/encoding become
> relevant. Some models of computation (programming languages) are more
> equal than others.

None of this makes sense. What is your point?

--
Ben.

[Richard Damon]

Nope, Maybe YOUR idea of Truth is broken, but not the real one.

Undecidability is REAL. it is very provable to exist.

So is Incompletness.

YOUR concept that Truth must be provable, is thus shown to be incorrect,
as it directly contradicts what can be actually shown to be true

The ACTUAL concept of Truth, that other people understands, still works
fine.

[Richard Damon]

On 8/4/22 6:25 PM, olcott wrote:
> On 8/4/2022 3:53 PM, Skep Dick wrote:
>> On Thursday, 4 August 2022 at 22:40:18 UTC+2, Ben Bacarisse wrote:
>>> In a language with higher-order function you would, I think, be able to
>>> say what you want to say.
>>
>> This is the crux of it, in this part of the woods.
>>
>> Turing computability only concerns itself with functions from N -> N.
>> For higher order functions not all models of computations are
>> Turing-equivalent - questions of representation/encoding become
>> relevant. Some models of computation (programming languages) are more
>> equal than others.
>>
>> Which is why all the software engineers on this thread are outraged.
>> They are intuitively using their favourite programming language as
>> their default model of computation. That language happens to be
>> strictly-evaluated (whereas all of Mathematics is lazy-evaluated) and
>> they can't resolve the semantic gap between the two.
>>
>
> Apparently every C function that is a pure function is Turing
> equivalent. https://en.wikipedia.org/wiki/Pure_function
>

Yes, but the Turing Machine include the algorithm for everything that
the C function calls, just like the Turing Machine equivant for P (and
thus what the representation for P needs to include) also includes
everything it calls, like H.

[Richard Damon]

No, you haven't because the pattern you use is NOT a decidably
infinitely recursiove simulation pattern when H has the ability to abort
is simulation,

This is proven by the fact that P(P) Halts when H(P,P) returns 0,
therefor a correct simulation of the input to H(P,P) can not simulate
forever if H(P,P) returns 0,

H stops its simulation, so its simulation clearly doesnt go forever.

If that same input (which included P calling THAT H) is given to a true
pure simulator, then we see that the simulaiton does reach the end, at
least as long as you keep your H to be one that returns 0 for H(P,P).

Thus, the pattern is proved to be incorrect.

Your confusion just shows you don't actually understand how
computations, computers, or simulations actually work.

[Andy Walker]

On 04/08/2022 23:09, olcott wrote:
> It would seem intuitively true that if BB reduces to HP and HP is
> refuted that BB is thus refuted. You seem to be saying this this
> intuition is wrong and that may be true.

No; it is true that HP and BB stand or fall together. It is your
"/if/ ... HP is refuted ..." [my emphasis] that is, to say the least, in
doubt. Contrariwise, since BB is very firmly established, it follows that
HP has, in fact, not been refuted [and is remarkably unlikely ever to be].

> What I have refuted is the common undecidable template as referenced
> by Sipser and many others where program under test P does the
> opposite of whatever the halt decider H decides.

Sadly, or otherwise, you have done no such thing. ...

> These templates always present the decidable infinitely recursive
> simulation behavior pattern to every simulating halt decider.

... That's because you have misunderstood the relation between "H"
and "P". If you change "H" to be a "simulating halt decider", then you
are required by the proof in Linz and elsewhere to change "P" in line with
the new "H". The old "P" is of no further interest whatsoever, and no-one
any longer cares what the original or the new "H" does about it. You have
been told this often enough, and I don't intend to repeat this point yet
again in the future.

> [...] These templates always present the decidable infinitely

> recursive simulation behavior pattern to every simulating halt
> decider.

Even if they do, so what? If your "simulating halt decider"
either gets the wrong answer or never gives an answer at all, then it
is not a halt decider, and if it gets the right answer then you have
not built "P" correctly from it by the usual construction. Either
way, you have not refuted even the one proof of the HP theorem, let
alone all the other proofs.

--
Andy Walker, Nottingham.
Andy's music pages: www.cuboid.me.uk/andy/Music

Composer of the day: www.cuboid.me.uk/andy/Music/Composers/Boccherini

[olcott]

On 8/4/2022 6:47 PM, Andy Walker wrote:
> On 04/08/2022 23:09, olcott wrote:
>> It would seem intuitively true that if BB reduces to HP and HP is
>> refuted that BB is thus refuted. You seem to be saying this this
>> intuition is wrong and that may be true.
>
>     No;  it is true that HP and BB stand or fall together.

First let me start with my appreciation for your technically competent
review.

Great! I thought that you were saying that if one of the HP proofs is
refuted that a dozen more take over in its place. If they all reduce to
one another then when one falls they all fall.

> It is your
> "/if/ ... HP is refuted ..." [my emphasis] that is, to say the least, in
> doubt.  Contrariwise, since BB is very firmly established, it follows that
> HP has, in fact, not been refuted [and is remarkably unlikely ever to be].
>
>> What I have refuted is the common undecidable template as referenced
>> by Sipser and many others where program under test P does the
>> opposite of whatever the halt decider H decides.
>
>     Sadly, or otherwise, you have done no such thing. ...
>
>> These templates always present the decidable infinitely recursive
>> simulation behavior pattern to every simulating halt decider.
>
>     ... That's because you have misunderstood the relation between "H"
> and "P".  If you change "H" to be a "simulating halt decider",

I don't have to change H to be a simulating halt decider all of the
proofs allow for any sequence of "moves" to be implemented at the Linz
wildcard ⊢* symbol:

H ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* Ĥ.qy
H ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* Ĥ.qn

> then you
> are required by the proof in Linz and elsewhere to change "P" in line with
> the new "H".  The old "P" is of no further interest whatsoever, and no-one
> any longer cares what the original or the new "H" does about it.  You have
> been told this often enough, and I don't intend to repeat this point yet
> again in the future.
>
>> [...] These templates always present the decidable infinitely
>> recursive simulation behavior pattern to every simulating halt
>> decider.
>
>     Even if they do, so what?  If your "simulating halt decider"
> either gets the wrong answer

As is required by all computable functions it must map the machine
description of its first argument to an accept or reject state based on
the actual behavior of this specified by this machine description.

Unless one rejects the notion of UTM simulation then the correct
simulation/x86 emulation of the TM description/x86 machine-code by H
provides the definitive measure of the actual behavior of its first
argument.

H, cannot, and must not map the behavior of anything besides the actual
behavior of its actual input otherwise it ceases to be a computable
function.

Everyone that has been disagreeing with this has been insisting that H
is not allowed to be a computable function, instead it must map behavior
that is not specified by its arguments.

> or never gives an answer at all, then it
> is not a halt decider, and if it gets the right answer then you have
> not built "P" correctly from it by the usual construction.  Either
> way, you have not refuted even the one proof of the HP theorem, let
> alone all the other proofs.
>



--

[Richard Damon]

Yes, A FIXED set if moves.

IF one H get stuck in an infinte recursion when given the input <P> <P>
then ALL H's will execute the EXACT SAME sequence of steps and also get
stuck in that same infinite recursion, and not answer.

If one H when given the input <P> <P> transitions to the Qn final state,
the ALL H's will do so and not get stuck in an infinite recursion.

If you want to claim differently, show the FIRST instruction that
differs between the H that answers and the H that gets stuck, and
expalin how the SAME instruction, with the SAME data can perform
differently, or how the instructions can get different data when they
started with EXACLY the same state and did exactly the same thing so far.

>
>> then you
>> are required by the proof in Linz and elsewhere to change "P" in line
>> with
>> the new "H".  The old "P" is of no further interest whatsoever, and
>> no-one
>> any longer cares what the original or the new "H" does about it.  You
>> have
>> been told this often enough, and I don't intend to repeat this point yet
>> again in the future.
>>
>>> [...] These templates always present the decidable infinitely
>>> recursive simulation behavior pattern to every simulating halt
>>> decider.
>>
>>      Even if they do, so what?  If your "simulating halt decider"
>> either gets the wrong answer
>
> As is required by all computable functions it must map the machine
> description of its first argument to an accept or reject state based on
> the actual behavior of this specified by this machine description.
>

And the actual behavior of the input to H(P,P) is P(P), or your P isn't
defined right.

> Unless one rejects the notion of UTM simulation then the correct
> simulation/x86 emulation of the TM description/x86 machine-code by H
> provides the definitive measure of the actual behavior of its first
> argument.

Nope, your H does a PARTIAL simulation of the input, and then applies an
INCORRECT Rule to conclude the input is non-halting.

>
> H, cannot, and must not map the behavior of anything besides the actual
> behavior of its actual input otherwise it ceases to be a computable
> function.

Rigbt, and the input is an EXACT representation of the Program P applied
to the input P, so the EXACT behavior of the input (if H is a Haltting
Decider) is the behavor or P(P);.

>
> Everyone that has been disagreeing with this has been insisting that H
> is not allowed to be a computable function, instead it must map behavior
> that is not specified by its arguments.

THAT is your problem. You haven't PROVEN that the mapping that H
actually IS a computable function. Until you do, you can't assume that
it is.

Since it has, in fact, to NOT be a computable function, of course you
aren't allowed to presume that it is. That would just be presenting a
FALSEHOOD.

Yes, your H will have to produce what IS a computable function, but it
won't be the HALTING function, as that has been shown to not be computable.

[Ben Bacarisse]

So your "halt decider" correctly reports halting or non-halting for all
cases except for ONE AND ONLY case -- the one in Strachey's letter?
Either "ONE AND ONLY case" means you don't care about all others (for
which suggestion you call me obtuse) or it means there is "ONE AND ONLY"
exceptional case.

No, I don't believe you. Mind you, I don't believe you have a universal
compiler either. I think you just like to say stuff.

--
Ben.

[Andy Walker]

On 05/08/2022 01:34, olcott wrote:
>>> It would seem intuitively true that if BB reduces to HP and HP is
>>> refuted that BB is thus refuted. You seem to be saying this this
>>> intuition is wrong and that may be true.
>>      No;  it is true that HP and BB stand or fall together.

> [...] I thought that you were saying that if one of the HP proofs is

> refuted that a dozen more take over in its place. If they all reduce
> to one another then when one falls they all fall.

You seem not to understand the difference between a theorem and a
proof. The /proofs/ don't all reduce to each other, and it is perfectly
possible [though very unlikely] that one or more of the standard proofs
is flawed. That doesn't affect the HP /theorem/. OTOH, if you manage to
produce an actual correct halt decider, that would demolish the theorem.
Do not hold your breath.

>>  [... Y]ou have misunderstood the relation between "H"

>> and "P".  If you change "H" to be a "simulating halt decider",
> I don't have to change H to be a simulating halt decider all of the
> proofs allow for any sequence of "moves" to be implemented at the
> Linz wildcard ⊢* symbol:

It's not "any" sequence of moves, it's the sequence of moves
specified by the program when applied to its tape. To follow the
standard proof, you are required /first/ to produce a program which
you claim is a correct halt decider [and if you can't do that, then
there is nothing to debate], /then/ to apply the hat construction,
which finds a case that your program [only /your/ program, no-one
cares what any other program does] gets wrong, and then observe the
contradiction, which demolishes your claim. If you first try with
your "H", and then try with a program that simulates "H" [or "P",
or "H" simulating "P", or ...], then the two hat constructions are
different.

> H, cannot, and must not map the behavior of anything besides the
> actual behavior of its actual input otherwise it ceases to be a
> computable function.

If we could have that in English, it might make enough sense
to be agreed or disagreed with.

> Everyone that has been disagreeing with this has been insisting that
> H is not allowed to be a computable function, instead it must map
> behavior that is not specified by its arguments.

I think you have misunderstood what at least the more sensible
"everyone"s have been saying to you. IMO, it's not helpful for some
of them to keep banging on about computable functions, esp once it
became clear [if anything is clear] that you are at cross-purposes.
OTOH, it's manifest [see my top paragraph in this article] that there
are some alarming gaps in your knowledge of what comprises theorems,
proofs and refutations, and until those gaps are plugged, further
discussion is futile. [FWIW, I acknowledge that, like Ben, I have
been banging my head against brick walls longer than makes sense,
and I should (and do) know better.]

[Ben Bacarisse]

Andy Walker <a...@cuboid.co.uk> writes:

> On 05/08/2022 01:34, olcott wrote:
> If we could have that in English, it might make enough sense
> to be agreed or disagreed with.
>
>> Everyone that has been disagreeing with this has been insisting that
>> H is not allowed to be a computable function, instead it must map
>> behavior that is not specified by its arguments.

PO uses multiple reasons to justify the wrong answer. One of them is
that it's simply "not OK" to specify what H(X,Y) must return based on
what X(Y) does because X(Y) is not the input to H. H(P,P) == false is
correct because P(P) is not the input to H.

This is why he consistently removed Linz's conditions from the lines
specifying H:

q_0 w_M w ⊦* x_1 q_y x_2 if M applied to w halts, and
q_0 w_M w ⊦* y_1 q_n y_2 if M applied to w does not halt.

M isn't an input (he would shout) so the condition is junk to start
with.

To fix this I tried to get him to specify a prime-number decider so he
could see for himself that the conditions for accepting and rejecting
are usually about what the input represents, but he bailed before we got
going. He was happy with a parity checker (though he could not write
one) because the property can be expressed as a trivial property of the
input string. Anything more abstract than that and he looses the plot.

We all know why this line of arguing is nonsense (for one thing, were it
a valid criticism, it would confirms that no halting decider is
possible!) but that is, I think what this latest mantra means.

--
Ben.

[Keith Thompson]

Andy Walker <a...@cuboid.co.uk> writes:
> On 04/08/2022 16:00, olcott wrote:
>> It is the case that every HP counter-example P [...]
>
> There is, and can be, no "HP counter-example". You have misled
> yourself about what Linz, Sipser and the Wiki paragraph you quote are
> saying.
>
>> If the HP proof is refuted then when we reduce Rice and Busy Beaver
>> to the refuted HP proof they would seem to be refuted too.
>
> It's not enough to refute an "HP proof". Compare the 4-colour
> theorem, where all the early proofs were refuted, but the only way to
> refute the /theorem/ would have been to produce a suitable map that
> could not be 4-coloured.

Or to prove that such a map exists without necessarily producing one.

[...]

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

[Keith Thompson]

olcott <No...@NoWhere.com> writes:
[...]

> Apparently every C function that is a pure function is Turing
> equivalent. https://en.wikipedia.org/wiki/Pure_function

I suggest you rephrase that. As stated, it makes no sense.

Here is a C function that is a pure function:

int answer(void) { return 42; }

That function obviously is not Turing equivalent.

[olcott]

On 8/5/2022 2:05 PM, Keith Thompson wrote:
> olcott <No...@NoWhere.com> writes:
> [...]
>> Apparently every C function that is a pure function is Turing
>> equivalent. https://en.wikipedia.org/wiki/Pure_function
>
> I suggest you rephrase that. As stated, it makes no sense.
>
> Here is a C function that is a pure function:
>
> int answer(void) { return 42; }
>
> That function obviously is not Turing equivalent.
>

It would be a TM the writes 42 to its tape on a blank tape input.

[olcott]

On 8/5/2022 12:20 PM, Andy Walker wrote:
> On 05/08/2022 01:34, olcott wrote:
>>>> It would seem intuitively true that if BB reduces to HP and HP is
>>>> refuted that BB is thus refuted. You seem to be saying this this
>>>> intuition is wrong and that may be true.
>>>      No;  it is true that HP and BB stand or fall together.
>> [...] I thought that you were saying that if one of the HP proofs is
>> refuted that a dozen more take over in its place. If they all reduce
>> to one another then when one falls they all fall.
>
>     You seem not to understand the difference between a theorem and a
> proof.  The /proofs/ don't all reduce to each other, and it is perfectly
> possible [though very unlikely] that one or more of the standard proofs
> is flawed.  That doesn't affect the HP /theorem/.  OTOH, if you manage to
> produce an actual correct halt decider, that would demolish the theorem.
> Do not hold your breath.
>

H correctly determines the halt status of the "impossible" input.

>>>  [... Y]ou have misunderstood the relation between "H"
>>> and "P".  If you change "H" to be a "simulating halt decider",
>> I don't have to change H to be a simulating halt decider all of the
>> proofs allow for any sequence of "moves" to be implemented at the
>> Linz wildcard ⊢* symbol:
>
>     It's not "any" sequence of moves, it's the sequence of moves
> specified by the program when applied to its tape.

None-the-less Linz does not say it that way. H assumes that people know
the extra details that you provided.

"The symbols ⊢* and ⊢+ have the usual meaning of an arbitrary
number of moves." (Linz:1990:237)

> To follow the
> standard proof, you are required /first/ to produce a program which
> you claim is a correct halt decider

I have a halt decider that correct determines that halt status of the
pathological input for many months now. When most people use the term:
"halt decider" they mean a "mind of God" machine that is "all knowing"
about the halt status of every possible input. I don't mean that.
H is a halt decider within its domain.

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));
}

Because it is DEAD-OBVIOUS that when H is a simulating halt decider that
correctly simulates the machine-code pointed to by its first argument
(a) Invoked H(P,P) simulates P(P) that calls a simulated H
(b) that simulates P(P) that calls a simulated H
(c) that simulates P(P) that calls a simulated H
(d) that simulates P(P) that calls a simulated H...

It is DEAD_OBVIOUS that the simulated P cannot possibly ever reach any
instruction after its call to H(P,P) thus cannot reach its "return"
instruction which is required for halting.

computation that halts … the Turing machine will halt whenever it enters
a final state. (Linz:1990:234)

> [and if you can't do that, then
> there is nothing to debate], /then/ to apply the hat construction,
> which finds a case that your program [only /your/ program, no-one
> cares what any other program does] gets wrong, and then observe the
> contradiction, which demolishes your claim.

H does correctly map its first argument: (P,P) to the halt status
specified by the actual behavior of this first argument.

Unless you reject the notion of UTM's when H performs a correct x86
emulation of the machine-code pointed to by the its first argument, then
this is the behavior that H must base its halt status decision on.

> If you first try with
> your "H", and then try with a program that simulates "H" [or "P",
> or "H" simulating "P", or ...], then the two hat constructions are
> different.
>

A halt decider must compute the mapping from its arguments to an accept
or reject state on the basis of the actual behavior that is actually
specified by the finite string machine description of its first argument.

A simulating halt decider determines the actual behavior specified by
correctly simulating the finite string machine description of its first
argument. Unless one rejects the concept of UTM's then this is already
known to be correct.

>> H, cannot, and must not map the behavior of anything besides the
>> actual behavior of its actual input otherwise it ceases to be a
>> computable function.
>
>     If we could have that in English, it might make enough sense
> to be agreed or disagreed with.
>

Everyone here (besides me) believes that H must report on the behavior
other than the behavior specified by its actual arguments as measured by
the correct simulation of these arguments performed by H.

>> Everyone that has been disagreeing with this has been insisting that
>> H is not allowed to be a computable function, instead it must map
>> behavior that is not specified by its arguments.
>
>     I think you have misunderstood what at least the more sensible
> "everyone"s have been saying to you.  IMO, it's not helpful for some
> of them to keep banging on about computable functions, esp once it
> became clear [if anything is clear] that you are at cross-purposes.
> OTOH, it's manifest [see my top paragraph in this article] that there
> are some alarming gaps in your knowledge of what comprises theorems,
> proofs and refutations, and until those gaps are plugged, further
> discussion is futile.  [FWIW, I acknowledge that, like Ben, I have
> been banging my head against brick walls longer than makes sense,
> and I should (and do) know better.]
>

None-the-less H(P,P) does correctly determine the halt status of an
input that exactly matches the HP impossible input template:

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

*My H does handle this case*

[olcott]

When the behavior of the directly executed P(P) diverges from the
behavior of the correct simulation of the first argument to H(P,P)**
then the behavior of the correct simulation must take precedence.

**computable functions must only be a function of their arguments and
nothing else.

A halt decider must compute the mapping from its arguments to an accept
or reject state on the basis of the actual behavior that is actually
specified by the finite string machine description of its first argument.

A simulating halt decider determines the actual behavior specified by

correctly simulating the finite string machine description of its first
argument.

*Unless one rejects the concept of UTM's then the*
*above sentence is already known to be correct*

[olcott]

Prior to my very extensive research into applying a simulating halt
decider to the conventional HP "impossible" inputs it seems that no one
was aware that these behaviors could possibly diverge. Because of this
they falsely assumed that the behavior of P(P) would be the correct
measure of the behavior of the first argument to H.

[Keith Thompson]

olcott <No...@NoWhere.com> writes:
> On 8/5/2022 2:05 PM, Keith Thompson wrote:
>> olcott <No...@NoWhere.com> writes:
>> [...]
>>> Apparently every C function that is a pure function is Turing
>>> equivalent. https://en.wikipedia.org/wiki/Pure_function
>> I suggest you rephrase that. As stated, it makes no sense.
>> Here is a C function that is a pure function:
>> int answer(void) { return 42; }
>> That function obviously is not Turing equivalent.
>
> It would be a TM the writes 42 to its tape on a blank tape input.

You miss my point.

A system that is Turing-equivalent is Turing-complete, meaning that
it can compute every Turing-computable function. My function above
obviously cannot do that.

https://en.wikipedia.org/wiki/Turing_completeness#Formal_definitions

I think you meant to say something about the set of all C pure
functions, or perhaps about a subset of the C language that includes
only pure functions, not about *every* (each) C pure function.

[olcott]

Furthermore I have refuted your claim that I changed H. The possible
implementations of H was always wide open and never restricted, thus a
simulating halt decider is merely one of the possible ways to implement
a halt decider that was already allowed for.

[Newberry]

You can declare C_s(unsigned int n), and let C_s() ignore the parameter.
The point is that each C_n() has memory address. URM programs do not
have any types. Function types have nothing to do with this. You are
diverting attention from the relevant to the irrelevant. The program
compiles, runs, and gives the right answer.

[olcott]

On 8/5/2022 3:32 PM, Keith Thompson wrote:
> olcott <No...@NoWhere.com> writes:
>> On 8/5/2022 2:05 PM, Keith Thompson wrote:
>>> olcott <No...@NoWhere.com> writes:
>>> [...]
>>>> Apparently every C function that is a pure function is Turing
>>>> equivalent. https://en.wikipedia.org/wiki/Pure_function
>>> I suggest you rephrase that. As stated, it makes no sense.
>>> Here is a C function that is a pure function:
>>> int answer(void) { return 42; }
>>> That function obviously is not Turing equivalent.
>>
>> It would be a TM the writes 42 to its tape on a blank tape input.
>
> You miss my point.
>
> A system that is Turing-equivalent is Turing-complete, meaning that
> it can compute every Turing-computable function. My function above
> obviously cannot do that.
>

That is why I went the other direction. Not every C function can compute
what a TM can, yet a TM can compute any computable function that a C
function can.

C can compute every computable function that a TM can as long as it has
enough memory, thus is TM equivalent for this subset.

> https://en.wikipedia.org/wiki/Turing_completeness#Formal_definitions
>
> I think you meant to say something about the set of all C pure
> functions, or perhaps about a subset of the C language that includes
> only pure functions, not about *every* (each) C pure function.
>


--

[Mr Flibble]

Nope. I have shown that a simulating halt decider needn't be recursive
in nature:

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

/Flibble

[Ben Bacarisse]

Newberry <newbe...@gmail.com> writes:

> Ben Bacarisse wrote:
>> Newberry <newbe...@gmail.com> writes:
>>
>>> C_k(unsigned int n) {
>>> A(n,n);
>>> }
>>>
>>> C_s() {
>>> C_k(s);
>>> }
>>>
>>> // If A(n,m) halts then C_n(m) does NOT halt.
>>> A(unsigned int n, unsigned int m) {
>>
>> You need to change programming language. The comment refers to C_n in
>> the context of n being an unsigned int. That is, C_n is talked about as
>> if it is a family of functions, but the two you written out are just
>> functions with an underscore in the name (and they have different types
>> so C_k and C_s can not both be the same kind of function as the C_n).
>>
>> In a language with higher-order function you would, I think, be able to
>> say what you want to say.
>
> You can declare C_s(unsigned int n), and let C_s() ignore the
> parameter.

But you didn't. And even if you did, that does not address the main
problem. But as I have said before, a discussion is only possible when
both parties want to be understood. I don't think you want to be
understood or you would not have confused part of C function name (the n
in C_n(m)) with a run-time parameter (the n in A(n,m)).

> The point is that each C_n() has memory address.

My point is that there is no "each C_n" in C. C_n is one function with
one address. Do you really not know any programming languages where you
can express the notion of a family of function? Using C (and old and
buggy C at that) means you have to fake things with globals. You may be
saying something interesting, but who's going to grub about in undefined
old-fashioned C code to find out?

> URM programs do not have any types.

Where you not writing C? It looked like C.

> Function types have nothing to do with this.

The types were a side issue, but the only issue you chose to respond to.
There's a bigger problem, but that does not seem to bother you.

> You are diverting attention from the relevant to the irrelevant. The
> program compiles, runs, and gives the right answer.

It has no main so how can it give any answer at all?

--
Ben.

[Keith Thompson]

Newberry <newbe...@gmail.com> writes:
> Ben Bacarisse wrote:
>> Newberry <newbe...@gmail.com> writes:
>>
>>> C_k(unsigned int n) {
>>> A(n,n);
>>> }
>>>
>>> C_s() {
>>> C_k(s);
>>> }
>>>
>>> // If A(n,m) halts then C_n(m) does NOT halt.
>>> A(unsigned int n, unsigned int m) {
>>
>> You need to change programming language. The comment refers to C_n in
>> the context of n being an unsigned int. That is, C_n is talked about as
>> if it is a family of functions, but the two you written out are just
>> functions with an underscore in the name (and they have different types
>> so C_k and C_s can not both be the same kind of function as the C_n).
>>
>> In a language with higher-order function you would, I think, be able to
>> say what you want to say.
>
> You can declare C_s(unsigned int n), and let C_s() ignore the
> parameter.

But you didn't do that.

> The point is that each C_n() has memory address. URM
> programs do not have any types. Function types have nothing to do with
> this. You are diverting attention from the relevant to the
> irrelevant. The program compiles, runs, and gives the right answer.

How does it run without a main() function? And why are you using
implicit int, a feature that was removed from the language in 1999.
Your functions C_k, C_s, and A should be declared to return void, and
C_s should probably be declared so it explicitly has no parameters:
"void C_s(void)".

If this is supposed to be pseudo-code that looks a lot like C, that's
fine -- but you say it "compiles, runs, and gives the right answer".
If you post something that you claim to be correct C code, expect it to
be reviewed on that basis.

[Keith Thompson]

olcott <No...@NoWhere.com> writes:
> On 8/5/2022 3:32 PM, Keith Thompson wrote:
>> olcott <No...@NoWhere.com> writes:
>>> On 8/5/2022 2:05 PM, Keith Thompson wrote:
>>>> olcott <No...@NoWhere.com> writes:
>>>> [...]
>>>>> Apparently every C function that is a pure function is Turing
>>>>> equivalent. https://en.wikipedia.org/wiki/Pure_function
>>>> I suggest you rephrase that. As stated, it makes no sense.
>>>> Here is a C function that is a pure function:
>>>> int answer(void) { return 42; }
>>>> That function obviously is not Turing equivalent.
>>>
>>> It would be a TM the writes 42 to its tape on a blank tape input.
>> You miss my point.
>> A system that is Turing-equivalent is Turing-complete, meaning that
>> it can compute every Turing-computable function. My function above
>> obviously cannot do that.
>>
>
> That is why I went the other direction. Not every C function can
> compute what a TM can, yet a TM can compute any computable function
> that a C function can.
>
> C can compute every computable function that a TM can as long as it
> has enough memory, thus is TM equivalent for this subset.

So you're saying that C is Turing equivalent, not that "every C
function" is Turing equivalent, yes? (You have to pretend that a C
program can access infinite storage for that to be true, but I think
it's common to handwave that issue.)

You have not yet acknowledged that there was anything wrong with your
original statement.

>> https://en.wikipedia.org/wiki/Turing_completeness#Formal_definitions
>> I think you meant to say something about the set of all C pure
>> functions, or perhaps about a subset of the C language that includes
>> only pure functions, not about *every* (each) C pure function.

--

[Richard Damon]

Except that is CAN'T differ and still be CORRECT.

Note, in YOUR traces, the divergence occurs at the point that H stop
simulating the input and INCORRECTLY presumes that the pattern it sees
proves the input is non-halting. Thus H is just INCORRECT about what it
thinks is the actual behavior of its input, because it decides that it
doesn't need to see the rest of the behavior because it makes a FALSE
assumption about the behavior.

>
> **computable functions must only be a function of their arguments and
> nothing else.

Right, and the INPUT to H is the exact x86 instructions that will be
executed when the input is run, and the "correct behavior" of the input
is what an x86 processor would do when executiong those instrucitons.

>
> A halt decider must compute the mapping from its arguments to an accept
> or reject state on the basis of the actual behavior that is actually
> specified by the finite string machine description of its first argument.

Right, and the "actual behavior" that is "actually specified" by a
string of x86 instructions is what would happen if that string of bytes
was actually given to an x86 processor.


One thing to note, that means this string needs to include the code of
H, as the x86 processor will need that to execute it. Your attemps to
omit it just say that the input you claim is the input isn't actually a
complete description, and thus improperly defined.

The C function P alone is NOT a computation as it doesn't actaully
specify the full algorithm to be used, but only becomes one when all the
code that it calls is included, like H.

>
> A simulating halt decider determines the actual behavior specified by
> correctly simulating the finite string machine description of its first
> argument.
>
> *Unless one rejects the concept of UTM's then the*
> *above sentence is already known to be correct*
>
>
>

Yes, a CORRECT simulating Halt Decider will CORRECTLY determine the
ACTUAL behavior specified by the input, which IS the behavior that this
input would do when run by the x86 processor.

P(P) Halts when run if H(P,P) returns 0.

Thus, H determining that the input to H(P,P) is non-halting and thus
returning 0 means H was just WRONG.

Talking about an H that didn't abort is just a Strawman, and a dishonest
dodge, as that isn't the H that the input specifies, so doesn't apply to
determining the behavior of the input.

Remember, P calls a PARTICULAR definion of H, not some abstract model.
Since the H you claim is correct does return 0 for the call to H(P,P),
then, to b correct, the P that it is looking at is also calling an H
that returns 0 for a call to H(P,P), and thus is NOT stuck in some
infinite recursion of simulation, because that H DOES have code to abort
that loop.


You are just showing that you don't understand these basic facts. The
x86 code given to H IS the program P, and the input specified was P, so
the computation H needs to decide on is P(P), with that P calling an H
that acts EXACTLY like the decider deciding on it.

Since that decider returns 0 for H(P,P), we can see that P(P) will Halt,
and thus the answer that H gave is WRONG.

Your claim that the input means something else means you are just lying
somewhere about what everything means, and this is painfully obviousl to
most of us, even if you are just to stupid to see it.

[Richard Damon]

And they CAN'T

You "proof" that they do is INVALID and UNSOUND as it presumes
statements that are just not true.

Your "Correct Simulation" differs from reality when H fails to actually
simulate the H that P calls, but replaces it with behavior fhat doesn't
match the actual behavor of H. Thus H is doing an INCORRECT simulation
and/or UNSOUND LOGIC depending on exactly how you want to define your terms.

Either way, you claim is just WRONG, and you have wasted you life
pursuing a false god.

[Richard Damon]

On 8/5/22 3:56 PM, olcott wrote:
> On 8/5/2022 12:20 PM, Andy Walker wrote:
>> On 05/08/2022 01:34, olcott wrote:
>>>>> It would seem intuitively true that if BB reduces to HP and HP is
>>>>> refuted that BB is thus refuted. You seem to be saying this this
>>>>> intuition is wrong and that may be true.
>>>>      No;  it is true that HP and BB stand or fall together.
>>> [...] I thought that you were saying that if one of the HP proofs is
>>> refuted that a dozen more take over in its place. If they all reduce
>>> to one another then when one falls they all fall.
>>
>>      You seem not to understand the difference between a theorem and a
>> proof.  The /proofs/ don't all reduce to each other, and it is perfectly
>> possible [though very unlikely] that one or more of the standard proofs
>> is flawed.  That doesn't affect the HP /theorem/.  OTOH, if you manage to
>> produce an actual correct halt decider, that would demolish the theorem.
>> Do not hold your breath.
>>
>
> H correctly determines the halt status of the "impossible" input.

No;pe, P(P) Halts when H(P,P) returns 0;

H(P,P) MUST refer to P(P) or you claim that P was defined right is just
a lie.

PERIOD.

>
>>>>  [... Y]ou have misunderstood the relation between "H"
>>>> and "P".  If you change "H" to be a "simulating halt decider",
>>> I don't have to change H to be a simulating halt decider all of the
>>> proofs allow for any sequence of "moves" to be implemented at the
>>> Linz wildcard ⊢* symbol:
>>
>>      It's not "any" sequence of moves, it's the sequence of moves
>> specified by the program when applied to its tape.
>
> None-the-less Linz does not say it that way. H assumes that people know
> the extra details that you provided.
>
>    "The symbols ⊢* and  ⊢+ have the usual meaning of an arbitrary
>     number of moves." (Linz:1990:237)

Just shows that you don't understand what he is saying.

Yes, they can be any arbirtary number of moves, but a SPECIFIED
arbitrary number of moves.

>
>> To follow the
>> standard proof, you are required /first/ to produce a program which
>> you claim is a correct halt decider
>
> I have a halt decider that correct determines that halt status of the
> pathological input for many months now. When most people use the term:
> "halt decider" they mean a "mind of God" machine that is "all knowing"
> about the halt status of every possible input. I don't mean that.
> H is a halt decider within its domain.

Nope: Halt Decider, a machine the fits the following requirement

H(M,x) accepts if M(x) Halts in finite time
H(M,x) reject if M(x) will Never Halt after an unbounded number of steps.

H is a decider, so ALWAYS accepts or rejects ANY input in a finite
amount of time.

>
> 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));
> }
>
> Because it is DEAD-OBVIOUS that when H is a simulating halt decider that
> correctly simulates the machine-code pointed to by its first argument
> (a) Invoked H(P,P) simulates P(P) that calls a simulated H
> (b) that simulates P(P) that calls a simulated H
> (c) that simulates P(P) that calls a simulated H
> (d) that simulates P(P) that calls a simulated H...
>

Which only happens if H never aborts its simulation.

The Correct and complete simulation of the input to H, if the simulated
H ever aborts its simulation and returns 0, shows that the simulation
will reach a final state.

Note, since the simulating Halt Decider aborts its simulation, IT
doesn't get there, but that doesn't matter, the Correct and Complete
simulation of the input halts, as does the direct execution of that input.

> It is DEAD_OBVIOUS that the simulated P cannot possibly ever reach any
> instruction after its call to H(P,P) thus cannot reach its "return"
> instruction which is required for halting.

H can't see P getting there, but the correct and complete simulation of
the input to H can (if H aborts and returns 0) as does the actual
execution of the input.

>
> computation that halts … the Turing machine will halt whenever it enters
> a final state. (Linz:1990:234)

Right, THE TURING MACHINE, that is P(P)

P(P) WILL HALT with your H, since your H does return 0 for H(P,P).

>
>> [and if you can't do that, then
>> there is nothing to debate], /then/ to apply the hat construction,
>> which finds a case that your program [only /your/ program, no-one
>> cares what any other program does] gets wrong, and then observe the
>> contradiction, which demolishes your claim.
>
> H does correctly map its first argument: (P,P) to the halt status
> specified by the actual behavior of this first argument.

Nope, P(P) Halts since you H returns 0 for H(P,P)
Thus the CORRECT mapping of the input (P,P) is Halting, since that IS
the actual behavior of this first argument when given the second
arguement either via direct execution of complete and correct simulaiton.

>
> Unless you reject the notion of UTM's when H performs a correct x86
> emulation of the machine-code pointed to by the its first argument, then
> this is the behavior that H must base its halt status decision on.

No problems with UTMs. Just remember, to be a UTM, U(M,x) must behave
exactly like M(x).

SInce that is NOT true of H(P,P), H isn't a UTM, nor is it using an
actual UTM.

>
>> If you first try with
>> your "H", and then try with a program that simulates "H" [or "P",
>> or "H" simulating "P", or ...], then the two hat constructions are
>> different.
>>
>
> A halt decider must compute the mapping from its arguments to an accept
> or reject state on the basis of the actual behavior that is actually
> specified by the finite string machine description of its first argument.

And the actual behavior of the input to H(P,P) is the behavior of P(P)
or you have lied about P being defined by the specifiecation.

>
> A simulating halt decider determines the actual behavior specified by
> correctly simulating the finite string machine description of its first
> argument. Unless one rejects the concept of UTM's then this is already
> known to be correct.

But if it stops before reaching the final state, then the correect
answer is STILL determined by the behavior of the direct exectution of
that input, or the UTM simulation of the input to the decider.

Since UTM(P,P) will Halt since H(P,P) returns 0, H is incorrect.

If you want to change to a different H that doesn't make the mistake and
doesn't abort until it can actually PROVE the input is non-halting, then
it has been shown that your H will simulate FOREVER and fail to answer.

>
>>> H, cannot, and must not map the behavior of anything besides the
>>> actual behavior of its actual input otherwise it ceases to be a
>>> computable function.
>>
>>      If we could have that in English, it might make enough sense
>> to be agreed or disagreed with.
>>
>
> Everyone here (besides me) believes that H must report on the behavior
> other than the behavior specified by its actual arguments as measured by
> the correct simulation of these arguments performed by H.

No, everyone KNOWS that the behavior that H must report is that which
the input actually does specify, that of P(P).

Only YOU ERRONEOUSLY think that this isn't the meaning of the input,
even though you yourself assert that it is by your design of P.

You somehow think that a Halting Input can be non-halting because it is
impossible for H to get the correct answer.

>
>>> Everyone that has been disagreeing with this has been insisting that
>>> H is not allowed to be a computable function, instead it must map
>>> behavior that is not specified by its arguments.
>>
>>      I think you have misunderstood what at least the more sensible
>> "everyone"s have been saying to you.  IMO, it's not helpful for some
>> of them to keep banging on about computable functions, esp once it
>> became clear [if anything is clear] that you are at cross-purposes.
>> OTOH, it's manifest [see my top paragraph in this article] that there
>> are some alarming gaps in your knowledge of what comprises theorems,
>> proofs and refutations, and until those gaps are plugged, further
>> discussion is futile.  [FWIW, I acknowledge that, like Ben, I have
>> been banging my head against brick walls longer than makes sense,
>> and I should (and do) know better.]
>>
>
> None-the-less H(P,P) does correctly determine the halt status of an
> input that exactly matches the HP impossible input template:
>
>    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
>
> *My H does handle this case*
>

Nope.

The input represents P(P), this is PROVED by the design of P, for it to
be the template required by the ACTUAL proof.

P(P) Halts

H(P,P) says its input is non-halting.



Note, your quote isn't the actual proof you claim to be solving, and you
aren't even meeting THAT requrement, as the version you are quoting says
to give H the SOURCE CODE. In you case, that would be the C code of P,
H, and everything that H calls.

[Richard Damon]

On 8/5/22 4:32 PM, olcott wrote:
> On 8/5/2022 2:56 PM, olcott wrote:

>> None-the-less Linz does not say it that way. H assumes that people
>> know the extra details that you provided.
>>
>>     "The symbols ⊢* and  ⊢+ have the usual meaning of an arbitrary
>>      number of moves." (Linz:1990:237)
>>
>
> Furthermore I have refuted your claim that I changed H. The possible
> implementations of H was always wide open and never restricted, thus a
> simulating halt decider is merely one of the possible ways to implement
> a halt decider that was already allowed for.

But it must be *A* implementation of your decider, which means that ALL
calls to H(P,P) behave the same.

Since when main calls H(P,P) it returns 0, then ALL calls to H(P,P) need
to return 0, even when P calls it.

Thus a CORRECT simulation of a call to H(P,P) by P must similarly show
that H will return 0.

The fact that YOUR trace shows H determining that it will never return
says either H is doing an incorrect simulation of what that function is
doing or is just using bad logic to derive that answer.

Either way, it is wrong.

[Richard Damon]

He means that every pure function that can be written in C has an
equivalent Turing Machine that does the same computation.

That is the "Turing Equivalent" for a Computation.

There is also a "System" definition of Turing Equivalence that means
that the system can compute anything that a Turing Machine can, which in
this case means that you can take any Turing Machine and write a C
function that computes the same mapping as it.

Since we haven't found anything more powerful than a Turing Machine,
that also means that any PURE C PROGRAM (or pure function) can also has
an equivalent Turing Machine that computes the same mapping as it does.

Of course, he doesn't understand the technical details of the words so
slightly misuses them. (In other cases he can grossly misuse terms)

[olcott]

On 8/5/2022 4:27 PM, Keith Thompson wrote:
> olcott <No...@NoWhere.com> writes:
>> On 8/5/2022 3:32 PM, Keith Thompson wrote:
>>> olcott <No...@NoWhere.com> writes:
>>>> On 8/5/2022 2:05 PM, Keith Thompson wrote:
>>>>> olcott <No...@NoWhere.com> writes:
>>>>> [...]
>>>>>> Apparently every C function that is a pure function is Turing
>>>>>> equivalent. https://en.wikipedia.org/wiki/Pure_function
>>>>> I suggest you rephrase that. As stated, it makes no sense.
>>>>> Here is a C function that is a pure function:
>>>>> int answer(void) { return 42; }
>>>>> That function obviously is not Turing equivalent.
>>>>
>>>> It would be a TM the writes 42 to its tape on a blank tape input.
>>> You miss my point.
>>> A system that is Turing-equivalent is Turing-complete, meaning that
>>> it can compute every Turing-computable function. My function above
>>> obviously cannot do that.
>>>
>>
>> That is why I went the other direction. Not every C function can
>> compute what a TM can, yet a TM can compute any computable function
>> that a C function can.
>>
>> C can compute every computable function that a TM can as long as it
>> has enough memory, thus is TM equivalent for this subset.
>
> So you're saying that C is Turing equivalent,

In the direction from C to TM, Pure C functions are Turing Equivalent.

In the direction from TM to C, Pure C functions that have enough memory
to compete the computation are Turing Equivalent.

> not that "every C
> function" is Turing equivalent, yes? (You have to pretend that a C
> program can access infinite storage for that to be true, but I think
> it's common to handwave that issue.)
>
> You have not yet acknowledged that there was anything wrong with your
> original statement.
>

My original statement referred to:
In the direction from C to TM, Pure C functions are Turing Equivalent.
Thus my original statement is correct.

>>> https://en.wikipedia.org/wiki/Turing_completeness#Formal_definitions
>>> I think you meant to say something about the set of all C pure
>>> functions, or perhaps about

> a subset of the C language that includes
>>> only pure functions, not about *every* (each) C pure function.

Yes

My original statement:

>>>>>> Apparently every C function that is a pure function is Turing
>>>>>> equivalent. https://en.wikipedia.org/wiki/Pure_function

[olcott]

Finally you got something correctly.

[olcott]

On 8/5/2022 5:02 PM, Richard Damon wrote:
> On 8/5/22 4:32 PM, olcott wrote:
>> On 8/5/2022 2:56 PM, olcott wrote:
>
>>> None-the-less Linz does not say it that way. H assumes that people
>>> know the extra details that you provided.
>>>
>>>     "The symbols ⊢* and  ⊢+ have the usual meaning of an arbitrary
>>>      number of moves." (Linz:1990:237)
>>>
>>
>> Furthermore I have refuted your claim that I changed H. The possible
>> implementations of H was always wide open and never restricted, thus a
>> simulating halt decider is merely one of the possible ways to
>> implement a halt decider that was already allowed for.
>
> But it must be *A* implementation of your decider, which means that ALL
> calls to H(P,P) behave the same.

All invocations of H(P,P) behave the same way.

[André G. Isaak]

Except that's not what 'Turing Equivalent' means. You have this nasty
habit of inventing your own definitions for terms and assuming that
those definitions are correct when they usually are not. And then you
wonder why you aren't understood.

A computational model is Turing Equivalent if it can compute the exact
same set of functions that Turing Machines are capable of computing. It
makes no sense to refer to some specific function ('pure' or otherwise)
as 'Turing Equivalent'.

What you are *trying* to say, as far as I am able to discern, is that a
given C functions could also be implemented by Turing Machines. That may
be true, but that doesn't make the function 'Turing Equivalent'. That
isn't what the term 'Turing Equivalent' actually means.

André


--
To email remove 'invalid' & replace 'gm' with well known Google mail
service.

[Richard Damon]

On 8/5/22 6:16 PM, olcott wrote:
> On 8/5/2022 5:02 PM, Richard Damon wrote:
>> On 8/5/22 4:32 PM, olcott wrote:
>>> On 8/5/2022 2:56 PM, olcott wrote:
>>
>>>> None-the-less Linz does not say it that way. H assumes that people
>>>> know the extra details that you provided.
>>>>
>>>>     "The symbols ⊢* and  ⊢+ have the usual meaning of an arbitrary
>>>>      number of moves." (Linz:1990:237)
>>>>
>>>
>>> Furthermore I have refuted your claim that I changed H. The possible
>>> implementations of H was always wide open and never restricted, thus
>>> a simulating halt decider is merely one of the possible ways to
>>> implement a halt decider that was already allowed for.
>>
>> But it must be *A* implementation of your decider, which means that
>> ALL calls to H(P,P) behave the same.
>
> All invocations of H(P,P) behave the same way.
>
>

But not all interpretations of simulation of H(P,P) by H, thus H is
WRONG about what H(P,P) does.

H(P,P) will return 0, but H INCORRECT presumes that the call to H(P,P)
in P will never return.

That is a WRONG assumption, thus H gets the wrong answer for the
behavior of P(P).

Remember, the DEFINITION of a correct simulation is it FULLY agrees with
the behavior of the thing it is simulating.

Thus for H to assume (incorrectly) that the call to H(P,P) by P does not
return is just INCORRECT and thus an indication of incorrect simulation.

[Richard Damon]

Yes, it is a somewhat misuse of the term, but the Turing Machine IS the
"Equivalent" of the C function. (They perform the equivalent computation).

[olcott]

Welcome back it is a pleasure to speak with techically competent
reviewers such as yourself.

I am doing Turing equivalence in the other direction.
What set of C functions are Turing computable?

I was told that many ways that I could implement H would not be Turing
computable, oniy the subset of pure C functions would be Turing computable.

> It
> makes no sense to refer to some specific function ('pure' or otherwise)
> as 'Turing Equivalent'.
>
> What you are *trying* to say, as far as I am able to discern, is that a
> given C functions could also be implemented by Turing Machines. That may
> be true, but that doesn't make the function 'Turing Equivalent'.

The set of functions that both TM's and C functions compute are
computationally equivalent.

> That
> isn't what the term 'Turing Equivalent' actually means.
>

I had to derive some name for the above set.
{Turing equivalent subset of functions} is what I chose.

It is logically incorrect to be boxed in by the limitations of language:
linguistic determinism, says that language determines thought and that
linguistic categories limit and determine cognitive categories.
https://en.wikipedia.org/wiki/Linguistic_relativity


> André

[olcott]

On 8/5/2022 5:57 PM, Richard Damon wrote:
> On 8/5/22 6:16 PM, olcott wrote:
>> On 8/5/2022 5:02 PM, Richard Damon wrote:
>>> On 8/5/22 4:32 PM, olcott wrote:
>>>> On 8/5/2022 2:56 PM, olcott wrote:
>>>
>>>>> None-the-less Linz does not say it that way. H assumes that people
>>>>> know the extra details that you provided.
>>>>>
>>>>>     "The symbols ⊢* and  ⊢+ have the usual meaning of an arbitrary
>>>>>      number of moves." (Linz:1990:237)
>>>>>
>>>>
>>>> Furthermore I have refuted your claim that I changed H. The possible
>>>> implementations of H was always wide open and never restricted, thus
>>>> a simulating halt decider is merely one of the possible ways to
>>>> implement a halt decider that was already allowed for.
>>>
>>> But it must be *A* implementation of your decider, which means that
>>> ALL calls to H(P,P) behave the same.
>>
>> All invocations of H(P,P) behave the same way.
>>
>>
>
> But not all interpretations of simulation of H(P,P) by H, thus H is
> WRONG about what H(P,P) does.
>
>> All invocations of H(P,P) behave the same way.

In my current version of H, the simulated calls are never invoked.

[André G. Isaak]

Then he could say that for a given C function, there was a corresponding
TM which computed the same function. No need to abuse terms by calling
the C function 'Turing Equivalent'.

[André G. Isaak]

No. What you were told was that many of the C functions you referred to
were not complete computations on their own and could not be treated as
such. Arbitrary blocks of C code don't always correspond to
computations, though a complete C program which compiles and runs will.
Also, the formal parameters of a C function do not always directly
correspond to the input of a computation. These are two reasons (among
many others) why C is not a good choice for discussing issues having to
do with computational theory.

>> It makes no sense to refer to some specific function ('pure' or
>> otherwise) as 'Turing Equivalent'.
>>
>> What you are *trying* to say, as far as I am able to discern, is that
>> a given C functions could also be implemented by Turing Machines. That
>> may be true, but that doesn't make the function 'Turing Equivalent'.
>
> The set of functions that both TM's and C functions compute are
> computationally equivalent.
>
>>  That isn't what the term 'Turing Equivalent' actually means.
>>
>
> I had to derive some name for the above set.
> {Turing equivalent subset of functions} is what I chose.
>
> It is logically incorrect to be boxed in by the limitations of language:

Nobody's asking you to be 'boxed in'. If there is some concept you want
to refer to which existing terms don't cover, you are always free to
define a new term. What you *don't* want to do if you actually want to
be understood is to misuse or redefine terms which already have well
established meanings.

And you don't do this with merely the one term I mention above. You do
this with virtually *every* term you use. This makes communication
virtually impossible.

André

> linguistic determinism, says that language determines thought and that
> linguistic categories limit and determine cognitive categories.
> https://en.wikipedia.org/wiki/Linguistic_relativity

[Richard Damon]

C functions that can return different values for the same input, based
on state information from sources other than their defined input, can
not be converted to a Turing Machine, because they do not compute a
Computation Theory "function" since Functions in compuation theory are
deterministic mappings of the input to the output.

Depending on exactly what definition of "Pure Function" you use, some
"non-pure functions" might still always compute the same mapping for a
given input, does have some other side effect that doesn't affect their
being a "Computaton Theory Function".

>
>> It makes no sense to refer to some specific function ('pure' or
>> otherwise) as 'Turing Equivalent'.
>>
>> What you are *trying* to say, as far as I am able to discern, is that
>> a given C functions could also be implemented by Turing Machines. That
>> may be true, but that doesn't make the function 'Turing Equivalent'.
>
> The set of functions that both TM's and C functions compute are
> computationally equivalent.

The point that he is making is that is a misuse of the term.

Computaiton Equivalence, is a term to define two SYSTEMS of computation
to say that anything that can be computed in one system can be computed
in the other, and vis-versa.

The more accurate term for you to use is that the C function and the
Turing Machine are Equivalent Computations (They compute the same mapping).

>
>>  That isn't what the term 'Turing Equivalent' actually means.
>>
>
> I had to derive some name for the above set.
> {Turing equivalent subset of functions} is what I chose.
>
> It is logically incorrect to be boxed in by the limitations of language:
> linguistic determinism, says that language determines thought and that
> linguistic categories limit and determine cognitive categories.
> https://en.wikipedia.org/wiki/Linguistic_relativity

I thought you said that language was what DEFINED what things are, thus
language needs to be a slave to reality.

Maybe your problem is that bad linguistic has given you bad thought
processes that cause you to perform illigical thinking.

After all, if your thought processes don't match the reality of the
system, then your reasoning becomes incorrect.

This is what we have been telling you for many years, that you are using
incorrect reasoning. The source of that might be that you have adopted
an incorrect linguistic, that doesn't actually match that of reality.

Unless you are of the thoght that we totally create our own reality, and
thus reality doesn't actually exist as a shared concept.

>
>
>> André
>>
>>
>
>

[Richard Damon]

On 8/5/22 7:10 PM, olcott wrote:
> On 8/5/2022 5:57 PM, Richard Damon wrote:
>> On 8/5/22 6:16 PM, olcott wrote:
>>> On 8/5/2022 5:02 PM, Richard Damon wrote:
>>>> On 8/5/22 4:32 PM, olcott wrote:
>>>>> On 8/5/2022 2:56 PM, olcott wrote:
>>>>
>>>>>> None-the-less Linz does not say it that way. H assumes that people
>>>>>> know the extra details that you provided.
>>>>>>
>>>>>>     "The symbols ⊢* and  ⊢+ have the usual meaning of an arbitrary
>>>>>>      number of moves." (Linz:1990:237)
>>>>>>
>>>>>
>>>>> Furthermore I have refuted your claim that I changed H. The
>>>>> possible implementations of H was always wide open and never
>>>>> restricted, thus a simulating halt decider is merely one of the
>>>>> possible ways to implement a halt decider that was already allowed
>>>>> for.
>>>>
>>>> But it must be *A* implementation of your decider, which means that
>>>> ALL calls to H(P,P) behave the same.
>>>
>>> All invocations of H(P,P) behave the same way.
>>>
>>>
>>
>> But not all interpretations of simulation of H(P,P) by H, thus H is
>> WRONG about what H(P,P) does.
>>
> >> All invocations of H(P,P) behave the same way.
> In my current version of H, the simulated calls are never invoked.
>

No, but the results of the call to H(P,P) are assumed, and that
assumption is incorrect.

Correct but incomplete simulations do not by themselves prove
non-halting, you need to use SOUND and VALID logic to prove this from
the results of your simulation.

Note, you do this because you have introduced a FALSE premise into your
logic system, making it UNSOUND, and thus liable to give wrong answers.

If you want to try to actually PROVE your claimed rule is correct, or
site a source of someone else that also says it IN THAT FORM, go ahead
and show me wrong in the claim that it is incorrect.

You refuse to acknoledge this, which means that you just keep spouting
off LIES and UNTRUTHS because you have refused to accept what it true.

Note, incorrect rules can in some cases give the right answer, that is
why "Proof By Example" is a Fallacy.

Your Rule (3) doesn't work if there is a conditional in H, or if H is a
simulator that can at some point decide to stop simulating. THis is true
for the call to H(P,P) by P, so the rule isn't correct.

Your "Proof By Examples", of course, look at cases where that problem
doesn't show up, so the rule does work for them.

[olcott]

Pure functions do.

> though a complete C program which compiles and runs will.
> Also, the formal parameters of a C function do not always directly
> correspond to the input of a computation.

Pure functions always do.

> These are two reasons (among
> many others) why C is not a good choice for discussing issues having to
> do with computational theory.
>

*C is a good choice for two reasons*:

(a) It abstracts away such an enormous amount of purely extraneous
complexity such that the underlying algorithm that it is implements can
actually be seen and understood. In a machine that doesn't even have
direct memory addressing the associated TM description would be utterly
incomprehensible.

(b) Because of the above (and most importantly) only with a C
implementation can every single detail be fully examined instead of all
of the other proofs that the leave these details utterly unspecified as
with the Linz ⊢* (wildcard) arbitrary number of moves:

H ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* Ĥ.qy
H ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* Ĥ.qn

Only when 100% of all of the details can be specified can previously
undiscovered gaps in reasoning be uncovered.

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));
}

It is a DEAD_OBVIOUS VERIFIED FACT that the correct x86 emulation by
H(P,P) of its arguments would never stop running unless its simulation
was aborted. (ignoring stack overflow).

That no one has ever agreed to this DEAD_OBVIOUS VERIFIED FACT leads me
to believe that an honest dialogue has never been the goal of most of my
reviewers.

>>> It makes no sense to refer to some specific function ('pure' or
>>> otherwise) as 'Turing Equivalent'.
>>>
>>> What you are *trying* to say, as far as I am able to discern, is that
>>> a given C functions could also be implemented by Turing Machines.
>>> That may be true, but that doesn't make the function 'Turing
>>> Equivalent'.
>>
>> The set of functions that both TM's and C functions compute are
>> computationally equivalent.
>>
>>>  That isn't what the term 'Turing Equivalent' actually means.
>>>
>>
>> I had to derive some name for the above set.
>> {Turing equivalent subset of functions} is what I chose.
>>
>> It is logically incorrect to be boxed in by the limitations of language:
>
> Nobody's asking you to be 'boxed in'. If there is some concept you want
> to refer to which existing terms don't cover, you are always free to
> define a new term.

That is what I did.

> What you *don't* want to do if you actually want to
> be understood is to misuse or redefine terms which already have well
> established meanings.
>

The set of computationally equivalent functions bijection between TM's
and pure functions in C.

> And you don't do this with merely the one term I mention above. You do
> this with virtually *every* term you use. This makes communication
> virtually impossible.
>

I have to do it with a few terms because there are no preexisting terms
that fully capture all of the nuances of meaning that I must to express.

> André
>
>> linguistic determinism, says that language determines thought and that
>> linguistic categories limit and determine cognitive categories.
>> https://en.wikipedia.org/wiki/Linguistic_relativity
>
>


--

[olcott]

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));
}

It is a DEAD_OBVIOUS VERIFIED FACT that the correct x86 emulation by
H(P,P) of its arguments would never stop running unless its simulation
was aborted. (ignoring stack overflow).

That no one has ever agreed to this DEAD_OBVIOUS VERIFIED FACT leads me
to believe that an honest dialogue has never been the goal of most of my
reviewers.

[Richard Damon]

Nope, It is DEAD_OBVIOUS and VERIFIED by the fact that H(P,P) returns 0
to main that the correct x86 emulation of the input to H(P,P) by a
CORRCT and COMPLETE emulator will see the call to H(P,P) by P(P)
eventually do the same thing and return 0 to P and P then return showing
it reached its final state.

It is also clear that H gave up on its simulation too soon and thus
doesn't see that result. The fact that H DID abort its simulation means
NOTHING (there is no 'unless', since by the algorithm of your defined H,
it WILL abort its simulation at the exact point it did).

It is also dead obvious and verified that you just don't understand that
the simulation by H means NOTHING for determining the behavior of its
input, but only the behavior by the DEFINITION that it is x86 machine
code that is to be run.

Halting is based on the behavior of the Turing Machine, that is the
DIRECT EXECUTION, or the simulation by an ACTUAL UTM (which will be
identical to the direct execution by definition).

If you want to use H's simulation, either you need to show that it
actually matches this (which it doesn't) or admit that you aren't
working on the Halting Problem.

This is the clear meaning of the words you use.

It is clear you just are ignorant of the topic, and are talking out of
your Hat (or something lower).

[Keith Thompson]

Yes, it's a misuse of the term.

Now how would you rephrase your original statement so that it either (a)
uses the term "Turing equivalent" correctly or (b) doesn't use the term
"Turing equivalent" at all? (I'm assuming you're interested in
communicating clearly.)

[Richard Damon]

Nope, it is dead obvious and a verified fact that you are incorrect
here. as explained in the other post.

Since H(P,P) returns 0 to Main, it will ALWAYS return 0 for ANY and ALL
calls to H(P,P), and thus any logic that says otherwise is just incorrect.

Thus YOU are incorrect, and dead obvious that you are ignorant of the
fields you pontificat about.

>
>>>> It makes no sense to refer to some specific function ('pure' or
>>>> otherwise) as 'Turing Equivalent'.
>>>>
>>>> What you are *trying* to say, as far as I am able to discern, is
>>>> that a given C functions could also be implemented by Turing
>>>> Machines. That may be true, but that doesn't make the function
>>>> 'Turing Equivalent'.
>>>
>>> The set of functions that both TM's and C functions compute are
>>> computationally equivalent.
>>>
>>>>  That isn't what the term 'Turing Equivalent' actually means.
>>>>
>>>
>>> I had to derive some name for the above set.
>>> {Turing equivalent subset of functions} is what I chose.
>>>
>>> It is logically incorrect to be boxed in by the limitations of language:
>>
>> Nobody's asking you to be 'boxed in'. If there is some concept you
>> want to refer to which existing terms don't cover, you are always free
>> to define a new term.
>
> That is what I did.

Nope, "Turing Equivalence" is an existing term.

[olcott]

The #1 deception is changing the subject.
The #1 deception is changing the subject.
The #1 deception is changing the subject.
The #1 deception is changing the subject.
The #1 deception is changing the subject.

So you are saying that the simulation would stop running on its own
without the need for H to abort it?

[olcott]

It is crucially important that it be understood that the results of
H(P,P) apply equally to all of the conventional HP proofs and are not
baselessly dismissed out-of-hand.