#include <stdint.h>
#include <stdio.h>
typedef int (*ptr)();

int H(ptr x, ptr y)
{ x(y); // direct execution of P(P)
return 1;
}

// Minimal essence of Linz(1990) Ĥ
// and Strachey(1965) P
int P(ptr x)
{ H(x, x);
return 1; // Give P a last instruction at the "c" level
}

int main(void)
{ H(P, P);
}

PSR set: It is self evident that when 0 to ∞ steps of the input to
H(P,P) are directly executed or correctly simulated that the input to
H(P,P) never reaches its final instruction.

We can think of the combinations of (H,P) as an enumerated sequence of
finite strings of C source-code. The above source code specifies the
H0(P0,P0) first element of this sequence.

Computation that halts
a computation is said to halt whenever it enters a final state.
(Linz:1990:234)

PSR subset A: When Hn(Pn, Pn) executes or simulates a fixed number of N
steps of its input this input still never reaches its last instruction
and Hn(Pn, Pn) halts.

PSR subset B: When Hn(Pn, Pn) executes or simulates a fixed number of N
steps of its input this input still never reaches its last instruction
and Hn(Pn, Pn) halts and Pn(Pn) called from main() halts.

PSR subset C: For the subset of PSR subset A where Hn(Pn, Pn) returns 0
the returned halt status corresponds to the actual behavior of the input
to Hn(Pn, Pn).

PSR subset D: For the subset of PSR subset C where Hn(Pn, Pn) returns 0
on the basis that this input matches the infinite recursion behavior
pattern. Hn(Pn, Pn) detects that its input is calling H again with the
same input that it was called with. This makes Hn a correct halt decider
of this input.

H is a computable function that accepts or rejects inputs in its domain
on the basis that these inputs specify a sequence of configurations that
reach their final state.

--
Copyright 2021 Pete Olcott

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

Same Problem as before.

Definition of Non-Halting is that is will not reach a halting state
after an UNBOUNDED (not some finite) number of steps.

Thus, your H is NOT a Halt Decider, because it doesn't even claim to
follow the real definition of Halting.

PERIOD.

You just LIE claiming it is.

We KNOW that if Hn(Pn,Pn) returns 0 then the direct execution of Pn(Pn)
will Halt. You even have aggreed to it.

In fact, woth your current definition that each Hn has some number N for
the number of steps it will simulate before aborting its simulaton,
there is a small number k, such that we know that Pn(Pn) will halt in
N+k steps.

The fact that N < N+k just shows that Hn was just a bit to impatient,
and incorrect as a Halt Decider.

FAIL.

On 11/24/21 12:49 PM, olcott wrote:
> #include <stdint.h>
> #include <stdio.h>
> typedef int (*ptr)();
>
> int H(ptr x, ptr y)
> {
>   x(y); // direct execution of P(P)
>   return 1;
> }
>
> // Minimal essence of Linz(1990) Ĥ
> // and Strachey(1965) P
> int P(ptr x)
> {
>   H(x, x);
>   return 1; // Give P a last instruction at the "c" level
> }
>
> int main(void)
> {
>   H(P, P);
> }
>
> PSR set: It is self evident that when 0 to ∞ steps of the input to
> H(P,P) are directly executed or correctly simulated that the input to
> H(P,P) never reaches its final instruction.
>
> We can think of the combinations of (H,P) as an enumerated sequence of
> finite strings of C source-code. The above source code specifies the
> H0(P0,P0) first element of this sequence.
>
> Computation that halts
> a computation is said to halt whenever it enters a final state.
> (Linz:1990:234)
>
> PSR subset A: When Hn(Pn, Pn) executes or simulates a fixed number of N
> steps of its input this input still never reaches its last instruction
> and Hn(Pn, Pn) halts.
>
> PSR subset B: When Hn(Pn, Pn) executes or simulates a fixed number of N
> steps of its input this input still never reaches its last instruction
> and Hn(Pn, Pn) halts and Pn(Pn) called from main() halts.
>
> PSR subset C: For the subset of PSR subset A where Hn(Pn, Pn) returns 0
> the returned halt status corresponds to the actual behavior of the input
> to Hn(Pn, Pn).
>
> PSR subset D: For the subset of PSR subset C where Hn(Pn, Pn) returns 0
> on the basis that this input matches the infinite recursion behavior
> pattern. Hn(Pn, Pn) detects that its input is calling H again with the
> same input that it was called with. This makes Hn a correct halt decider
> of this input.
>
> H is a computable function that accepts or rejects inputs in its domain
> on the basis that these inputs specify a sequence of configurations that
> reach their final state.
>

Small Followup.

You may be trying to be precise, but you are also precisely WRONG, as
you try to precisely specify something that is actually very precisesly
defined, but you define it differently, and thus WRONGLY.

You don't get to change the Rules of the Game.

On 11/24/21 1:02 PM, Richard Damon wrote:
> Same Problem as before.
>
> Definition of Non-Halting is that is will not reach a halting state
> after an UNBOUNDED (not some finite) number of steps.
>
> Thus, your H is NOT a Halt Decider, because it doesn't even claim to
> follow the real definition of Halting.
>
> PERIOD.
>
> You just LIE claiming it is.
>
>
> We KNOW that if Hn(Pn,Pn) returns 0 then the direct execution of Pn(Pn)
> will Halt. You even have aggreed to it.
>
>
> In fact, woth your current definition that each Hn has some number N for
> the number of steps it will simulate before aborting its simulaton,
> there is a small number k, such that we know that Pn(Pn) will halt in
> N+k steps.
>
> The fact that N < N+k just shows that Hn was just a bit to impatient,
> and incorrect as a Halt Decider.
>
> FAIL.
>
>
> On 11/24/21 12:49 PM, olcott wrote:
>> #include <stdint.h>
>> #include <stdio.h>
>> typedef int (*ptr)();
>>
>> int H(ptr x, ptr y)
>> {
>>    x(y); // direct execution of P(P)
>>    return 1;
>> }
>>
>> // Minimal essence of Linz(1990) Ĥ
>> // and Strachey(1965) P
>> int P(ptr x)
>> {
>>    H(x, x);
>>    return 1; // Give P a last instruction at the "c" level
>> }
>>
>> int main(void)
>> {
>>    H(P, P);
>> }
>>
>> PSR set: It is self evident that when 0 to ∞ steps of the input to
>> H(P,P) are directly executed or correctly simulated that the input to
>> H(P,P) never reaches its final instruction.
>>
>> We can think of the combinations of (H,P) as an enumerated sequence of
>> finite strings of C source-code. The above source code specifies the
>> H0(P0,P0) first element of this sequence.
>>
>> Computation that halts
>> a computation is said to halt whenever it enters a final state.
>> (Linz:1990:234)
>>
>> PSR subset A: When Hn(Pn, Pn) executes or simulates a fixed number of
>> N steps of its input this input still never reaches its last
>> instruction and Hn(Pn, Pn) halts.
>>
>> PSR subset B: When Hn(Pn, Pn) executes or simulates a fixed number of
>> N steps of its input this input still never reaches its last
>> instruction and Hn(Pn, Pn) halts and Pn(Pn) called from main() halts.
>>
>> PSR subset C: For the subset of PSR subset A where Hn(Pn, Pn) returns
>> 0 the returned halt status corresponds to the actual behavior of the
>> input to Hn(Pn, Pn).
>>
>> PSR subset D: For the subset of PSR subset C where Hn(Pn, Pn) returns
>> 0 on the basis that this input matches the infinite recursion behavior
>> pattern. Hn(Pn, Pn) detects that its input is calling H again with the
>> same input that it was called with. This makes Hn a correct halt
>> decider of this input.
>>
>> H is a computable function that accepts or rejects inputs in its
>> domain on the basis that these inputs specify a sequence of
>> configurations that reach their final state.
>>
>

On 2021-11-24 10:49, olcott wrote:
> #include <stdint.h>
> #include <stdio.h>
> typedef int (*ptr)();
>
> int H(ptr x, ptr y)
> {
>   x(y); // direct execution of P(P)
>   return 1;
> }
>
> // Minimal essence of Linz(1990) Ĥ
> // and Strachey(1965) P
> int P(ptr x)
> {
>   H(x, x);
>   return 1; // Give P a last instruction at the "c" level
> }
>
> int main(void)
> {
>   H(P, P);
> }
>
> PSR set: It is self evident that when 0 to ∞ steps of the input to
> H(P,P) are directly executed or correctly simulated that the input to
> H(P,P) never reaches its final instruction.
>
> We can think of the combinations of (H,P) as an enumerated sequence of
> finite strings of C source-code. The above source code specifies the
> H0(P0,P0) first element of this sequence.
>
> Computation that halts
> a computation is said to halt whenever it enters a final state.
> (Linz:1990:234)
>
> PSR subset A: When Hn(Pn, Pn) executes or simulates a fixed number of N
> steps of its input this input still never reaches its last instruction
> and Hn(Pn, Pn) halts.
>
> PSR subset B: When Hn(Pn, Pn) executes or simulates a fixed number of N
> steps of its input this input still never reaches its last instruction
> and Hn(Pn, Pn) halts and Pn(Pn) called from main() halts.
>
> PSR subset C: For the subset of PSR subset A where Hn(Pn, Pn) returns 0
> the returned halt status corresponds to the actual behavior of the input
> to Hn(Pn, Pn).
>
> PSR subset D: For the subset of PSR subset C where Hn(Pn, Pn) returns 0
> on the basis that this input matches the infinite recursion behavior
> pattern. Hn(Pn, Pn) detects that its input is calling H again with the
> same input that it was called with. This makes Hn a correct halt decider
> of this input.
>
> H is a computable function that accepts or rejects inputs in its domain
> on the basis that these inputs specify a sequence of configurations that
> reach their final state.

The H you've given above is a computer program, not a computable
function. Functions are mathematical objects. Computable functions are
functions where it is possible to construct a program which computes
them, but the program isn't a 'computable function', its a program.

And the H you provide above cannot reject *any* input, so it is not the
same H that you describe in your final paragraph.

André

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

