On Sunday, 19 September 2021 at 04:42:41 UTC+1, olcott wrote:
This is my paraphrase of the requirement a partialTo qualify as a decider, the halt decider must calculate a (mathematical) function.
halt decider must be a pure function of its inputs:
As long as there is one set of inputs such as such as the formal
parameters to a function and a single output such as return value of
{1,0} (indicating true or false) from this function, then whatever
occurs in-between does not make any difference.
This would mean that my use of static local variables has no detrimental
effect on the applicability of my partial halt decider to the halting
problem.
u32 H(u32 P, u32 I)
{
static u32 Aborted;
static u32* execution_trace;
That is, for each possible input, there must be one and only one output, that is always the same for each input.
How a piece of computer code achieves that is not important, and details vary from language to language. In some primitive languages (or high-level scripting
languages) it may not be possible to declare local variables, for instance.
On Saturday, September 18, 2021 at 11:42:41 PM UTC-4, olcott wrote:
This is my paraphrase of the requirement a partial
halt decider must be a pure function of its inputs:
As long as there is one set of inputs such as such as the formal
parameters to a function and a single output such as return value of
{1,0} (indicating true or false) from this function, then whatever
occurs in-between does not make any difference.
This would mean that my use of static local variables has no detrimental
effect on the applicability of my partial halt decider to the halting
problem.
u32 H(u32 P, u32 I)
{
static u32 Aborted;
static u32* execution_trace;
--
Copyright 2021 Pete Olcott
"Great spirits have always encountered violent opposition from mediocre
minds." Einstein
There is no significance to solving "some instances" of a problem. That includes no instances or trivial instances (here it would be YES answers) which have no significance.
It's basically impossible to carve out any non-trivial subsets of programs whose halting problem can be solved.
The easiest way to advance unsolvable problems (nonrecursive sets) has always been to find unsolved problems - proving sets are not recursive, typically r.e. sets.
C-B
On 2021-09-20 10:44, olcott wrote:
On 9/20/2021 11:15 AM, Charlie-Boo wrote:
On Saturday, September 18, 2021 at 11:42:41 PM UTC-4, olcott wrote:
This is my paraphrase of the requirement a partial
halt decider must be a pure function of its inputs:
As long as there is one set of inputs such as such as the formal
parameters to a function and a single output such as return value of
{1,0} (indicating true or false) from this function, then whatever
occurs in-between does not make any difference.
This would mean that my use of static local variables has no
detrimental
effect on the applicability of my partial halt decider to the halting
problem.
u32 H(u32 P, u32 I)
{
static u32 Aborted;
static u32* execution_trace;
--
Copyright 2021 Pete Olcott
"Great spirits have always encountered violent opposition from mediocre >>>> minds." Einstein
There is no significance to solving "some instances" of a problem.
That includes no instances or trivial instances (here it would be YES
answers) which have no significance.
It's basically impossible to carve out any non-trivial subsets of
programs whose halting problem can be solved.
The easiest way to advance unsolvable problems (nonrecursive sets)
has always been to find unsolved problems - proving sets are not
recursive, typically r.e. sets.
C-B
void P(u32 x)
{
if (H(x, x))
HERE: goto HERE;
}
int main()
{
Output("Input_Halts = ", H1((u32)P, (u32)P));
}
H and H1 are simulating partial halt deciders that make their halt
status decision on the basis of whether or not the execution trace of
the simulation of their input matches one of two known infinite
execution patterns.
The above conventional undecidable TM/input pair is correctly decided
as halting on the basis of fully operational C/x86 code in the x86utm
operating system.
Your P is derived from H (somewhat) in accordance with the rules that
Linz uses to derive H_Hat from H.
Your P is *not* derived from H1 in this way.
If your H1 can correctly decide (P, P) that has no bearing on Linz.
Linz
never claimed that you cannot construct a TM which correctly decides
H_Hat, H_Hat. He claims only that H cannot do so.
Your H can *not* correctly decide (P, P) and that's the case that
actually matters.
H1 is an exact copy of H and is able to correctly decide that its
input halts because P was not designed to contradict H1. Because P was
intentionally designed to contradict H the return value from H and H1
are not the same.
The key question of this post is whether H/H1 would be disallowed as
Turing computable on the basis that H must use static local variables
to keep track of the execution trace of its input across subsequent
recursive simulations.
If it must keep track of *any* data across different calls then it is
not a computation. So yes, it is disqualified.
André
On 2021-09-20 11:42, olcott wrote:
On 9/20/2021 12:17 PM, André G. Isaak wrote:
On 2021-09-20 10:44, olcott wrote:
On 9/20/2021 11:15 AM, Charlie-Boo wrote:
On Saturday, September 18, 2021 at 11:42:41 PM UTC-4, olcott wrote: >>>>>> This is my paraphrase of the requirement a partial
halt decider must be a pure function of its inputs:
As long as there is one set of inputs such as such as the formal
parameters to a function and a single output such as return value of >>>>>> {1,0} (indicating true or false) from this function, then whatever >>>>>> occurs in-between does not make any difference.
This would mean that my use of static local variables has no
detrimental
effect on the applicability of my partial halt decider to the halting >>>>>> problem.
u32 H(u32 P, u32 I)
{
static u32 Aborted;
static u32* execution_trace;
--
Copyright 2021 Pete Olcott
"Great spirits have always encountered violent opposition from
mediocre
minds." Einstein
There is no significance to solving "some instances" of a problem.
That includes no instances or trivial instances (here it would be
YES answers) which have no significance.
It's basically impossible to carve out any non-trivial subsets of
programs whose halting problem can be solved.
The easiest way to advance unsolvable problems (nonrecursive sets)
has always been to find unsolved problems - proving sets are not
recursive, typically r.e. sets.
C-B
void P(u32 x)
{
if (H(x, x))
HERE: goto HERE;
}
int main()
{
Output("Input_Halts = ", H1((u32)P, (u32)P));
}
H and H1 are simulating partial halt deciders that make their halt
status decision on the basis of whether or not the execution trace
of the simulation of their input matches one of two known infinite
execution patterns.
The above conventional undecidable TM/input pair is correctly
decided as halting on the basis of fully operational C/x86 code in
the x86utm operating system.
Your P is derived from H (somewhat) in accordance with the rules that
Linz uses to derive H_Hat from H.
Your P is *not* derived from H1 in this way.
If your H1 can correctly decide (P, P) that has no bearing on Linz.
It may seem that way to a reviewer that says blah, blah, blah, I know
that you must be wrong because I really, really believe that you must
be wrong so there is no sense in paying any attention to what you say.
It doesn't merely seem that way, it is that way.
On the other hand Olcott H1/H/P is analogous to Linz H/Ĥ/⟨Ĥ⟩ in that it
Given that your P is essentially Linz's H_Hat, How can H1/H/P be
analogous to H/Ĥ/⟨Ĥ⟩?
You're claiming that your H is somehow analogous to both Linz's H and to Linz's H_Hat.
shows that simulating halt decider Linz H correctly decides the halt
status of the Linz input ⟨Ĥ⟩ ⟨Ĥ⟩.
Linz never claimed that you cannot construct a TM which correctly
decides H_Hat, H_Hat. He claims only that H cannot do so.
The whole point of the halting theorem is to prove that no universal
halt decider can possibly exist.
I have shown how to create a decidability decider that correctly
decides that Ĥ.qx ⟨Ĥ⟩ ⟨Ĥ⟩ is not correctly decidable by Ĥ.qx, thus
allowing H to be automatically selected as the correct halting decider
for ⟨Ĥ⟩ ⟨Ĥ⟩, thus the combination of the decidability decider and >> three instances of the same algorithm derives a universal halt decider.
When H applied to ⟨Ĥ⟩ ⟨Ĥ⟩ != When Ĥ.qx applied to ⟨Ĥ⟩ ⟨Ĥ⟩ we know that
⟨Ĥ⟩ ⟨Ĥ⟩ is not correctly decidable for either H or Ĥ.qx, one more >> instance of this same algorithm excludes the odd-man-out and thus
selects the correct halt decider.
But, as I have pointed out previously, and which you ignored, you are
then claiming that your *real* halt decider is the combination of H, H1,
Hx and your 'decidability decider'.
In that case your P must be derived from that *combination* if you want
to claim that it is analogous to Linz's H_Hat.
The whole point of the Linz proof is that for *any* 'halt decider' X,
one can always construct an X_Hat which it cannot decide correctly. Your combined H+H1+Hx+DD is just as susceptible to this as any other putative 'halt decider'.
André
Sysop: | Keyop |
---|---|
Location: | Huddersfield, West Yorkshire, UK |
Users: | 366 |
Nodes: | 16 (3 / 13) |
Uptime: | 00:13:49 |
Calls: | 7,837 |
Calls today: | 6 |
Files: | 12,933 |
Messages: | 5,771,873 |