On 11/18/21 11:04 PM, olcott wrote:
typedef void (*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);
}
computation that halts
a computation is said to halt whenever it enters a final state.
(Linz:1990:234)
Combinations of H/P having pathological self-reference (PSR set)
For every possible H of H(P,P) invoked from main() where P(P) calls
this same H(P,P) and H simulates or executes its input and aborts or
does not abort its input P never reaches its last instruction.
Right, H will never see its processing of its input reach a final state,
so maybe H is a correct POOP decider, but that is not the definiton of Halting, that looks at the ACTUAL behavior of the computation the input represents, which if H(P,P) returns 0, will be halting.
One element of the above (PSR set) Hz simply simulates 100 steps of Pz
and returns.
This provides a specific concrete example where the input to H(P,P)
never halts and P(P) halts thus conclusively proving that such an
example exists.
Right, and now let us look at what Pz(Pz) does, when we DIRECTLY run
Pz(Pz), which is what we need to do to see what that computation does.
1) Pz(Pz) calls Hz(Pz,Pz)
2) Hz(Pz,Pz) will execute 100 steps, flipping between code in Hz and Pz perhaps many times.
3) Hz will then abort its processing of the input.
4) Hz(Pz,Pz) will return 0 to the Pz(Pz) that called it
5) Pz(Pz) then returns 1
Thus, the computation Pz(Pz) is shown to reach its final state when run,
and thus is halting.
Instead of simply simulating the first 100 instructions of P halt
decider H might abort the simulation of its input on the basis of the
behavior of this input. It is still the case that the input to H(P,P)
never halts and P(P) halts.
But then the above trace is STILL the results of directly running P(P).
When H sees that P calls H(P,P) with the same parameters that it was
called with this gives H its correct (infinite recursion) halt
deciding basis. H(P,P) then aborts the simulation of its input and
returns 0.
Ĥ.q0 ⟨Ĥ⟩ ⊢* Ĥ.qx ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* Ĥ.qn
The reasoning applied to H(P,P) and P(P) equally applies to Linz Ĥ.qx
⟨Ĥ⟩ ⟨Ĥ⟩ and Ĥ ⟨Ĥ⟩
Right, and since this is showing the execution path of H^ applied to
<H^> is shows that H^ applied to <H^> reaches the final state H.qn,
which is a halting state, thus H^ applied to <H^> is a halting computation.
We also have that since H^.qx is a copy of H we have that H applied to <H^><H^> gives the decision that its input is non-halting.
But its input is the representaiton of H^ appied to <H^> which we just
showed halted, so H is wrong.
We can also see this by taking that exact input <H^><H^> and applying a
UTM to it, which BY DEFINITION will behave exactly like H^ applied to
<H^> so iit will also halt.
Thus H is wrong, and you claim that it was right is shown to be a LIE.
Halting problem undecidability and infinitely nested simulation (V2)
November 2021 PL Olcott
https://www.researchgate.net/publication/356105750_Halting_problem_undecidability_and_infinitely_nested_simulation_V2
FAIL.
You just prove your ignorance of what you are talking about.
On 2021-11-19 07:44, olcott wrote:
On 11/19/2021 6:35 AM, Richard Damon wrote:
Except that just calling something a 'Strawman' doesn't make it go away.
Yes it does make it go away.
When I refer to a the behavior of P in a precisely defined set of
computations and your rebuttal refers to the behavior of P in an
entirely different set of computations then you make the logic mistake
known at the strawman error.
The problem is that your 'precisely defined set of computations' doesn't match the ones which the halting problem is concerned with.
You can't
claim to have 'solved' this problem when you are concerned with an
entirely different set of behaviours than the actual problem is.
The halting problem is interested *only* in the behaviour of P(P) when
it is run *outside* of H. You are determined to only discuss its
behaviour when it is run inside of H.
André
On 2021-11-19 09:45, olcott wrote:
On 11/19/2021 9:08 AM, André G. Isaak wrote:
On 2021-11-19 07:44, olcott wrote:
On 11/19/2021 6:35 AM, Richard Damon wrote:
Except that just calling something a 'Strawman' doesn't make it go
away.
Yes it does make it go away.
When I refer to a the behavior of P in a precisely defined set of
computations and your rebuttal refers to the behavior of P in an
entirely different set of computations then you make the logic
mistake known at the strawman error.
The problem is that your 'precisely defined set of computations'
doesn't match the ones which the halting problem is concerned with.
Yes it does that you fail to comprehend this is not may fault.
This is the exact set of all of the "Impossible" inputs to the halting
theorem's halt decider:
Combinations of H/P having pathological self-reference (PSR set)
For every possible H of H(P,P) invoked from main() where P(P) calls
this same H(P,P) and H simulates or executes its input and aborts or
does not abort its input P never reaches its last instruction.
Yes, but the definition of a halt decider, translated into C for your benefit, is a program H which takes an input P, I such that the H in
int main { H(P, I); }
returns true if and only if the following computation halts:
int main { P(I); }
It doesn't make a bit of difference whether you call P(P) 'pathological'
or not. The crucial point is that your H does not correctly answer the question that a halt decider is required to answer for this particular
input.
Your claim that your H is 'correct' is because you assume that your H is answering an entirely different question from the above.
No one, including Linz, has ever claimed that that a TM cannot be
constructed that answers that question, largely because no one has ever
even found your question to be sufficiently interesting to even think
about.
André
On 2021-11-19 10:32, olcott wrote:
On 11/19/2021 10:57 AM, André G. Isaak wrote:
On 2021-11-19 09:45, olcott wrote:
On 11/19/2021 9:08 AM, André G. Isaak wrote:
On 2021-11-19 07:44, olcott wrote:
On 11/19/2021 6:35 AM, Richard Damon wrote:
Except that just calling something a 'Strawman' doesn't make it
go away.
Yes it does make it go away.
When I refer to a the behavior of P in a precisely defined set of
computations and your rebuttal refers to the behavior of P in an
entirely different set of computations then you make the logic
mistake known at the strawman error.
The problem is that your 'precisely defined set of computations'
doesn't match the ones which the halting problem is concerned with.
Yes it does that you fail to comprehend this is not may fault.
This is the exact set of all of the "Impossible" inputs to the
halting theorem's halt decider:
Combinations of H/P having pathological self-reference (PSR set)
For every possible H of H(P,P) invoked from main() where P(P) calls
this same H(P,P) and H simulates or executes its input and aborts or
does not abort its input P never reaches its last instruction.
Yes, but the definition of a halt decider, translated into C for your
benefit, is a program H which takes an input P, I such that the H in
int main { H(P, I); }
returns true if and only if the following computation halts:
int main { P(I); }
NO That is a very very persistent fallacy of equivocation error.
Where am I equivocating? I am telling you how 'halt decider' is actually DEFINED. The definition is precise and unambiguous. The fact that you
have come up with a deranged interpretation in attempting to translate
the Turing Machine terminology (which you really don't understand) into
C terminology is your problem, not mine.
A correct halt decider must base its halt status decision on:
(a) the actual sequence of instruction steps
(b) that are actually specified by
(c) an actual direct execution or
(d) actual correct simulation of
(e) the actual input.
If you get rid of any of the "actuals" the halt decider cannot be
relied on as correct.
The 'actual input' to a halt decider is a description of a computation.
The behaviour which it is supposed to decide is that of the computation itself.
A computation is a self-contained entity which runs independently, not something which runs 'inside' the halt decider.
André
The input to (H,P) never halts P(P) halts.
Here are the divergent execution sequences at the C level:
int main(){ H(P,P); }
(1) main()
(2) calls H(P,P) that simulates the input to H(P,P)
(3) that calls H(P,P) which aborts its simulation of P(P) and returns to
(4) main().
int main(){ P(P); }
(a) main() calls P(P) that
(b) calls H(P,P) that simulates the input to H(P,P)
(c) that calls H(P,P) which aborts its simulation of P(P) and returns to
(d) P(P) that returns to main()
(1) diverges from (a) causing (4) to diverge from (d)
And a halt decider is concerned only with the SECOND case, not the first.
This is a simple matter of definition. If you are addressing the first
case rather than the second you are not addressing the halting problem
but rather some other problem of your own making. Neither Linz nor
anyone else cares about that other problem.
André
On 2021-11-19 11:06, olcott wrote:
On 11/19/2021 11:46 AM, André G. Isaak wrote:
On 2021-11-19 10:32, olcott wrote:
The input to (H,P) never halts P(P) halts.
Here are the divergent execution sequences at the C level:
int main(){ H(P,P); }
(1) main()
(2) calls H(P,P) that simulates the input to H(P,P)
(3) that calls H(P,P) which aborts its simulation of P(P) and
returns to
(4) main().
int main(){ P(P); }
(a) main() calls P(P) that
(b) calls H(P,P) that simulates the input to H(P,P)
(c) that calls H(P,P) which aborts its simulation of P(P) and
returns to
(d) P(P) that returns to main()
(1) diverges from (a) causing (4) to diverge from (d)
And a halt decider is concerned only with the SECOND case, not the
first.
The halt decider is concerned with the execution trace of a sequence
of instructions other than the actual execution trace that is
specified by actually executing or simulating its actual input?
Your question makes no sense.
int main() { P(P); } *is* actually executing the input to int main() { H(P,P); }. In int main() { H(P,P); } it is *not* being executed; it is
being passed as a parameter to another function.
The halting problem asks whether a given computation will halt *when it
is performed*.
When you execute H(H_Hat, H_Hat) the computation H_Hat(H_Hat) is *not*
being performed. It is having a question asked about it. That's true
even if H makes use of partial simulation.
The computation is being performed only when you actually run
H_Hat(H_Hat), not when you provide a description of it to another Turing Machine.
André
On 2021-11-19 13:13, olcott wrote:
On 11/19/2021 2:03 PM, André G. Isaak wrote:
On 2021-11-19 12:26, olcott wrote:
On 11/19/2021 12:31 PM, André G. Isaak wrote:
On 2021-11-19 11:06, olcott wrote:
On 11/19/2021 11:46 AM, André G. Isaak wrote:
On 2021-11-19 10:32, olcott wrote:
The input to (H,P) never halts P(P) halts.
Here are the divergent execution sequences at the C level:
int main(){ H(P,P); }
(1) main()
(2) calls H(P,P) that simulates the input to H(P,P)
(3) that calls H(P,P) which aborts its simulation of P(P) and
returns to
(4) main().
int main(){ P(P); }
(a) main() calls P(P) that
(b) calls H(P,P) that simulates the input to H(P,P)
(c) that calls H(P,P) which aborts its simulation of P(P) and
returns to
(d) P(P) that returns to main()
(1) diverges from (a) causing (4) to diverge from (d)
And a halt decider is concerned only with the SECOND case, not
the first.
The halt decider is concerned with the execution trace of a
sequence of instructions other than the actual execution trace
that is specified by actually executing or simulating its actual
input?
Your question makes no sense.
It is proven that the execution trace of P(P) and the execution
trace of the input to H(P,P) are not the same and that this
difference results in different behavior.
And the halting problem, BY DEFINITION, is concerned only with the
former. The latter is not of interest to anyone.
It may seem that way until you realize that any other case would not
be reporting on the actual behavior of the actual sequence of
instructions specified by the actual execution trace of the actual
simulation or execution of its actual input.
The definition is what it is. A halt reporter reports on the behaviour
of the computation described by its input when that computation is run
as an independent computation; not when it is wrapped inside your H.
Just because you don't like the definition doesn't mean you can change it.
When Bill Jones robs a liquor store people may get confused and arrest
his identical twin brother that is also named Bill Jones.
Except that you are the one who is arresting the wrong Bill Jones.
André
On 2021-11-19 13:13, olcott wrote:
On 11/19/2021 2:03 PM, André G. Isaak wrote:
On 2021-11-19 12:26, olcott wrote:
On 11/19/2021 12:31 PM, André G. Isaak wrote:
On 2021-11-19 11:06, olcott wrote:
On 11/19/2021 11:46 AM, André G. Isaak wrote:
On 2021-11-19 10:32, olcott wrote:
The input to (H,P) never halts P(P) halts.
Here are the divergent execution sequences at the C level:
int main(){ H(P,P); }
(1) main()
(2) calls H(P,P) that simulates the input to H(P,P)
(3) that calls H(P,P) which aborts its simulation of P(P) and
returns to
(4) main().
int main(){ P(P); }
(a) main() calls P(P) that
(b) calls H(P,P) that simulates the input to H(P,P)
(c) that calls H(P,P) which aborts its simulation of P(P) and
returns to
(d) P(P) that returns to main()
(1) diverges from (a) causing (4) to diverge from (d)
And a halt decider is concerned only with the SECOND case, not
the first.
The halt decider is concerned with the execution trace of a
sequence of instructions other than the actual execution trace
that is specified by actually executing or simulating its actual
input?
Your question makes no sense.
It is proven that the execution trace of P(P) and the execution
trace of the input to H(P,P) are not the same and that this
difference results in different behavior.
And the halting problem, BY DEFINITION, is concerned only with the
former. The latter is not of interest to anyone.
It may seem that way until you realize that any other case would not
be reporting on the actual behavior of the actual sequence of
instructions specified by the actual execution trace of the actual
simulation or execution of its actual input.
The definition is what it is. A halt reporter reports on the behaviour
of the computation described by its input when that computation is run
as an independent computation; not when it is wrapped inside your H.
Just because you don't like the definition doesn't mean you can change it.
When Bill Jones robs a liquor store people may get confused and arrest
his identical twin brother that is also named Bill Jones.
Except that you are the one who is arresting the wrong Bill Jones.
André
On 2021-11-19 15:15, olcott wrote:
On 11/19/2021 3:05 PM, André G. Isaak wrote:
On 2021-11-19 13:13, olcott wrote:
On 11/19/2021 2:03 PM, André G. Isaak wrote:
On 2021-11-19 12:26, olcott wrote:
On 11/19/2021 12:31 PM, André G. Isaak wrote:
On 2021-11-19 11:06, olcott wrote:
On 11/19/2021 11:46 AM, André G. Isaak wrote:
On 2021-11-19 10:32, olcott wrote:
The input to (H,P) never halts P(P) halts.
Here are the divergent execution sequences at the C level: >>>>>>>>>>
int main(){ H(P,P); }
(1) main()
(2) calls H(P,P) that simulates the input to H(P,P)
(3) that calls H(P,P) which aborts its simulation of P(P) and >>>>>>>>>> returns to
(4) main().
int main(){ P(P); }
(a) main() calls P(P) that
(b) calls H(P,P) that simulates the input to H(P,P)
(c) that calls H(P,P) which aborts its simulation of P(P) and >>>>>>>>>> returns to
(d) P(P) that returns to main()
(1) diverges from (a) causing (4) to diverge from (d)
And a halt decider is concerned only with the SECOND case, not >>>>>>>>> the first.
The halt decider is concerned with the execution trace of a
sequence of instructions other than the actual execution trace >>>>>>>> that is specified by actually executing or simulating its actual >>>>>>>> input?
Your question makes no sense.
It is proven that the execution trace of P(P) and the execution
trace of the input to H(P,P) are not the same and that this
difference results in different behavior.
And the halting problem, BY DEFINITION, is concerned only with the
former. The latter is not of interest to anyone.
It may seem that way until you realize that any other case would not
be reporting on the actual behavior of the actual sequence of
instructions specified by the actual execution trace of the actual
simulation or execution of its actual input.
The definition is what it is. A halt reporter reports on the
behaviour of the computation described by its input when that
computation is run as an independent computation; not when it is
wrapped inside your H.
Just because you don't like the definition doesn't mean you can
change it.
given the description of a Turing machine M and an input w, does M,
when started in the initial configuration q0 w, perform a computation
that eventually halts? (Linz:1990:317)
In other words: Does UTM(M, w) halt?
That definition makes no mention of UTMs, and he carefully distinguishes between the description of M (which he elsewhere notates as w_M).
But yes, UTM(w_M, w) will halt if and only if M(w) halts.
But that isn't what you've been claiming since your H is not a UTM, nor
are you claiming that H(P, P) halts if and only if P(P) halts but are
instead claiming something about the "input" to H.
If an actual UTM were applied to P(P), you would find that UTM(P, P)
does in fact halt just as P(P) does.
André
| Sysop: | Keyop |
|---|---|
| Location: | Huddersfield, West Yorkshire, UK |
| Users: | 296 |
| Nodes: | 16 (2 / 14) |
| Uptime: | 65:17:12 |
| Calls: | 6,654 |
| Files: | 12,200 |
| Messages: | 5,331,838 |