On 11/24/2021 12:06 PM, André G. Isaak wrote:
> On 2021-11-24 10:49, olcott wrote:
>> #include <stdint.h>
>> #include <stdio.h>
>> typedef int (*ptr)();
>>
>> int H(ptr x, ptr y)
>> {
>>    x(y); // direct execution of P(P)
>>    return 1;
>> }
>>
>> // Minimal essence of Linz(1990) Ĥ
>> // and Strachey(1965) P
>> int P(ptr x)
>> {
>>    H(x, x);
>>    return 1; // Give P a last instruction at the "c" level
>> }
>>
>> int main(void)
>> {
>>    H(P, P);
>> }
>>
>> PSR set: It is self evident that when 0 to ∞ steps of the input to
>> H(P,P) are directly executed or correctly simulated that the input to
>> H(P,P) never reaches its final instruction.
>>
>> We can think of the combinations of (H,P) as an enumerated sequence of
>> finite strings of C source-code. The above source code specifies the
>> H0(P0,P0) first element of this sequence.
>>
>> Computation that halts
>> a computation is said to halt whenever it enters a final state.
>> (Linz:1990:234)
>>
>> PSR subset A: When Hn(Pn, Pn) executes or simulates a fixed number of
>> N steps of its input this input still never reaches its last
>> instruction and Hn(Pn, Pn) halts.
>>
>> PSR subset B: When Hn(Pn, Pn) executes or simulates a fixed number of
>> N steps of its input this input still never reaches its last
>> instruction and Hn(Pn, Pn) halts and Pn(Pn) called from main() halts.
>>
>> PSR subset C: For the subset of PSR subset A where Hn(Pn, Pn) returns
>> 0 the returned halt status corresponds to the actual behavior of the
>> input to Hn(Pn, Pn).
>>
>> PSR subset D: For the subset of PSR subset C where Hn(Pn, Pn) returns
>> 0 on the basis that this input matches the infinite recursion behavior
>> pattern. Hn(Pn, Pn) detects that its input is calling H again with the
>> same input that it was called with. This makes Hn a correct halt
>> decider of this input.
>>
>> H is a computable function that accepts or rejects inputs in its
>> domain on the basis that these inputs specify a sequence of
>> configurations that reach their final state.
>
> The H you've given above is a computer program, not a computable
> function.

Because H is a pure function it is a computable function. Adaptations to
ensure this part took six months to find and are trivial one found.

Pure function
In computer programming, a pure function is a function that has the
following properties:

The function return values are identical for identical arguments (no
variation with local static variables, non-local variables, mutable
reference arguments or input streams).

The function application has no side effects (no mutation of local
static variables, non-local variables, mutable reference arguments or
input/output streams).

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

> Functions are mathematical objects. Computable functions are
> functions where it is possible to construct a program which computes
> them, but the program isn't a 'computable function', its a program.
>
> And the H you provide above cannot reject *any* input, so it is not the
> same H that you describe in your final paragraph.
>
> André
>

PSR subset D does correctly reject its input.

--
Copyright 2021 Pete Olcott

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

On 11/24/21 1:22 PM, olcott wrote:
> On 11/24/2021 12:06 PM, André G. Isaak wrote:
>> On 2021-11-24 10:49, olcott wrote:
>>> #include <stdint.h>
>>> #include <stdio.h>
>>> typedef int (*ptr)();
>>>
>>> int H(ptr x, ptr y)
>>> {
>>>    x(y); // direct execution of P(P)
>>>    return 1;
>>> }
>>>
>>> // Minimal essence of Linz(1990) Ĥ
>>> // and Strachey(1965) P
>>> int P(ptr x)
>>> {
>>>    H(x, x);
>>>    return 1; // Give P a last instruction at the "c" level
>>> }
>>>
>>> int main(void)
>>> {
>>>    H(P, P);
>>> }
>>>
>>> PSR set: It is self evident that when 0 to ∞ steps of the input to
>>> H(P,P) are directly executed or correctly simulated that the input to
>>> H(P,P) never reaches its final instruction.
>>>
>>> We can think of the combinations of (H,P) as an enumerated sequence
>>> of finite strings of C source-code. The above source code specifies
>>> the H0(P0,P0) first element of this sequence.
>>>
>>> Computation that halts
>>> a computation is said to halt whenever it enters a final state.
>>> (Linz:1990:234)
>>>
>>> PSR subset A: When Hn(Pn, Pn) executes or simulates a fixed number of
>>> N steps of its input this input still never reaches its last
>>> instruction and Hn(Pn, Pn) halts.
>>>
>>> PSR subset B: When Hn(Pn, Pn) executes or simulates a fixed number of
>>> N steps of its input this input still never reaches its last
>>> instruction and Hn(Pn, Pn) halts and Pn(Pn) called from main() halts.
>>>
>>> PSR subset C: For the subset of PSR subset A where Hn(Pn, Pn) returns
>>> 0 the returned halt status corresponds to the actual behavior of the
>>> input to Hn(Pn, Pn).
>>>
>>> PSR subset D: For the subset of PSR subset C where Hn(Pn, Pn) returns
>>> 0 on the basis that this input matches the infinite recursion
>>> behavior pattern. Hn(Pn, Pn) detects that its input is calling H
>>> again with the same input that it was called with. This makes Hn a
>>> correct halt decider of this input.
>>>
>>> H is a computable function that accepts or rejects inputs in its
>>> domain on the basis that these inputs specify a sequence of
>>> configurations that reach their final state.
>>
>> The H you've given above is a computer program, not a computable
>> function.
>
> Because H is a pure function it is a computable function. Adaptations to
> ensure this part took six months to find and are trivial one found.

You are making a category error.

'Pure Functions' as you are using them refer to computer code with
certain properties.

'Computable Functions' are mathematical concepts, they are strictly a
MAPPING of input values to output values. They are not 'Computer Code'.

'Computable Functions' are a subset of the more general 'Functions' of
mathematics which are also general mappings of inputs to output. The
difference between a 'Computatable Function' and a just 'Function' is
that for a "Computable Function' it is possible to write an algorithm
(like a computer program) that takes an input in the domain of the
mapping and produces the corresponding output in a finite number of steps.

That algorithm/computer program is NOT a 'Computable Function' but an
algorithm that IMPLEMENTS that Computable Function.

>
> Pure function
> In computer programming, a pure function is a function that has the
> following properties:
>
> The function return values are identical for identical arguments (no
> variation with local static variables, non-local variables, mutable
> reference arguments or input streams).
>
> The function application has no side effects (no mutation of local
> static variables, non-local variables, mutable reference arguments or
> input/output streams).
>
> https://en.wikipedia.org/wiki/Pure_function
>
>> Functions are mathematical objects. Computable functions are functions
>> where it is possible to construct a program which computes them, but
>> the program isn't a 'computable function', its a program.
>>
>> And the H you provide above cannot reject *any* input, so it is not
>> the same H that you describe in your final paragraph.
>>
>> André
>>
>
> PSR subset D does correctly reject its input.
>
>

LIE, it doesn't (or is an empty set). As we can show that for ANY Hn
that returns 0 for Hn(Pn,Pn) that the corresponding Pn(Pn) will Halt.

Thus, BY THE DEFINITION OF THE HALTING PROBLEM, Hn is NOT a correct Halt
Decider for Pn(Pn) as requested by Hn(Pn,Pn) PERIOD.

Your 'Proof' uses unsound logic. FAIL.

On 2021-11-24 11:22, olcott wrote:
> On 11/24/2021 12:06 PM, André G. Isaak wrote:
>> On 2021-11-24 10:49, olcott wrote:
>>> #include <stdint.h>
>>> #include <stdio.h>
>>> typedef int (*ptr)();
>>>
>>> int H(ptr x, ptr y)
>>> {
>>>    x(y); // direct execution of P(P)
>>>    return 1;
>>> }
>>>
>>> // Minimal essence of Linz(1990) Ĥ
>>> // and Strachey(1965) P
>>> int P(ptr x)
>>> {
>>>    H(x, x);
>>>    return 1; // Give P a last instruction at the "c" level
>>> }
>>>
>>> int main(void)
>>> {
>>>    H(P, P);
>>> }
>>>
>>> PSR set: It is self evident that when 0 to ∞ steps of the input to
>>> H(P,P) are directly executed or correctly simulated that the input to
>>> H(P,P) never reaches its final instruction.
>>>
>>> We can think of the combinations of (H,P) as an enumerated sequence
>>> of finite strings of C source-code. The above source code specifies
>>> the H0(P0,P0) first element of this sequence.
>>>
>>> Computation that halts
>>> a computation is said to halt whenever it enters a final state.
>>> (Linz:1990:234)
>>>
>>> PSR subset A: When Hn(Pn, Pn) executes or simulates a fixed number of
>>> N steps of its input this input still never reaches its last
>>> instruction and Hn(Pn, Pn) halts.
>>>
>>> PSR subset B: When Hn(Pn, Pn) executes or simulates a fixed number of
>>> N steps of its input this input still never reaches its last
>>> instruction and Hn(Pn, Pn) halts and Pn(Pn) called from main() halts.
>>>
>>> PSR subset C: For the subset of PSR subset A where Hn(Pn, Pn) returns
>>> 0 the returned halt status corresponds to the actual behavior of the
>>> input to Hn(Pn, Pn).
>>>
>>> PSR subset D: For the subset of PSR subset C where Hn(Pn, Pn) returns
>>> 0 on the basis that this input matches the infinite recursion
>>> behavior pattern. Hn(Pn, Pn) detects that its input is calling H
>>> again with the same input that it was called with. This makes Hn a
>>> correct halt decider of this input.
>>>
>>> H is a computable function that accepts or rejects inputs in its
>>> domain on the basis that these inputs specify a sequence of
>>> configurations that reach their final state.
>>
>> The H you've given above is a computer program, not a computable
>> function.
>
> Because H is a pure function it is a computable function. Adaptations to
> ensure this part took six months to find and are trivial one found.

Why is it that every time someone attempts to correct your misuse of
terminology you double down? Despite the fact that you claim that you
are posting here so you can learn the 'correct terminology'.

A "pure function" is a type of computer function.

A computable function is a type of mathematical function.

The term 'function' refers to different things in computer programming
and in math.

Consider the function y = x². Here is a what the *mathematical* function
looks like:

{ (0, 0), (1, 1), (2, 4), (3, 9), (4, 16), (5, 25)... }

A mathematical function is simply a mapping. It contains no information
about how the two members of each pair are related or how to derive the
second member of any given pair from the first. It contains no
instructions. The only requirement is that every member of the domain
occur as the first member of one and only one pair in that set.

For some, but not all, functions it is possible to construct an
algorithm which allows one to determine the second member of each pair
from the first. Those are functions that are computable functions.

A computer function is the instantiation of an algorithm, and unlike a
mathematical computation includes a sequence of steps which allows one
to mechanically determine the value of the second member of a pair from
the first. For the above function, the C function might be as follows:

int SQR(int x) {
return (x * x);
}

SQR() is a computer function which computes a specific mathematical
function, but it is *not* that mathematical function.

The halting function is simply a set of pairs of the form ((M, I), S)
where M is a Turing Machine, I is an input, and S is the halting status
of that machine. Somewhere in that set will be the pair ((P, P), true)
since the independent computation P(P) halts.

Note that here it is meaningless to talk about things like 'pathological
self-reference' since there are no instructions being performed here.
There is simply a mapping. What you call 'pathological self-reference'
only arises when you actually try to construct an algorithm for
determining that (P, P) maps to true.

And that is why the halting function is not a *computable* function. It
is not possible to construct a TM which, for *every* element of the
halting function can determine what the second member of the pair is
based on the first.

And, as I have said, the halting function exists INDEPENDENTLY of any
particular decider. The set { ....((P,P), true)... } is simply 'out
there' so to speak. A halt decider is an algorithm which must then be
able to determine that the pair whose first member is (P, P) in that set
has 'true' as its second member.

