XPost: comp.theory, sci.logic, sci.math
On 11/25/2021 6:46 PM, André G. Isaak wrote:
On 2021-11-25 16:56, olcott wrote:
On 11/25/2021 2:00 PM, André G. Isaak wrote:
On 2021-11-25 12:29, 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);
}
The above program is obviously infinitely recursive. 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.
PSR set (pathological self-reference)
H1(P1,P1) Is the above code.
H2(P2,P2) Is the above code where H2 simulates rather than directly
executes its input.
H3(P3,P3) Is the execution of N steps of the input of H1(P1,P1).
H4(P4,P4) Is the simulation of N steps of the input of H2(P2,P2).
<rewrite>
Every Hn(Px,Py) that returns a value returns 1 except for instances
of {H3, H4} that determine whether or not to return {0,1} on the
basis of the behavior of their input.
</rewrite>
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 by H.
When H directly executes 1 to N steps of its actual input this
conclusively proves that this is the correct direct execution basis
for the halt decider's halt status decision. The simulation of this
same input derives the exact same sequence of steps.
The point in the sequence of 1 to N steps where the execution trace
of the simulation of P shows that P is about to call H(P,P) again
with the same input that H was called with provides conclusive proof
that P would be infinitely recursive unless H aborted its simulation.
When P(P) calls H(P,P) reaches the above point in its simulation it
returns 0 to P.
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.
You seem determined not to learn.
H is a computer program, *not* a computable function.
If it is a halt decider, it computes the halting function.
If it is a decider then if maps finite strings to accept / reject states.
Yes, and in doing so it computes the halting function.
The domain of the halting function is the set of all computations.
This is too abstract and you know it.
A halt decider maps finite string pairs to accept / reject states.
And those strings consist of descriptions of a computation,
appropriately encoded for your particular halt decider.
Therefore, the domain of H is the same, appropriately encoded as
strings.
P(P) is a computation, therefore it is in the domain of H.
P(P) halts, therefore H(P, P) must return true.
You keep insisting on a leap of logic. For H(x,y) the pair of finite
strings (x,y) must be transformed into a sequence of configurations by
a specific algorithm.
No, it doesn't. That's the implementational path you've chosen to take,
but the problem doesn't specify this.
Simply saying that this is whatever sequence is specified by the
direct execution of P(P) is too vague.
There's nothing vague about this at all.
The input to H(x,y) is transformed into a sequence of configurations
by the (direct execution, x86 emulation or UTM simulation) of this
(x,y) input by H.
You are extremely confused here. You keep referring to
*implementational* details of your H as if they were somehow part of the halting problem.
The halting problem is defined as follows. Note this is a definition, so
it isn't open to debate.
A halt decider H is a turing machine which decides for any arbitrary computation M(I) whether that computation will halt. In your
terminology, that means whether int main { M(I); } halts. [This last bit isn't usually specified since computations by definition are
*indendepent* entities and you are the only one who gets confused by this].
The input to H is a string which encodes M and a string which encodes I.
Note that nothing in the above statement of the problem mentions
anything about 'sequences of configurations' or the (direct execution,
x86 emulation or UTM simulation) of the input by H. These are *YOUR* additions which have nothing to do with the actual definition of the
problem.
computable function
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
an algorithm that can do the job of the function,
an algorithm that can do the job of the function,
an algorithm that can do the job of the function,
an algorithm that can do the job of the function,
given an input ... it can return the corresponding output.
given an input ... it can return the corresponding output.
given an input ... it can return the corresponding output.
given an input ... it can return the corresponding output.
Given a finite string pair (x,y) every configuration
from x.q0, x.q1, x.q2, x.qn ... x.final must be shown.
The actual TM description quintuple for each configuration must be
explicitly shown:
http://www.lns.mit.edu/~dsw/turing/examples/add10.tm
It is only vagueness that has kept the truth hidden for so many years.
I use x86 because it has zero vagueness.
If you can not specify a 100% perfectly precise algorithm that lists the
actual quintuple for x.q0, x.q1, x.q2, x.qn ... x.final for H(x,y)
you are only talking about vague abstractions.
When you say whatever it is that x(y) actually does
you are only talking about vague abstractions.
Since P(P) is a computation it must be possible to represent this as a concatenation of strings which can be passed to H as an input.
Since P(P) halts, H must return 1 for this particular input.
If your H cannot properly interpret the representation of P(P) as representing the *independent* computation P(P), then your
implementation fails to meet the definition of the problem.
If your H cannot properly determine that P(P) halts, then your
implementation fails to meet the definition of the problem.
The fact that your H is unable to meet these specifications doesn't
*change* what these specifications are. The problem is what it is. The definition of halt decider is what it is. You can't fiddle with these definitions just because you can't figure out how to solve the actual question specified by the problem.
The halting function is simply not computable, so you'll never be able
to create an H which actually gets all cases right.
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
--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)