On 2021-11-23 18:53, olcott wrote:
On 11/23/2021 7:34 PM, André G. Isaak wrote:
Crucially, the halting function exists *independently* and *prior* to
any Turing Machine which attempts to compute this function. The halting function is *not* associated with any sort of algorithm; it is simply a mapping. In other words it is simply a denumerably infinite list of all possible computations and their halting status expressed as ordered pairs.
The computation P(P) will occur in this list exactly once, as will be
true for all other computation. Since your P(P) halts, it will map to 'halts'.
A halt decider, given <P> <P> as its input, is tasked with determining
what the entry for that computation in the list described above actually
is in a finite number of steps. If <P> <P> maps to 'halts' in the
halting function, then a halt decider must accept it. If it maps to
'doesn't halt', it must reject it.
That means that the halting value of P(P) is *not* specific to a given
halt decider. Your H and H1 must both provide the same answer if they
are both halt deciders. It means that it is non-sensical to talk about
the halting value of P(P) 'inside' some H, since H's job is to determine
what value this computation maps to in the halting FUNCTION which is independent of any halt decider.
André
On 2021-11-24 08:02, olcott wrote:
On 11/24/2021 12:27 AM, André G. Isaak wrote:
On 2021-11-23 22:48, olcott wrote:
On 11/23/2021 10:18 PM, André G. Isaak wrote:
On 2021-11-23 21:03, olcott wrote:
On 11/23/2021 9:44 PM, André G. Isaak wrote:
On 2021-11-23 20:24, olcott wrote:
On 11/23/2021 8:22 PM, André G. Isaak wrote:
On 2021-11-23 18:53, olcott wrote:
On 11/23/2021 7:34 PM, André G. Isaak wrote:
Crucially, the halting function exists *independently* and
*prior* to any Turing Machine which attempts to compute this >>>>>>>>> function. The halting function is *not* associated with any
sort of algorithm; it is simply a mapping. In other words it is >>>>>>>>> simply a denumerably infinite list of all possible computations >>>>>>>>> and their halting status expressed as ordered pairs.
You don't realize it but you are asking a decider to make its
decision on the basis of a hypothetical string that does not
actually exist.
???
So now you claim the STRING <P> <P> can't exist? But at the same >>>>>>> time you claim that your H1 returns the correct answer for this
allegedly impossible string? How on earth does that work.
int H(ptr x, ptr y) { x(y); }
int H1(ptr x, ptr y) { x(y); int P(ptr x) { H(x, x); }
int P1(ptr x) { H1(x, x); }
What does any of this have to do with your ridiculous claim that
the string <P> <P> does not actually exist?
If you want the actual behavior of P(P) run independently
then you have to change P or H into something that they are not
because they are defined with hardwired inter-dependency.
If you want the actual behaviour of P(P) run independently, you
simply run P(P) independently.
So in other words H must report on the behavior of a finite string
that is not is input.
H doesn't report on the behaviour of finite strings at all. It reports
on the behaviour of computations.
P(P) is a computation which halts.
Your H needs to be able to report that P(P) halts (or any other
arbitrary computation).
Determining exactly how that particular computation must be encoded as a finite string so it can be passed as an input to H is part of your job
when designing H.
Maybe you don't grasp this. Consider two UTMs, X and Y (and by UTM I
mean actual UTMs). Both of these should be able to emulate P(P) if we
give them two copies of a string which describes the Turing Machine P.
But the strings we pass to X and the string we pass to Y are *not* necessarily the same string. X and Y may use different alphabets and may
use different encoding schemes. To constitute a UTM, it must be the
case, though, that it is possible to represent every possible
computation as a string that can be passed to that UTM.
If you've designed an H such that there is no possible way to represent
the independent computation P(P) as a string which can be passed to H as
an input, then there is something wrong with your design.
I think what you mean to say is if you want H to give you the correct
answer about the actual behaviour of P(P) run independently, which it
can't. The interdependency prevents this.
It is incorrect to think of H having the hypothetical input where P
does not call H.All deciders must have finite string inputs. Because P
foes
Where did I (or anyone) mention a P that does not simulate/call H?
H is required to describe the halting behaviour of the independent computation P(P). That means it must describe how P(P) behaves when
called directly from main rather than from within your halt decider.
call this same H changing P so that it does not call this same H is
incorrect.
It is equally incorrect to have H report on the behavior of P as if H
was H1 where P does not call H1.
But that does not change the fact that the computation P(P) halts, and
The fact there there are no cats in the kitchen does not have one damn
thing to do with dogs in the living room. I can't imagine how people
can so persistently make this strawman error even after being warned
dozens of times.
#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);
}
Combinations of (H,P) having pathological self-reference (PSR)
H(P,P) simulates or executes its input and aborts or does
not abort its input and P(P) calls this same H(P,P) with itself.
for all Hn(Pn,Pn) in the above PSR set Pn never reaches its final
instruction.
that this therefore is the only correct answer to the question which
a halt decider is required to answer.
That is not the freaking way that deciders work.
A decider accepts or rejects all possible inputs based on some criteria determined by the problem at hand.
For the halting problem, the criterion is that the decider must accept
all and only those independent computations which HALT.
If H(P,P) reports on the behavior of H1(P,P) or H(P1,P1) it freaking
answered the wrong freaking question.
Those are the only pair of combinations that show P(P) as an
independent computation and they are both answers to the wrong question.
NEITHER of those show P(P) as an independent computation.
H(P,P) must report on the behaviour of P(P). That's the *only* behaviour
it is being asked about.
The one key verified fact that everyone simply assumes away even
though it is a verified fact is that there are elements of the PSR set
such that the input to Hn(Pn,Pn) never reaches its final state and
Pn(Pn) does reach its final state in this exact same sequence of
configurations.
People assume that the placement in the execution trace can't make a
difference and yet it is a verified fact that this placement does make
a difference. The one way dependency relationship that Pn(Pn) has on
Hn(Pn,Pn) causes the outer Pn to behave differently than the inner Pn.
Simply assuming this away is flat out dishonest.
None of this is relevant (or even coherent). H(P, P) by the definition
of the problem must report the behaviour of the independent computation
P(P). Whether the "placement in the execution trace can make a
difference" has no bearing on the behaviour of P(P). It might have some bearing on the behaviour of the simulation of P(P) inside of H, but
that's not what the halt decider is being asked about.
| Sysop: | Keyop |
|---|---|
| Location: | Huddersfield, West Yorkshire, UK |
| Users: | 293 |
| Nodes: | 16 (2 / 14) |
| Uptime: | 216:46:07 |
| Calls: | 6,621 |
| Calls today: | 3 |
| Files: | 12,169 |
| Messages: | 5,317,616 |