Linz demonstrates that this isn't possible. *YOU'VE* demonstrated that
this isn't possible but you keep trying to change the rules of the game
so you can maintain that your 'decider' is somehow getting the right
answer when it is not. A halt decider must compute the halting function
as described above.

> Pure function
> In computer programming, a pure function is a function that has the
> following properties:
>
> The function return values are identical for identical arguments (no
> variation with local static variables, non-local variables, mutable
> reference arguments or input streams).
>
> The function application has no side effects (no mutation of local
> static variables, non-local variables, mutable reference arguments or
> input/output streams).
>
> https://en.wikipedia.org/wiki/Pure_function
>
>> Functions are mathematical objects. Computable functions are functions
>> where it is possible to construct a program which computes them, but
>> the program isn't a 'computable function', its a program.
>>
>> And the H you provide above cannot reject *any* input, so it is not
>> the same H that you describe in your final paragraph.
>>
>> André
>>
>
> PSR subset D does correctly reject its input.

Sets don't accept or reject things at all. Turing Machine accept or
reject things.

André

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

On 11/24/2021 1:19 PM, André G. Isaak wrote:
> On 2021-11-24 11:22, olcott wrote:
>> On 11/24/2021 12:06 PM, André G. Isaak wrote:
>>> On 2021-11-24 10:49, olcott wrote:
>>>> #include <stdint.h>
>>>> #include <stdio.h>
>>>> typedef int (*ptr)();
>>>>
>>>> int H(ptr x, ptr y)
>>>> {
>>>>    x(y); // direct execution of P(P)
>>>>    return 1;
>>>> }
>>>>
>>>> // Minimal essence of Linz(1990) Ĥ
>>>> // and Strachey(1965) P
>>>> int P(ptr x)
>>>> {
>>>>    H(x, x);
>>>>    return 1; // Give P a last instruction at the "c" level
>>>> }
>>>>
>>>> int main(void)
>>>> {
>>>>    H(P, P);
>>>> }
>>>>
>>>> PSR set: It is self evident that when 0 to ∞ steps of the input to
>>>> H(P,P) are directly executed or correctly simulated that the input
>>>> to H(P,P) never reaches its final instruction.
>>>>
>>>> We can think of the combinations of (H,P) as an enumerated sequence
>>>> of finite strings of C source-code. The above source code specifies
>>>> the H0(P0,P0) first element of this sequence.
>>>>
>>>> Computation that halts
>>>> a computation is said to halt whenever it enters a final state.
>>>> (Linz:1990:234)
>>>>
>>>> PSR subset A: When Hn(Pn, Pn) executes or simulates a fixed number
>>>> of N steps of its input this input still never reaches its last
>>>> instruction and Hn(Pn, Pn) halts.
>>>>
>>>> PSR subset B: When Hn(Pn, Pn) executes or simulates a fixed number
>>>> of N steps of its input this input still never reaches its last
>>>> instruction and Hn(Pn, Pn) halts and Pn(Pn) called from main() halts.
>>>>
>>>> PSR subset C: For the subset of PSR subset A where Hn(Pn, Pn)
>>>> returns 0 the returned halt status corresponds to the actual
>>>> behavior of the input to Hn(Pn, Pn).
>>>>
>>>> PSR subset D: For the subset of PSR subset C where Hn(Pn, Pn)
>>>> returns 0 on the basis that this input matches the infinite
>>>> recursion behavior pattern. Hn(Pn, Pn) detects that its input is
>>>> calling H again with the same input that it was called with. This
>>>> makes Hn a correct halt decider of this input.
>>>>
>>>> H is a computable function that accepts or rejects inputs in its
>>>> domain on the basis that these inputs specify a sequence of
>>>> configurations that reach their final state.
>>>
>>> The H you've given above is a computer program, not a computable
>>> function.
>>
>> Because H is a pure function it is a computable function. Adaptations
>> to ensure this part took six months to find and are trivial one found.
>
> Why is it that every time someone attempts to correct your misuse of
> terminology you double down? Despite the fact that you claim that you
> are posting here so you can learn the 'correct terminology'.
>
> A "pure function" is a type of computer function.
>
> A computable function is a type of mathematical function.
>
> The term 'function' refers to different things in computer programming
> and in math.
>
> Consider the function y = x². Here is a what the *mathematical* function
> looks like:
>
> { (0, 0), (1, 1), (2, 4), (3, 9), (4, 16), (5, 25)... }
>
> A mathematical function is simply a mapping. It contains no information
> about how the two members of each pair are related or how to derive the
> second member of any given pair from the first. It contains no
> instructions. The only requirement is that every member of the domain
> occur as the first member of one and only one pair in that set.
>
> For some, but not all, functions it is possible to construct an
> algorithm which allows one to determine the second member of each pair
> from the first. Those are functions that are computable functions.
>
> A computer function is the instantiation of an algorithm, and unlike a
> mathematical computation includes a sequence of steps which allows one
> to mechanically determine the value of the second member of a pair from
> the first. For the above function, the C function might be as follows:
>
> int SQR(int x) {
>     return (x * x);
> }
>
> SQR() is a computer function which computes a specific mathematical
> function, but it is *not* that mathematical function.
>
> The halting function is simply a set of pairs of the form ((M, I), S)
> where M is a Turing Machine, I is an input, and S is the halting status
> of that machine. Somewhere in that set will be the pair ((P, P), true)
> since the independent computation P(P) halts.
>
> Note that here it is meaningless to talk about things like 'pathological
> self-reference' since there are no instructions being performed here.
> There is simply a mapping. What you call 'pathological self-reference'
> only arises when you actually try to construct an algorithm for
> determining that (P, P) maps to true.
>

No. Not at all. The mapping of PSR to a digraph has cycles.

> And that is why the halting function is not a *computable* function. It
> is not possible to construct a TM which, for *every* element of the
> halting function can determine what the second member of the pair is
> based on the first.
>
> And, as I have said, the halting function exists INDEPENDENTLY of any
> particular decider. The set { ....((P,P), true)... } is simply 'out
> there' so to speak. A halt decider is an algorithm which must then be
> able to determine that the pair whose first member is (P, P) in that set
> has 'true' as its second member.
>

That is not true when the input is based on invoking a specifc decider.
The mapping to a digraph contains cycles that do not exist for other
inputs.

> Linz demonstrates that this isn't possible. *YOU'VE* demonstrated that
> this isn't possible but you keep trying to change the rules of the game
> so you can maintain that your 'decider' is somehow getting the right
> answer when it is not. A halt decider must compute the halting function
> as described above.
>

Computable functions are the basic objects of study in computability
theory. Computable functions are the formalized analogue of the
intuitive notion of algorithms, in the sense that a function is
computable if there exists an algorithm that can do the job of the
function, i.e. given an input of the function domain it can return the
corresponding output.

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

>> Pure function
>> In computer programming, a pure function is a function that has the
>> following properties:
>>
>> The function return values are identical for identical arguments (no
>> variation with local static variables, non-local variables, mutable
>> reference arguments or input streams).
>>
>> The function application has no side effects (no mutation of local
>> static variables, non-local variables, mutable reference arguments or
>> input/output streams).
>>
>> https://en.wikipedia.org/wiki/Pure_function
>>
>>> Functions are mathematical objects. Computable functions are
>>> functions where it is possible to construct a program which computes
>>> them, but the program isn't a 'computable function', its a program.
>>>
>>> And the H you provide above cannot reject *any* input, so it is not
>>> the same H that you describe in your final paragraph.
>>>
>>> André
>>>
>>
>> PSR subset D does correctly reject its input.
>
> Sets don't accept or reject things at all. Turing Machine accept or
> reject things.
>
> André
>

--
Copyright 2021 Pete Olcott

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

On 2021-11-24 12:36, olcott wrote:
> On 11/24/2021 1:19 PM, André G. Isaak wrote:
>> On 2021-11-24 11:22, olcott wrote:
>>> On 11/24/2021 12:06 PM, André G. Isaak wrote:
>>>> On 2021-11-24 10:49, olcott wrote:
>>>>> #include <stdint.h>
>>>>> #include <stdio.h>
>>>>> typedef int (*ptr)();
>>>>>
>>>>> int H(ptr x, ptr y)
>>>>> {
>>>>>    x(y); // direct execution of P(P)
>>>>>    return 1;
>>>>> }
>>>>>
>>>>> // Minimal essence of Linz(1990) Ĥ
>>>>> // and Strachey(1965) P
>>>>> int P(ptr x)
>>>>> {
>>>>>    H(x, x);
>>>>>    return 1; // Give P a last instruction at the "c" level
>>>>> }
>>>>>
>>>>> int main(void)
>>>>> {
>>>>>    H(P, P);
>>>>> }
>>>>>
>>>>> PSR set: It is self evident that when 0 to ∞ steps of the input to
>>>>> H(P,P) are directly executed or correctly simulated that the input
>>>>> to H(P,P) never reaches its final instruction.
>>>>>
>>>>> We can think of the combinations of (H,P) as an enumerated sequence
>>>>> of finite strings of C source-code. The above source code specifies
>>>>> the H0(P0,P0) first element of this sequence.
>>>>>
>>>>> Computation that halts
>>>>> a computation is said to halt whenever it enters a final state.
>>>>> (Linz:1990:234)
>>>>>
>>>>> PSR subset A: When Hn(Pn, Pn) executes or simulates a fixed number
>>>>> of N steps of its input this input still never reaches its last
>>>>> instruction and Hn(Pn, Pn) halts.
>>>>>
>>>>> PSR subset B: When Hn(Pn, Pn) executes or simulates a fixed number
>>>>> of N steps of its input this input still never reaches its last
>>>>> instruction and Hn(Pn, Pn) halts and Pn(Pn) called from main() halts.
>>>>>
>>>>> PSR subset C: For the subset of PSR subset A where Hn(Pn, Pn)
>>>>> returns 0 the returned halt status corresponds to the actual
>>>>> behavior of the input to Hn(Pn, Pn).
>>>>>
>>>>> PSR subset D: For the subset of PSR subset C where Hn(Pn, Pn)
>>>>> returns 0 on the basis that this input matches the infinite
>>>>> recursion behavior pattern. Hn(Pn, Pn) detects that its input is
>>>>> calling H again with the same input that it was called with. This
>>>>> makes Hn a correct halt decider of this input.
>>>>>
>>>>> H is a computable function that accepts or rejects inputs in its
>>>>> domain on the basis that these inputs specify a sequence of
>>>>> configurations that reach their final state.
>>>>
>>>> The H you've given above is a computer program, not a computable
>>>> function.
>>>
>>> Because H is a pure function it is a computable function. Adaptations
>>> to ensure this part took six months to find and are trivial one found.
>>
>> Why is it that every time someone attempts to correct your misuse of
>> terminology you double down? Despite the fact that you claim that you
>> are posting here so you can learn the 'correct terminology'.
>>
>> A "pure function" is a type of computer function.
>>
>> A computable function is a type of mathematical function.
>>
>> The term 'function' refers to different things in computer programming
>> and in math.
>>
>> Consider the function y = x². Here is a what the *mathematical*
>> function looks like:
>>
>> { (0, 0), (1, 1), (2, 4), (3, 9), (4, 16), (5, 25)... }
>>
>> A mathematical function is simply a mapping. It contains no
>> information about how the two members of each pair are related or how
>> to derive the second member of any given pair from the first. It
>> contains no instructions. The only requirement is that every member of
>> the domain occur as the first member of one and only one pair in that
>> set.
>>
>> For some, but not all, functions it is possible to construct an
>> algorithm which allows one to determine the second member of each pair
>> from the first. Those are functions that are computable functions.
>>
>> A computer function is the instantiation of an algorithm, and unlike a
>> mathematical computation includes a sequence of steps which allows one
>> to mechanically determine the value of the second member of a pair
>> from the first. For the above function, the C function might be as
>> follows:
>>
>> int SQR(int x) {
>>      return (x * x);
>> }
>>
>> SQR() is a computer function which computes a specific mathematical
>> function, but it is *not* that mathematical function.
>>
>> The halting function is simply a set of pairs of the form ((M, I), S)
>> where M is a Turing Machine, I is an input, and S is the halting
>> status of that machine. Somewhere in that set will be the pair ((P,
>> P), true) since the independent computation P(P) halts.
>>
>> Note that here it is meaningless to talk about things like
>> 'pathological self-reference' since there are no instructions being
>> performed here. There is simply a mapping. What you call 'pathological
>> self-reference' only arises when you actually try to construct an
>> algorithm for determining that (P, P) maps to true.
>>
>
> No. Not at all. The mapping of PSR to a digraph has cycles.

