#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

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