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.
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é
On 2021-11-25 19:28, olcott wrote:
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.
Is there some reason why you are quoting the above, let alone quoting it
five times? Does it have something to do with something I said? If so,
what?
An algorithm computes a function. An algorithm is not the function it computes. A given function may have many different algorithms which can compute it. Or it might have none.
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
That's exactly what the input string describes: it encodes a Turing
Machine and an input string. It does *not* encode a 'sequence of configurations'. The TM description includes a *set* of quintuples representing state transitions. A set is *not* a sequence.
It is only vagueness that has kept the truth hidden for so many years.
I use x86 because it has zero vagueness.
Which 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.
Do you not understand the difference between a SPECIFICATION and an IMPLEMENTATION?
I have been giving you the specification of the halting problem, i.e. a description of *exactly* which problem a halt decider must solve. How
you go about solving it is the implementation.
The SPECIFICATION of the problem is that a halt decider takes as its
input a description of a computation and determines whether that
computation, when run independently, halts.
P(P) halts, so by the specification of the problem any halt decider
which is passed a string representing P(P) *must* return true as its
answer. Any "halt decider" which fails to do this fails to implement the specification.
All your nonsense about what P(P) does "inside H" is just that --
nonsense, because the specification clearly states that the decider must describe the behaviour of P(P) as an independent computation.
If you don't grasp the distinction between a specification and an implementation, read the C Standard. It describes the standard library functions and gives a *specification* of what each function must do. The actual implementation of these routines varies depending on your IDE and operating system.
Sysop: | Keyop |
---|---|
Location: | Huddersfield, West Yorkshire, UK |
Users: | 365 |
Nodes: | 16 (2 / 14) |
Uptime: | 63:49:53 |
Calls: | 7,774 |
Files: | 12,908 |
Messages: | 5,749,823 |