Reread what I wrote. The halting *function* is simply a set of pairs.
How can an ordered pair such as ((P, P), true) contain a cycle?

>> And that is why the halting function is not a *computable* function.
>> It is not possible to construct a TM which, for *every* element of the
>> halting function can determine what the second member of the pair is
>> based on the first.
>>
>> And, as I have said, the halting function exists INDEPENDENTLY of any
>> particular decider. The set { ....((P,P), true)... } is simply 'out
>> there' so to speak. A halt decider is an algorithm which must then be
>> able to determine that the pair whose first member is (P, P) in that
>> set has 'true' as its second member.
>>
>
> That is not true when the input is based on invoking a specifc decider.

But the halting *function* doesn't involve any decider. It is simply a
mapping from computations to their halting status.

Again, reread what I wrote. Mathematical functions don't involve
"invoking" anything. They are simply mappings, i.e. sets of ordered pairs.

The job of a halt *decider* is to compute the mappings contained in that
function.

> The mapping to a digraph contains cycles that do not exist for other
> inputs.
>> Linz demonstrates that this isn't possible. *YOU'VE* demonstrated that
>> this isn't possible but you keep trying to change the rules of the
>> game so you can maintain that your 'decider' is somehow getting the
>> right answer when it is not. A halt decider must compute the halting
>> function as described above.
>>
>
>
> Computable functions are the basic objects of study in computability
> theory. Computable functions are the formalized analogue of the
> intuitive notion of algorithms,

No, they are not. A computable function is a function for which it is
*possible* to construct an algorithm. But a computable function is *not*
an algorithm. It is simply a set of ordered pairs.

Once again, I ask, why is it that when people attempt to correct you on
your misuse of terminology you insist on doubling down rather than
carefully reading what is said to try to understand the distinction
between terms that is being brought to your attention?

André

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

On 11/24/21 2:36 PM, olcott wrote:
> On 11/24/2021 1:19 PM, André G. Isaak wrote:
>> On 2021-11-24 11:22, olcott wrote:
>>> On 11/24/2021 12:06 PM, André G. Isaak wrote:
>>>> On 2021-11-24 10:49, olcott wrote:
>>>>> #include <stdint.h>
>>>>> #include <stdio.h>
>>>>> typedef int (*ptr)();
>>>>>
>>>>> int H(ptr x, ptr y)
>>>>> {
>>>>>    x(y); // direct execution of P(P)
>>>>>    return 1;
>>>>> }
>>>>>
>>>>> // Minimal essence of Linz(1990) Ĥ
>>>>> // and Strachey(1965) P
>>>>> int P(ptr x)
>>>>> {
>>>>>    H(x, x);
>>>>>    return 1; // Give P a last instruction at the "c" level
>>>>> }
>>>>>
>>>>> int main(void)
>>>>> {
>>>>>    H(P, P);
>>>>> }
>>>>>
>>>>> PSR set: It is self evident that when 0 to ∞ steps of the input to
>>>>> H(P,P) are directly executed or correctly simulated that the input
>>>>> to H(P,P) never reaches its final instruction.
>>>>>
>>>>> We can think of the combinations of (H,P) as an enumerated sequence
>>>>> of finite strings of C source-code. The above source code specifies
>>>>> the H0(P0,P0) first element of this sequence.
>>>>>
>>>>> Computation that halts
>>>>> a computation is said to halt whenever it enters a final state.
>>>>> (Linz:1990:234)
>>>>>
>>>>> PSR subset A: When Hn(Pn, Pn) executes or simulates a fixed number
>>>>> of N steps of its input this input still never reaches its last
>>>>> instruction and Hn(Pn, Pn) halts.
>>>>>
>>>>> PSR subset B: When Hn(Pn, Pn) executes or simulates a fixed number
>>>>> of N steps of its input this input still never reaches its last
>>>>> instruction and Hn(Pn, Pn) halts and Pn(Pn) called from main() halts.
>>>>>
>>>>> PSR subset C: For the subset of PSR subset A where Hn(Pn, Pn)
>>>>> returns 0 the returned halt status corresponds to the actual
>>>>> behavior of the input to Hn(Pn, Pn).
>>>>>
>>>>> PSR subset D: For the subset of PSR subset C where Hn(Pn, Pn)
>>>>> returns 0 on the basis that this input matches the infinite
>>>>> recursion behavior pattern. Hn(Pn, Pn) detects that its input is
>>>>> calling H again with the same input that it was called with. This
>>>>> makes Hn a correct halt decider of this input.
>>>>>
>>>>> H is a computable function that accepts or rejects inputs in its
>>>>> domain on the basis that these inputs specify a sequence of
>>>>> configurations that reach their final state.
>>>>
>>>> The H you've given above is a computer program, not a computable
>>>> function.
>>>
>>> Because H is a pure function it is a computable function. Adaptations
>>> to ensure this part took six months to find and are trivial one found.
>>
>> Why is it that every time someone attempts to correct your misuse of
>> terminology you double down? Despite the fact that you claim that you
>> are posting here so you can learn the 'correct terminology'.
>>
>> A "pure function" is a type of computer function.
>>
>> A computable function is a type of mathematical function.
>>
>> The term 'function' refers to different things in computer programming
>> and in math.
>>
>> Consider the function y = x². Here is a what the *mathematical*
>> function looks like:
>>
>> { (0, 0), (1, 1), (2, 4), (3, 9), (4, 16), (5, 25)... }
>>
>> A mathematical function is simply a mapping. It contains no
>> information about how the two members of each pair are related or how
>> to derive the second member of any given pair from the first. It
>> contains no instructions. The only requirement is that every member of
>> the domain occur as the first member of one and only one pair in that
>> set.
>>
>> For some, but not all, functions it is possible to construct an
>> algorithm which allows one to determine the second member of each pair
>> from the first. Those are functions that are computable functions.
>>
>> A computer function is the instantiation of an algorithm, and unlike a
>> mathematical computation includes a sequence of steps which allows one
>> to mechanically determine the value of the second member of a pair
>> from the first. For the above function, the C function might be as
>> follows:
>>
>> int SQR(int x) {
>>      return (x * x);
>> }
>>
>> SQR() is a computer function which computes a specific mathematical
>> function, but it is *not* that mathematical function.
>>
>> The halting function is simply a set of pairs of the form ((M, I), S)
>> where M is a Turing Machine, I is an input, and S is the halting
>> status of that machine. Somewhere in that set will be the pair ((P,
>> P), true) since the independent computation P(P) halts.
>>
>> Note that here it is meaningless to talk about things like
>> 'pathological self-reference' since there are no instructions being
>> performed here. There is simply a mapping. What you call 'pathological
>> self-reference' only arises when you actually try to construct an
>> algorithm for determining that (P, P) maps to true.
>>
>
> No. Not at all. The mapping of PSR to a digraph has cycles.

No, it doesn't.

ALL your elements of the set you call PSR have FINITE STRING
representation (assuming you H exists and is of finite code size).

(P adds a finite amount to the length of that representation)

The input side of the mapping for the Halting Function is THIS STRING.

There are NO CYCLES in this string.

Note, Perhaps you are thinking that you need to make the string be
P:H:P:H:P:H ... as that is the execution path when you consider the
simulation/debug execute, but you don't

The input string representation for P is the code for P, appended with
the code for H, appended with the code for anything that H calls, and so on.

Let us call that string <P>

The mapping element for this computaton is therefore just the element
((<P>,<P>), True) (at least if H(<P>,<P>) is returning 0)

Finite and non-cyclic.

You seem to be confusing the execution trace with the input.

And actually, if you map the ACTUAL execution trace of what is ACTUALLY
running, it CAN'T have a real cycle (if you are tracking state/tape
combinations) as if you EVER reach an identical state that you have
preveously been in, you are stuck in an infinite loop. This is what
happens with your H0 that doesn't abort.

Note, this property applies to ACTUAL traces, not 'equivalent traces'
where you do things like replacing simulations of conditional simulators
with the machine you are simulating as that hides some of the state.

>
>> And that is why the halting function is not a *computable* function.
>> It is not possible to construct a TM which, for *every* element of the
>> halting function can determine what the second member of the pair is
>> based on the first.
>>
>> And, as I have said, the halting function exists INDEPENDENTLY of any
>> particular decider. The set { ....((P,P), true)... } is simply 'out
>> there' so to speak. A halt decider is an algorithm which must then be
>> able to determine that the pair whose first member is (P, P) in that
>> set has 'true' as its second member.
>>
>
> That is not true when the input is based on invoking a specifc decider.
> The mapping to a digraph contains cycles that do not exist for other
> inputs.

LIE. Shows your ignorance.

Remember the computation P INCLUDES the code for H, so there is no cycle.

Now, you could define P differently as P(h,p) which calls h(p,h,p) and
does the opposite, and then we look at P(H,P) and compare that to
H(P,H,P) but the just exposes even more you attempts to change the Halt
decider used inside P.

>
>> Linz demonstrates that this isn't possible. *YOU'VE* demonstrated that
>> this isn't possible but you keep trying to change the rules of the
>> game so you can maintain that your 'decider' is somehow getting the
>> right answer when it is not. A halt decider must compute the halting
>> function as described above.
>>
>
>
> Computable functions are the basic objects of study in computability
> theory. Computable functions are the formalized analogue of the
> intuitive notion of algorithms, in the sense that a function is
> computable if there exists an algorithm that can do the job of the
> function, i.e. given an input of the function domain it can return the
> corresponding output.
>
> https://en.wikipedia.org/wiki/Computable_function

On 11/24/2021 1:48 PM, André G. Isaak wrote:
> On 2021-11-24 12:36, olcott wrote:
>> On 11/24/2021 1:19 PM, André G. Isaak wrote:
>>> On 2021-11-24 11:22, olcott wrote:
>>>> On 11/24/2021 12:06 PM, André G. Isaak wrote:
>>>>> On 2021-11-24 10:49, olcott wrote:
>>>>>> #include <stdint.h>
>>>>>> #include <stdio.h>
>>>>>> typedef int (*ptr)();
>>>>>>
>>>>>> int H(ptr x, ptr y)
>>>>>> {
>>>>>>    x(y); // direct execution of P(P)
>>>>>>    return 1;
>>>>>> }
>>>>>>
>>>>>> // Minimal essence of Linz(1990) Ĥ
>>>>>> // and Strachey(1965) P
>>>>>> int P(ptr x)
>>>>>> {
>>>>>>    H(x, x);
>>>>>>    return 1; // Give P a last instruction at the "c" level
>>>>>> }
>>>>>>
>>>>>> int main(void)
>>>>>> {
>>>>>>    H(P, P);
>>>>>> }
>>>>>>
>>>>>> PSR set: It is self evident that when 0 to ∞ steps of the input to
>>>>>> H(P,P) are directly executed or correctly simulated that the input
>>>>>> to H(P,P) never reaches its final instruction.
>>>>>>
>>>>>> We can think of the combinations of (H,P) as an enumerated
>>>>>> sequence of finite strings of C source-code. The above source code
>>>>>> specifies the H0(P0,P0) first element of this sequence.
>>>>>>
>>>>>> Computation that halts
>>>>>> a computation is said to halt whenever it enters a final state.
>>>>>> (Linz:1990:234)
>>>>>>
>>>>>> PSR subset A: When Hn(Pn, Pn) executes or simulates a fixed number
>>>>>> of N steps of its input this input still never reaches its last
>>>>>> instruction and Hn(Pn, Pn) halts.
>>>>>>
>>>>>> PSR subset B: When Hn(Pn, Pn) executes or simulates a fixed number
>>>>>> of N steps of its input this input still never reaches its last
>>>>>> instruction and Hn(Pn, Pn) halts and Pn(Pn) called from main() halts.
>>>>>>
>>>>>> PSR subset C: For the subset of PSR subset A where Hn(Pn, Pn)
>>>>>> returns 0 the returned halt status corresponds to the actual
>>>>>> behavior of the input to Hn(Pn, Pn).
>>>>>>
>>>>>> PSR subset D: For the subset of PSR subset C where Hn(Pn, Pn)
>>>>>> returns 0 on the basis that this input matches the infinite
>>>>>> recursion behavior pattern. Hn(Pn, Pn) detects that its input is
>>>>>> calling H again with the same input that it was called with. This
>>>>>> makes Hn a correct halt decider of this input.
>>>>>>
>>>>>> H is a computable function that accepts or rejects inputs in its
>>>>>> domain on the basis that these inputs specify a sequence of
>>>>>> configurations that reach their final state.
>>>>>
>>>>> The H you've given above is a computer program, not a computable
>>>>> function.
>>>>
>>>> Because H is a pure function it is a computable function.
>>>> Adaptations to ensure this part took six months to find and are
>>>> trivial one found.
>>>
>>> Why is it that every time someone attempts to correct your misuse of
>>> terminology you double down? Despite the fact that you claim that you
>>> are posting here so you can learn the 'correct terminology'.
>>>
>>> A "pure function" is a type of computer function.
>>>
>>> A computable function is a type of mathematical function.
>>>
>>> The term 'function' refers to different things in computer
>>> programming and in math.
>>>
>>> Consider the function y = x². Here is a what the *mathematical*
>>> function looks like:
>>>
>>> { (0, 0), (1, 1), (2, 4), (3, 9), (4, 16), (5, 25)... }
>>>
>>> A mathematical function is simply a mapping. It contains no
>>> information about how the two members of each pair are related or how
>>> to derive the second member of any given pair from the first. It
>>> contains no instructions. The only requirement is that every member
>>> of the domain occur as the first member of one and only one pair in
>>> that set.
>>>
>>> For some, but not all, functions it is possible to construct an
>>> algorithm which allows one to determine the second member of each
>>> pair from the first. Those are functions that are computable functions.
>>>
>>> A computer function is the instantiation of an algorithm, and unlike
>>> a mathematical computation includes a sequence of steps which allows
>>> one to mechanically determine the value of the second member of a
>>> pair from the first. For the above function, the C function might be
>>> as follows:
>>>
>>> int SQR(int x) {
>>>      return (x * x);
>>> }
>>>
>>> SQR() is a computer function which computes a specific mathematical
>>> function, but it is *not* that mathematical function.
>>>
>>> The halting function is simply a set of pairs of the form ((M, I), S)
>>> where M is a Turing Machine, I is an input, and S is the halting
>>> status of that machine. Somewhere in that set will be the pair ((P,
>>> P), true) since the independent computation P(P) halts.
>>>
>>> Note that here it is meaningless to talk about things like
>>> 'pathological self-reference' since there are no instructions being
>>> performed here. There is simply a mapping. What you call
>>> 'pathological self-reference' only arises when you actually try to
>>> construct an algorithm for determining that (P, P) maps to true.
>>>
>>
>> No. Not at all. The mapping of PSR to a digraph has cycles.
>
> Reread what I wrote. The halting *function* is simply a set of pairs.
> How can an ordered pair such as ((P, P), true) contain a cycle?
>
>>> And that is why the halting function is not a *computable* function.
>>> It is not possible to construct a TM which, for *every* element of
>>> the halting function can determine what the second member of the pair
>>> is based on the first.
>>>
>>> And, as I have said, the halting function exists INDEPENDENTLY of any
>>> particular decider. The set { ....((P,P), true)... } is simply 'out
>>> there' so to speak. A halt decider is an algorithm which must then be
>>> able to determine that the pair whose first member is (P, P) in that
>>> set has 'true' as its second member.
>>>
>>
>> That is not true when the input is based on invoking a specifc decider.
>
> But the halting *function* doesn't involve any decider. It is simply a
> mapping from computations to their halting status.
>
> Again, reread what I wrote. Mathematical functions don't involve
> "invoking" anything. They are simply mappings, i.e. sets of ordered pairs.
>
> The job of a halt *decider* is to compute the mappings contained in that
> function.
>

a decider always maps finite strings to accept reject states.

You keep simply ignoring the fact the an input with pathological
self-reference has different behavior than one that does not.
You keep trytng to simply assume away verified facts.

>> The mapping to a digraph contains cycles that do not exist for other
>> inputs.
>>> Linz demonstrates that this isn't possible. *YOU'VE* demonstrated
>>> that this isn't possible but you keep trying to change the rules of
>>> the game so you can maintain that your 'decider' is somehow getting
>>> the right answer when it is not. A halt decider must compute the
>>> halting function as described above.
>>>
>>
>>
>> Computable functions are the basic objects of study in computability
>> theory. Computable functions are the formalized analogue of the
>> intuitive notion of algorithms,
>
> No, they are not. A computable function is a function for which it is
> *possible* to construct an algorithm. But a computable function is *not*
> an algorithm. It is simply a set of ordered pairs.
>
> Once again, I ask, why is it that when people attempt to correct you on
> your misuse of terminology you insist on doubling down rather than
> carefully reading what is said to try to understand the distinction
> between terms that is being brought to your attention?
>
> André
>

On 2021-11-24 13:41, olcott wrote:
> On 11/24/2021 1:48 PM, André G. Isaak wrote:
>> On 2021-11-24 12:36, olcott wrote:
>>> On 11/24/2021 1:19 PM, André G. Isaak wrote:

>> But the halting *function* doesn't involve any decider. It is simply a
>> mapping from computations to their halting status.
>>
>> Again, reread what I wrote. Mathematical functions don't involve
>> "invoking" anything. They are simply mappings, i.e. sets of ordered
>> pairs.
>>
>> The job of a halt *decider* is to compute the mappings contained in
>> that function.
>>
>
> a decider always maps finite strings to accept reject states.

Yes, it maps finite strings to accepting or rejecting states, but in
doing so it computes a *function*. I am asking you to think about what
that function is, not about the decider itself. The function is prior to
the decider.

Please explain how the ordered pair ((P, P), true) involves any sort of
reference, let alone 'pathological self reference'. That is the relevant
element of the halting *function* which your decider allegedly computes.

> You keep simply ignoring the fact the an input with pathological
> self-reference has different behavior than one that does not.
> You keep trytng to simply assume away verified facts.

Again, I am trying to get you to focus on the halting *function*, not on
your H. We can come back to your H once you demonstrate that you
understand what the distinction between the halting function and a halt
decider is, but you seem determined not to understand this.

>>> The mapping to a digraph contains cycles that do not exist for other
>>> inputs.
>>>> Linz demonstrates that this isn't possible. *YOU'VE* demonstrated
>>>> that this isn't possible but you keep trying to change the rules of
>>>> the game so you can maintain that your 'decider' is somehow getting
>>>> the right answer when it is not. A halt decider must compute the
>>>> halting function as described above.
>>>>
>>>
>>>
>>> Computable functions are the basic objects of study in computability
>>> theory. Computable functions are the formalized analogue of the
>>> intuitive notion of algorithms,
>>
>> No, they are not. A computable function is a function for which it is
>> *possible* to construct an algorithm. But a computable function is
>> *not* an algorithm. It is simply a set of ordered pairs.
>>
>> Once again, I ask, why is it that when people attempt to correct you
>> on your misuse of terminology you insist on doubling down rather than
>> carefully reading what is said to try to understand the distinction
>> between terms that is being brought to your attention?
>>
>> André
>>
>
> You are correcting an encyclopedia.
> deciders are a specific type of computable function that
> maps finite strings to accept reject states.

No. I am correcting you.

Deciders are a specific type of turing machine which *computes* a
computable function. Something which computes a function is not the same
thing as that function.

A function is a mapping.

A computation is an alogorithm.

A computable function is a function for which an algorithm exists for
computing that function.

A decider is related to some computable function. That doesn't make it a
computable function.

André

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

On 11/24/21 3:41 PM, olcott wrote:
> On 11/24/2021 1:48 PM, André G. Isaak wrote:
>> On 2021-11-24 12:36, olcott wrote:
>>> On 11/24/2021 1:19 PM, André G. Isaak wrote:
>>>> On 2021-11-24 11:22, olcott wrote:
>>>>> On 11/24/2021 12:06 PM, André G. Isaak wrote:
>>>>>> On 2021-11-24 10:49, olcott wrote:
>>>>>>> #include <stdint.h>
>>>>>>> #include <stdio.h>
>>>>>>> typedef int (*ptr)();
>>>>>>>
>>>>>>> int H(ptr x, ptr y)
>>>>>>> {
>>>>>>>    x(y); // direct execution of P(P)
>>>>>>>    return 1;
>>>>>>> }
>>>>>>>
>>>>>>> // Minimal essence of Linz(1990) Ĥ
>>>>>>> // and Strachey(1965) P
>>>>>>> int P(ptr x)
>>>>>>> {
>>>>>>>    H(x, x);
>>>>>>>    return 1; // Give P a last instruction at the "c" level
>>>>>>> }
>>>>>>>
>>>>>>> int main(void)
>>>>>>> {
>>>>>>>    H(P, P);
>>>>>>> }
>>>>>>>
>>>>>>> PSR set: It is self evident that when 0 to ∞ steps of the input
>>>>>>> to H(P,P) are directly executed or correctly simulated that the
>>>>>>> input to H(P,P) never reaches its final instruction.
>>>>>>>
>>>>>>> We can think of the combinations of (H,P) as an enumerated
>>>>>>> sequence of finite strings of C source-code. The above source
>>>>>>> code specifies the H0(P0,P0) first element of this sequence.
>>>>>>>
>>>>>>> Computation that halts
>>>>>>> a computation is said to halt whenever it enters a final state.
>>>>>>> (Linz:1990:234)
>>>>>>>
>>>>>>> PSR subset A: When Hn(Pn, Pn) executes or simulates a fixed
>>>>>>> number of N steps of its input this input still never reaches its
>>>>>>> last instruction and Hn(Pn, Pn) halts.
>>>>>>>
>>>>>>> PSR subset B: When Hn(Pn, Pn) executes or simulates a fixed
>>>>>>> number of N steps of its input this input still never reaches its
>>>>>>> last instruction and Hn(Pn, Pn) halts and Pn(Pn) called from
>>>>>>> main() halts.
>>>>>>>
>>>>>>> PSR subset C: For the subset of PSR subset A where Hn(Pn, Pn)
>>>>>>> returns 0 the returned halt status corresponds to the actual
>>>>>>> behavior of the input to Hn(Pn, Pn).
>>>>>>>
>>>>>>> PSR subset D: For the subset of PSR subset C where Hn(Pn, Pn)
>>>>>>> returns 0 on the basis that this input matches the infinite
>>>>>>> recursion behavior pattern. Hn(Pn, Pn) detects that its input is
>>>>>>> calling H again with the same input that it was called with. This
>>>>>>> makes Hn a correct halt decider of this input.
>>>>>>>
>>>>>>> H is a computable function that accepts or rejects inputs in its
>>>>>>> domain on the basis that these inputs specify a sequence of
>>>>>>> configurations that reach their final state.
>>>>>>
>>>>>> The H you've given above is a computer program, not a computable
>>>>>> function.
>>>>>
>>>>> Because H is a pure function it is a computable function.
>>>>> Adaptations to ensure this part took six months to find and are
>>>>> trivial one found.
>>>>
>>>> Why is it that every time someone attempts to correct your misuse of
>>>> terminology you double down? Despite the fact that you claim that
>>>> you are posting here so you can learn the 'correct terminology'.
>>>>
>>>> A "pure function" is a type of computer function.
>>>>
>>>> A computable function is a type of mathematical function.
>>>>
>>>> The term 'function' refers to different things in computer
>>>> programming and in math.
>>>>
>>>> Consider the function y = x². Here is a what the *mathematical*
>>>> function looks like:
>>>>
>>>> { (0, 0), (1, 1), (2, 4), (3, 9), (4, 16), (5, 25)... }
>>>>
>>>> A mathematical function is simply a mapping. It contains no
>>>> information about how the two members of each pair are related or
>>>> how to derive the second member of any given pair from the first. It
>>>> contains no instructions. The only requirement is that every member
>>>> of the domain occur as the first member of one and only one pair in
>>>> that set.
>>>>
>>>> For some, but not all, functions it is possible to construct an
>>>> algorithm which allows one to determine the second member of each
>>>> pair from the first. Those are functions that are computable functions.
>>>>
>>>> A computer function is the instantiation of an algorithm, and unlike
>>>> a mathematical computation includes a sequence of steps which allows
>>>> one to mechanically determine the value of the second member of a
>>>> pair from the first. For the above function, the C function might be
>>>> as follows:
>>>>
>>>> int SQR(int x) {
>>>>      return (x * x);
>>>> }
>>>>
>>>> SQR() is a computer function which computes a specific mathematical
>>>> function, but it is *not* that mathematical function.
>>>>
>>>> The halting function is simply a set of pairs of the form ((M, I),
>>>> S) where M is a Turing Machine, I is an input, and S is the halting
>>>> status of that machine. Somewhere in that set will be the pair ((P,
>>>> P), true) since the independent computation P(P) halts.
>>>>
>>>> Note that here it is meaningless to talk about things like
>>>> 'pathological self-reference' since there are no instructions being
>>>> performed here. There is simply a mapping. What you call
>>>> 'pathological self-reference' only arises when you actually try to
>>>> construct an algorithm for determining that (P, P) maps to true.
>>>>
>>>
>>> No. Not at all. The mapping of PSR to a digraph has cycles.
>>
>> Reread what I wrote. The halting *function* is simply a set of pairs.
>> How can an ordered pair such as ((P, P), true) contain a cycle?
>>
>>>> And that is why the halting function is not a *computable* function.
>>>> It is not possible to construct a TM which, for *every* element of
>>>> the halting function can determine what the second member of the
>>>> pair is based on the first.
>>>>
>>>> And, as I have said, the halting function exists INDEPENDENTLY of
>>>> any particular decider. The set { ....((P,P), true)... } is simply
>>>> 'out there' so to speak. A halt decider is an algorithm which must
>>>> then be able to determine that the pair whose first member is (P, P)
>>>> in that set has 'true' as its second member.
>>>>
>>>
>>> That is not true when the input is based on invoking a specifc decider.
>>
>> But the halting *function* doesn't involve any decider. It is simply a
>> mapping from computations to their halting status.
>>
>> Again, reread what I wrote. Mathematical functions don't involve
>> "invoking" anything. They are simply mappings, i.e. sets of ordered
>> pairs.
>>
>> The job of a halt *decider* is to compute the mappings contained in
>> that function.
>>
>
> a decider always maps finite strings to accept reject states.

Right, and the CORRECT answer is determined by the criteria that the
decider is required to follow.

I.E. a Correct Halt Decider answers based on the Halting of the
Computation that the input represents.

I.E. the correct answer for H(P,I) is based on the behavior of the
independent running of P(I).

On 11/24/2021 2:56 PM, André G. Isaak wrote:
> On 2021-11-24 13:41, olcott wrote:
>> On 11/24/2021 1:48 PM, André G. Isaak wrote:
>>> On 2021-11-24 12:36, olcott wrote:
>>>> On 11/24/2021 1:19 PM, André G. Isaak wrote:
>
>>> But the halting *function* doesn't involve any decider. It is simply
>>> a mapping from computations to their halting status.
>>>
>>> Again, reread what I wrote. Mathematical functions don't involve
>>> "invoking" anything. They are simply mappings, i.e. sets of ordered
>>> pairs.
>>>
>>> The job of a halt *decider* is to compute the mappings contained in
>>> that function.
>>>
>>
>> a decider always maps finite strings to accept reject states.
>
> Yes, it maps finite strings to accepting or rejecting states, but in
> doing so it computes a *function*. I am asking you to think about what
> that function is, not about the decider itself. The function is prior to
> the decider.
>

In the case of (P,P) it applies x86 emulation to a pair references to
the finite strings.

> Please explain how the ordered pair ((P, P), true) involves any sort of
> reference, let alone 'pathological self reference'. That is the relevant
> element of the halting *function* which your decider allegedly computes.
>

The execution trace has a cycle back to the same node in the directed
graph. x86 code has ready build digraphs of control flow.

>> You keep simply ignoring the fact the an input with pathological
>> self-reference has different behavior than one that does not.
>> You keep trytng to simply assume away verified facts.
>
> Again, I am trying to get you to focus on the halting *function*, not on
> your H. We can come back to your H once you demonstrate that you
> understand what the distinction between the halting function and a halt
> decider is, but you seem determined not to understand this.
>

Wikipedia and Linz define computable functions the same way that I do.
You told Wikipedia that it was wrong.

>>>> The mapping to a digraph contains cycles that do not exist for other
>>>> inputs.
>>>>> Linz demonstrates that this isn't possible. *YOU'VE* demonstrated
>>>>> that this isn't possible but you keep trying to change the rules of
>>>>> the game so you can maintain that your 'decider' is somehow getting
>>>>> the right answer when it is not. A halt decider must compute the
>>>>> halting function as described above.
>>>>>
>>>>
>>>>
>>>> Computable functions are the basic objects of study in computability
>>>> theory. Computable functions are the formalized analogue of the
>>>> intuitive notion of algorithms,
>>>
>>> No, they are not. A computable function is a function for which it is
>>> *possible* to construct an algorithm. But a computable function is
>>> *not* an algorithm. It is simply a set of ordered pairs.
>>>
>>> Once again, I ask, why is it that when people attempt to correct you
>>> on your misuse of terminology you insist on doubling down rather than
>>> carefully reading what is said to try to understand the distinction
>>> between terms that is being brought to your attention?
>>>
>>> André
>>>
>>
>> You are correcting an encyclopedia.
>> deciders are a specific type of computable function that
>> maps finite strings to accept reject states.
>
> No. I am correcting you.
>
> Deciders are a specific type of turing machine which *computes* a
> computable function. Something which computes a function is not the same
> thing as that function.
>
> A function is a mapping.
>
> A computation is an alogorithm.
>
> A computable function is a function for which an algorithm exists for
> computing that function.
>
> A decider is related to some computable function. That doesn't make it a
> computable function.
>

Deciders are a subset of computable functions.

> André
>

--
Copyright 2021 Pete Olcott

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

On 11/24/2021 2:56 PM, André G. Isaak wrote:
> On 2021-11-24 13:41, olcott wrote:
>> On 11/24/2021 1:48 PM, André G. Isaak wrote:
>>> On 2021-11-24 12:36, olcott wrote:
>>>> On 11/24/2021 1:19 PM, André G. Isaak wrote:
>
>>> But the halting *function* doesn't involve any decider. It is simply
>>> a mapping from computations to their halting status.
>>>
>>> Again, reread what I wrote. Mathematical functions don't involve
>>> "invoking" anything. They are simply mappings, i.e. sets of ordered
>>> pairs.
>>>
>>> The job of a halt *decider* is to compute the mappings contained in
>>> that function.
>>>
>>
>> a decider always maps finite strings to accept reject states.
>
> Yes, it maps finite strings to accepting or rejecting states, but in
> doing so it computes a *function*. I am asking you to think about what
> that function is, not about the decider itself. The function is prior to
> the decider.
>

In the case of (P,P) it applies x86 emulation to a pair references to
the finite strings.

> Please explain how the ordered pair ((P, P), true) involves any sort of
> reference, let alone 'pathological self reference'. That is the relevant
> element of the halting *function* which your decider allegedly computes.
>

The execution trace has a cycle back to the same node in the directed
graph. x86 code has ready build digraphs of control flow.

>> You keep simply ignoring the fact the an input with pathological
>> self-reference has different behavior than one that does not.
>> You keep trytng to simply assume away verified facts.
>
> Again, I am trying to get you to focus on the halting *function*, not on
> your H. We can come back to your H once you demonstrate that you
> understand what the distinction between the halting function and a halt
> decider is, but you seem determined not to understand this.
>

Wikipedia and Linz define computable functions the same way that I do.
You told Wikipedia that it was wrong.

>>>> The mapping to a digraph contains cycles that do not exist for other
>>>> inputs.
>>>>> Linz demonstrates that this isn't possible. *YOU'VE* demonstrated
>>>>> that this isn't possible but you keep trying to change the rules of
>>>>> the game so you can maintain that your 'decider' is somehow getting
>>>>> the right answer when it is not. A halt decider must compute the
>>>>> halting function as described above.
>>>>>
>>>>
>>>>
>>>> Computable functions are the basic objects of study in computability
>>>> theory. Computable functions are the formalized analogue of the
>>>> intuitive notion of algorithms,
>>>
>>> No, they are not. A computable function is a function for which it is
>>> *possible* to construct an algorithm. But a computable function is
>>> *not* an algorithm. It is simply a set of ordered pairs.
>>>
>>> Once again, I ask, why is it that when people attempt to correct you
>>> on your misuse of terminology you insist on doubling down rather than
>>> carefully reading what is said to try to understand the distinction
>>> between terms that is being brought to your attention?
>>>
>>> André
>>>
>>
>> You are correcting an encyclopedia.
>> deciders are a specific type of computable function that
>> maps finite strings to accept reject states.
>
> No. I am correcting you.
>
> Deciders are a specific type of turing machine which *computes* a
> computable function. Something which computes a function is not the same
> thing as that function.
>
> A function is a mapping.
>
> A computation is an alogorithm.
>
> A computable function is a function for which an algorithm exists for
> computing that function.
>
> A decider is related to some computable function. That doesn't make it a
> computable function.
>

Deciders are a subset of computable functions.

> André
>

--
Copyright 2021 Pete Olcott

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

On 11/24/21 4:58 PM, olcott wrote:
> On 11/24/2021 2:56 PM, André G. Isaak wrote:
>> On 2021-11-24 13:41, olcott wrote:
>>> On 11/24/2021 1:48 PM, André G. Isaak wrote:
>>>> On 2021-11-24 12:36, olcott wrote:
>>>>> On 11/24/2021 1:19 PM, André G. Isaak wrote:
>>
>>>> But the halting *function* doesn't involve any decider. It is simply
>>>> a mapping from computations to their halting status.
>>>>
>>>> Again, reread what I wrote. Mathematical functions don't involve
>>>> "invoking" anything. They are simply mappings, i.e. sets of ordered
>>>> pairs.
>>>>
>>>> The job of a halt *decider* is to compute the mappings contained in
>>>> that function.
>>>>
>>>
>>> a decider always maps finite strings to accept reject states.
>>
>> Yes, it maps finite strings to accepting or rejecting states, but in
>> doing so it computes a *function*. I am asking you to think about what
>> that function is, not about the decider itself. The function is prior
>> to the decider.
>>
>
> In the case of (P,P) it applies x86 emulation to a pair references to
> the finite strings.

Right, you are going to attempt to figure it out by emulating the x86
code of the representatoin.

>
>> Please explain how the ordered pair ((P, P), true) involves any sort
>> of reference, let alone 'pathological self reference'. That is the
>> relevant element of the halting *function* which your decider
>> allegedly computes.
>>
>
> The execution trace has a cycle back to the same node in the directed
> graph. x86 code has ready build digraphs of control flow.

The EXECUTION trace has cycles, the REPRESENTATION does not.

The mapping is of the REPRESENTATION, so the map has no cycles.

>
>>> You keep simply ignoring the fact the an input with pathological
>>> self-reference has different behavior than one that does not.
>>> You keep trytng to simply assume away verified facts.
>>
>> Again, I am trying to get you to focus on the halting *function*, not
>> on your H. We can come back to your H once you demonstrate that you
>> understand what the distinction between the halting function and a
>> halt decider is, but you seem determined not to understand this.
>>
>
> Wikipedia and Linz define computable functions the same way that I do.
> You told Wikipedia that it was wrong.

You don't seem to understand the words, do you.

the Computable Function is the MAPPING, there is no 'code' as part of
the mapping.

We get to add the modifier COMPUTABLE if the also exists some algorithm
that can be used to compute this mapping,

That computation is NOT 'the mapping' but a method to compute what the
output would be from the input.

>
>>>>> The mapping to a digraph contains cycles that do not exist for
>>>>> other inputs.
>>>>>> Linz demonstrates that this isn't possible. *YOU'VE* demonstrated
>>>>>> that this isn't possible but you keep trying to change the rules
>>>>>> of the game so you can maintain that your 'decider' is somehow
>>>>>> getting the right answer when it is not. A halt decider must
>>>>>> compute the halting function as described above.
>>>>>>
>>>>>
>>>>>
>>>>> Computable functions are the basic objects of study in
>>>>> computability theory. Computable functions are the formalized
>>>>> analogue of the intuitive notion of algorithms,
>>>>
>>>> No, they are not. A computable function is a function for which it
>>>> is *possible* to construct an algorithm. But a computable function
>>>> is *not* an algorithm. It is simply a set of ordered pairs.
>>>>
>>>> Once again, I ask, why is it that when people attempt to correct you
>>>> on your misuse of terminology you insist on doubling down rather
>>>> than carefully reading what is said to try to understand the
>>>> distinction between terms that is being brought to your attention?
>>>>
>>>> André
>>>>
>>>
>>> You are correcting an encyclopedia.
>>> deciders are a specific type of computable function that
>>> maps finite strings to accept reject states.
>>
>> No. I am correcting you.
>>
>> Deciders are a specific type of turing machine which *computes* a
>> computable function. Something which computes a function is not the
>> same thing as that function.
>>
>> A function is a mapping.
>>
>> A computation is an alogorithm.
>>
>> A computable function is a function for which an algorithm exists for
>> computing that function.
>>
>> A decider is related to some computable function. That doesn't make it
>> a computable function.
>>
>
> Deciders are a subset of computable functions.

LIE, CATEGORY ERROR

Deciders are Algorithms/Turing Machines.

Computable Functions are Mappings.

There is a relationship between them, but is itsn't an IS-A relationship.

If we have a Computable Function, that says that there exist a algorithm
that can compute it. That algorithm might be a decider. The decider (or
algorithm) is NOT the mapping, it is a way to compute it.

You are just showing of your ignorance.

>
>> André
>>
>
>

On 11/24/2021 2:56 PM, André G. Isaak wrote:
> On 2021-11-24 13:41, olcott wrote:
>> On 11/24/2021 1:48 PM, André G. Isaak wrote:
>>> On 2021-11-24 12:36, olcott wrote:
>>>> On 11/24/2021 1:19 PM, André G. Isaak wrote:
>
>>> But the halting *function* doesn't involve any decider. It is simply
>>> a mapping from computations to their halting status.
>>>
>>> Again, reread what I wrote. Mathematical functions don't involve
>>> "invoking" anything. They are simply mappings, i.e. sets of ordered
>>> pairs.
>>>
>>> The job of a halt *decider* is to compute the mappings contained in
>>> that function.
>>>
>>
>> a decider always maps finite strings to accept reject states.
>
> Yes, it maps finite strings to accepting or rejecting states, but in
> doing so it computes a *function*. I am asking you to think about what
> that function is, not about the decider itself. The function is prior to
> the decider.
>
> Please explain how the ordered pair ((P, P), true) involves any sort of
> reference, let alone 'pathological self reference'. That is the relevant
> element of the halting *function* which your decider allegedly computes.
>
>> You keep simply ignoring the fact the an input with pathological
>> self-reference has different behavior than one that does not.
>> You keep trytng to simply assume away verified facts.
>
> Again, I am trying to get you to focus on the halting *function*, not on
> your H. We can come back to your H once you demonstrate that you
> understand what the distinction between the halting function and a halt
> decider is, but you seem determined not to understand this.
>
>>>> The mapping to a digraph contains cycles that do not exist for other
>>>> inputs.
>>>>> Linz demonstrates that this isn't possible. *YOU'VE* demonstrated
>>>>> that this isn't possible but you keep trying to change the rules of
>>>>> the game so you can maintain that your 'decider' is somehow getting
>>>>> the right answer when it is not. A halt decider must compute the
>>>>> halting function as described above.
>>>>>
>>>>
>>>>
>>>> Computable functions are the basic objects of study in computability
>>>> theory. Computable functions are the formalized analogue of the
>>>> intuitive notion of algorithms,
>>>
>>> No, they are not. A computable function is a function for which it is
>>> *possible* to construct an algorithm. But a computable function is
>>> *not* an algorithm. It is simply a set of ordered pairs.
>>>
>>> Once again, I ask, why is it that when people attempt to correct you
>>> on your misuse of terminology you insist on doubling down rather than
>>> carefully reading what is said to try to understand the distinction
>>> between terms that is being brought to your attention?
>>>
>>> André
>>>
>>
>> You are correcting an encyclopedia.
>> deciders are a specific type of computable function that
>> maps finite strings to accept reject states.
>
> No. I am correcting you.
>
> Deciders are a specific type of turing machine which *computes* a
> computable function. Something which computes a function is not the same
> thing as that function.
>
> A function is a mapping.
>
> A computation is an alogorithm.
>
> A computable function is a function for which an algorithm exists for
> computing that function.
>
> A decider is related to some computable function. That doesn't make it a
> computable function.
>
> André
>

The sequence of 1 to N configurations specified by the input to H(X, Y)
cannot be correctly construed as anything other than the sequence of 1
to N steps of the (direct execution, x86 emulation or UTM simulation of
this input).

--
Copyright 2021 Pete Olcott

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

On 2021-11-24 14:57, olcott wrote:
> On 11/24/2021 2:56 PM, André G. Isaak wrote:
>> On 2021-11-24 13:41, olcott wrote:
>>> On 11/24/2021 1:48 PM, André G. Isaak wrote:
>>>> On 2021-11-24 12:36, olcott wrote:
>>>>> On 11/24/2021 1:19 PM, André G. Isaak wrote:
>>
>>>> But the halting *function* doesn't involve any decider. It is simply
>>>> a mapping from computations to their halting status.
>>>>
>>>> Again, reread what I wrote. Mathematical functions don't involve
>>>> "invoking" anything. They are simply mappings, i.e. sets of ordered
>>>> pairs.
>>>>
>>>> The job of a halt *decider* is to compute the mappings contained in
>>>> that function.
>>>>
>>>
>>> a decider always maps finite strings to accept reject states.
>>
>> Yes, it maps finite strings to accepting or rejecting states, but in
>> doing so it computes a *function*. I am asking you to think about what
>> that function is, not about the decider itself. The function is prior
>> to the decider.
>>
>
> In the case of (P,P) it applies x86 emulation to a pair references to
> the finite strings.

That's not a *function*, it's a computer program. I'm asking you to
think about the mathematical halting function.

>> Please explain how the ordered pair ((P, P), true) involves any sort
>> of reference, let alone 'pathological self reference'. That is the
>> relevant element of the halting *function* which your decider
>> allegedly computes.
>>
>
> The execution trace has a cycle back to the same node in the directed
> graph. x86 code has ready build digraphs of control flow.

Again, I'm asking you to think about the mathematical halting function.
Mathematical functions are *mappings*. They don't have traces. Reread my
description of the halting function.

>>> You keep simply ignoring the fact the an input with pathological
>>> self-reference has different behavior than one that does not.
>>> You keep trytng to simply assume away verified facts.
>>
>> Again, I am trying to get you to focus on the halting *function*, not
>> on your H. We can come back to your H once you demonstrate that you
>> understand what the distinction between the halting function and a
>> halt decider is, but you seem determined not to understand this.
>>
>
> Wikipedia and Linz define computable functions the same way that I do.
> You told Wikipedia that it was wrong.

No they don't.

Here is a direct quote from the wikipedia article your cited:

"Computable functions are the formalized analogue of the intuitive
notion of algorithms,"

please pay special attention to the word ANALOGUE in the above. If X is
an analogue of Y, that implies that X != Y.

"in the sense that a function is computable if there exists an algorithm
that can do the job of the function, i.e. given an input of the function
domain it can return the corresponding output"

The above clearly distinguishes between the FUNCTION and the ALGORITHM.
The algorithm != the function. The algorithm is what *computes* the
function.

A Turing Machine is not a function, it is the instantiation of an
algorithm which computes a computable function.

A computable function is not an algorithm. It is a mapping for which
there exists some algorithm capable of computing it.

André

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

On 11/24/21 5:25 PM, olcott wrote:
> On 11/24/2021 2:56 PM, André G. Isaak wrote:
>> On 2021-11-24 13:41, olcott wrote:
>>> On 11/24/2021 1:48 PM, André G. Isaak wrote:
>>>> On 2021-11-24 12:36, olcott wrote:
>>>>> On 11/24/2021 1:19 PM, André G. Isaak wrote:
>>
>>>> But the halting *function* doesn't involve any decider. It is simply
>>>> a mapping from computations to their halting status.
>>>>
>>>> Again, reread what I wrote. Mathematical functions don't involve
>>>> "invoking" anything. They are simply mappings, i.e. sets of ordered
>>>> pairs.
>>>>
>>>> The job of a halt *decider* is to compute the mappings contained in
>>>> that function.
>>>>
>>>
>>> a decider always maps finite strings to accept reject states.
>>
>> Yes, it maps finite strings to accepting or rejecting states, but in
>> doing so it computes a *function*. I am asking you to think about what
>> that function is, not about the decider itself. The function is prior
>> to the decider.
>>
>> Please explain how the ordered pair ((P, P), true) involves any sort
>> of reference, let alone 'pathological self reference'. That is the
>> relevant element of the halting *function* which your decider
>> allegedly computes.
>>
>>> You keep simply ignoring the fact the an input with pathological
>>> self-reference has different behavior than one that does not.
>>> You keep trytng to simply assume away verified facts.
>>
>> Again, I am trying to get you to focus on the halting *function*, not
>> on your H. We can come back to your H once you demonstrate that you
>> understand what the distinction between the halting function and a
>> halt decider is, but you seem determined not to understand this.
>>
>>>>> The mapping to a digraph contains cycles that do not exist for
>>>>> other inputs.
>>>>>> Linz demonstrates that this isn't possible. *YOU'VE* demonstrated
>>>>>> that this isn't possible but you keep trying to change the rules
>>>>>> of the game so you can maintain that your 'decider' is somehow
>>>>>> getting the right answer when it is not. A halt decider must
>>>>>> compute the halting function as described above.
>>>>>>
>>>>>
>>>>>
>>>>> Computable functions are the basic objects of study in
>>>>> computability theory. Computable functions are the formalized
>>>>> analogue of the intuitive notion of algorithms,
>>>>
>>>> No, they are not. A computable function is a function for which it
>>>> is *possible* to construct an algorithm. But a computable function
>>>> is *not* an algorithm. It is simply a set of ordered pairs.
>>>>
>>>> Once again, I ask, why is it that when people attempt to correct you
>>>> on your misuse of terminology you insist on doubling down rather
>>>> than carefully reading what is said to try to understand the
>>>> distinction between terms that is being brought to your attention?
>>>>
>>>> André
>>>>
>>>
>>> You are correcting an encyclopedia.
>>> deciders are a specific type of computable function that
>>> maps finite strings to accept reject states.
>>
>> No. I am correcting you.
>>
>> Deciders are a specific type of turing machine which *computes* a
>> computable function. Something which computes a function is not the
>> same thing as that function.
>>
>> A function is a mapping.
>>
>> A computation is an alogorithm.
>>
>> A computable function is a function for which an algorithm exists for
>> computing that function.
>>
>> A decider is related to some computable function. That doesn't make it
>> a computable function.
>>
>> André
>>
>
> The sequence of 1 to N configurations specified by the input to H(X, Y)
> cannot be correctly construed as anything other than the sequence of 1
> to N steps of the (direct execution, x86 emulation or UTM simulation of
> this input).
>

Ok, so what does it prove? Only that maybe the input X(Y) doesn't halt
in just N steps, but might in some number over N or it might never.

Thus, a trace aborted after just N steps doesn't actually show anything
useful (unless of course, it didn't need to abort becuase is halted in
less than N steps).

We DO know that if H(P,P) returns 0, then P(P) will Halt, and thus H was
wrong.

If H traced for N steps before aborting, when we look at P(P) it will
halt in some N+k steps, where k is finite positive integer.

k is basically the sum of the steps needed to get to the invokation of
the copy of H, plus and steps needed after that copy of H returns until
we stop.

For the code you have shown, it is about 8 x86 instructions.

On 11/24/2021 4:28 PM, André G. Isaak wrote:
> On 2021-11-24 14:57, olcott wrote:
>> On 11/24/2021 2:56 PM, André G. Isaak wrote:
>>> On 2021-11-24 13:41, olcott wrote:
>>>> On 11/24/2021 1:48 PM, André G. Isaak wrote:
>>>>> On 2021-11-24 12:36, olcott wrote:
>>>>>> On 11/24/2021 1:19 PM, André G. Isaak wrote:
>>>
>>>>> But the halting *function* doesn't involve any decider. It is
>>>>> simply a mapping from computations to their halting status.
>>>>>
>>>>> Again, reread what I wrote. Mathematical functions don't involve
>>>>> "invoking" anything. They are simply mappings, i.e. sets of ordered
>>>>> pairs.
>>>>>
>>>>> The job of a halt *decider* is to compute the mappings contained in
>>>>> that function.
>>>>>
>>>>
>>>> a decider always maps finite strings to accept reject states.
>>>
>>> Yes, it maps finite strings to accepting or rejecting states, but in
>>> doing so it computes a *function*. I am asking you to think about
>>> what that function is, not about the decider itself. The function is
>>> prior to the decider.
>>>
>>
>> In the case of (P,P) it applies x86 emulation to a pair references to
>> the finite strings.
>
> That's not a *function*, it's a computer program. I'm asking you to
> think about the mathematical halting function.
>
>>> Please explain how the ordered pair ((P, P), true) involves any sort
>>> of reference, let alone 'pathological self reference'. That is the
>>> relevant element of the halting *function* which your decider
>>> allegedly computes.
>>>
>>
>> The execution trace has a cycle back to the same node in the directed
>> graph. x86 code has ready build digraphs of control flow.
>
> Again, I'm asking you to think about the mathematical halting function.
> Mathematical functions are *mappings*. They don't have traces. Reread my
> description of the halting function.
>
>>>> You keep simply ignoring the fact the an input with pathological
>>>> self-reference has different behavior than one that does not.
>>>> You keep trytng to simply assume away verified facts.
>>>
>>> Again, I am trying to get you to focus on the halting *function*, not
>>> on your H. We can come back to your H once you demonstrate that you
>>> understand what the distinction between the halting function and a
>>> halt decider is, but you seem determined not to understand this.
>>>
>>
>> Wikipedia and Linz define computable functions the same way that I do.
>> You told Wikipedia that it was wrong.
>
> No they don't.
>
> Here is a direct quote from the wikipedia article your cited:
>
> "Computable functions are the formalized analogue of the intuitive
> notion of algorithms,"
>
> please pay special attention to the word ANALOGUE in the above. If X is
> an analogue of Y, that implies that X != Y.
>
> "in the sense that a function is computable if there exists an algorithm
> that can do the job of the function, i.e. given an input of the function
> domain it can return the corresponding output"
>
> The above clearly distinguishes between the FUNCTION and the ALGORITHM.
> The algorithm != the function. The algorithm is what *computes* the
> function.
>
> A Turing Machine is not a function, it is the instantiation of an
> algorithm which computes a computable function.
>
> A computable function is not an algorithm. It is a mapping for which
> there exists some algorithm capable of computing it.
>
> André
>

The sequence of 1 to N configurations specified by the input to H(X, Y)
cannot be correctly construed as anything other than the sequence of 1
to N steps of the (direct execution, x86 emulation or UTM simulation of
this input).

When H actually directly executes 1 to N steps of its actual input this
conclusively proves that this is the actual direct execution of 1 to N
steps of its input.

--
Copyright 2021 Pete Olcott

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

On 11/24/21 7:05 PM, olcott wrote:

> The sequence of 1 to N configurations specified by the input to H(X, Y)
> cannot be correctly construed as anything other than the sequence of 1
> to N steps of the (direct execution, x86 emulation or UTM simulation of
> this input).
>
> When H actually directly executes 1 to N steps of its actual input this
> conclusively proves that this is the actual direct execution of 1 to N
> steps of its input.
>

First point: Showing a machine doesn't stop in N steps doesn't mean it
goes on forever. Non-Halting means showing that it will NEVER halt,
after an unlimited number of steps.

Second Point: To be actual direct execution means that it needs to trace
through the copy of H that starts to trace through the copy of P(P) that
it was given, as THAT is what actually happens. Since we KNOW that this
H will abort its simulation in N steps, the code that manages that needs
to show in the trace.

This points out that we KNOW that P(P) will not execute forever as it
calls H(P,P) which if H is defined to only execute N steps, we know this
call will return in no more than N steps, so CAN'T create an infinite
recursion.

You implied induction arguement fails as each Hn/Pn pair is brand new
machine, so we can't induce from one to another.