On 2021-11-19 17:16, olcott wrote:
On 11/19/2021 5:33 PM, André G. Isaak wrote:
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.
Because the behavior of the UTM simulation of the machine description
of TM X on input Y is defined to precisely correspond to the direct
execution of TM X on input Y we can also always rely on the following:
If UTM U is adapted to become a halt decider H for a subset of inputs
Z such that it aborts the simulation of its input only when the
behavior of the pure simulation of this input conclusively proves that
this input would never reach its final state, then H can abort the
simulation of every element of Z and correctly report that its input
does not halt.
The fact that UTM(M, w) and M(w) have the same halting status has no
bearing on the definition of a halt decider and provides no
justification for the above.
The input to UTM(M, w) doesn't have a halting status anymore than the
input to H does. Only actual computations have a halting status. So you
can ask about whether UTM(M, w) halts, or about whether the computation described by its input halts, but not about whether the input halts.
H(P, P) may or may not reach a final state. P(P) may or may not reach a
final state. It is meaningless, though, to talk about the input to H(P,
P) reaching a final state.
André
On 2021-11-20 10:45, olcott wrote:
On 11/20/2021 12:57 AM, André G. Isaak wrote:
On 2021-11-19 17:16, olcott wrote:
On 11/19/2021 5:33 PM, André G. Isaak wrote:
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.And a halt decider is concerned only with the SECOND case, >>>>>>>>>>>>> not the first.
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) >>>>>>>>>>>>>
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.
Because the behavior of the UTM simulation of the machine
description of TM X on input Y is defined to precisely correspond to
the direct execution of TM X on input Y we can also always rely on
the following:
If UTM U is adapted to become a halt decider H for a subset of
inputs Z such that it aborts the simulation of its input only when
the behavior of the pure simulation of this input conclusively
proves that this input would never reach its final state, then H can
abort the simulation of every element of Z and correctly report that
its input does not halt.
The fact that UTM(M, w) and M(w) have the same halting status has no
bearing on the definition of a halt decider and provides no
justification for the above.
The input to UTM(M, w) doesn't have a halting status anymore than the
input to H does. Only actual computations have a halting status. So
you can ask about whether UTM(M, w) halts, or about whether the
computation described by its input halts, but not about whether the
input halts.
H(P, P) may or may not reach a final state. P(P) may or may not reach
a final state. It is meaningless, though, to talk about the input to
H(P, P) reaching a final state.
André
Not when the [PSR set] if the basis for this claim:
Computation that halts
a computation is said to halt whenever it enters a final state.
(Linz:1990:234)
PSR set: Combinations of H/P having pathological self-reference
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.
PSR subset: Because we know that the input to H(P,P) never halts for
the whole PSR set and a subset of these H/P combinations aborts the
execution or simulation of its input then we know that for this entire
subset the input to H(P,P) never halts and H(P,P) halts.
When int main(void) { P(P); } is invoked on H/P elements of the above
PSR subset, then we have a cases where the input to H(P,P) never halts
and P(P) halts.
The above cases conclusively prove that when the input to H(P,P) never
halts and the same P(P) does halt that this does not form any
contradiction.
Inputs neither halt nor don't halt. Your 'PSR set' included. Only
Computions halt or don't halt.
And, as I said, the definition of a Halt Decider is already defined.
H(P, P), if it is a halt decider, must report whether P(P) called
directly from main halts or not, so your meaningless claim that 'the
input to H(P, P) never halts' even though P(P) does halt is just a
feeble attempt on your part to rationalize the fact that your H gives
the wrong answer.
André
On 2021-11-20 13:35, olcott wrote:
On 11/20/2021 2:03 PM, André G. Isaak wrote:
On 2021-11-20 10:45, olcott wrote:
On 11/20/2021 12:57 AM, André G. Isaak wrote:
On 2021-11-19 17:16, olcott wrote:
On 11/19/2021 5:33 PM, André G. Isaak wrote:
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: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.
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.And a halt decider is concerned only with the SECOND >>>>>>>>>>>>>>> case, not the first.
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) >>>>>>>>>>>>>>>
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. >>>>>>>>>
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.
Because the behavior of the UTM simulation of the machine
description of TM X on input Y is defined to precisely correspond
to the direct execution of TM X on input Y we can also always rely >>>>>> on the following:
If UTM U is adapted to become a halt decider H for a subset of
inputs Z such that it aborts the simulation of its input only when >>>>>> the behavior of the pure simulation of this input conclusively
proves that this input would never reach its final state, then H
can abort the simulation of every element of Z and correctly
report that its input does not halt.
The fact that UTM(M, w) and M(w) have the same halting status has
no bearing on the definition of a halt decider and provides no
justification for the above.
The input to UTM(M, w) doesn't have a halting status anymore than
the input to H does. Only actual computations have a halting
status. So you can ask about whether UTM(M, w) halts, or about
whether the computation described by its input halts, but not about
whether the input halts.
H(P, P) may or may not reach a final state. P(P) may or may not
reach a final state. It is meaningless, though, to talk about the
input to H(P, P) reaching a final state.
André
Not when the [PSR set] if the basis for this claim:
Computation that halts
a computation is said to halt whenever it enters a final state.
(Linz:1990:234)
PSR set: Combinations of H/P having pathological self-reference
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.
PSR subset: Because we know that the input to H(P,P) never halts for
the whole PSR set and a subset of these H/P combinations aborts the
execution or simulation of its input then we know that for this
entire subset the input to H(P,P) never halts and H(P,P) halts.
When int main(void) { P(P); } is invoked on H/P elements of the
above PSR subset, then we have a cases where the input to H(P,P)
never halts and P(P) halts.
The above cases conclusively prove that when the input to H(P,P)
never halts and the same P(P) does halt that this does not form any
contradiction.
Inputs neither halt nor don't halt. Your 'PSR set' included. Only
Computions halt or don't halt.
Inputs specify a sequence of configurations that either reach a final
state or not.
And, as I said, the definition of a Halt Decider is already defined.
Halt decider H maps elements of its domain specifying sequences of
configurations to {0,1}. Its decision basis is whether or not the
specified sequence of configurations ever reaches a final state.
H(P, P), if it is a halt decider, must report whether P(P) called
directly from main halts or not, so your meaningless claim that 'the
An actual mathematical function H can only map elements of its domain
to elements of its codomain.
In mathematics, a function from a set X to a set Y is an assignment of
an element of Y to each element of X. The set X is called the domain
of the function and the set Y is called the codomain of the function.
https://en.wikipedia.org/wiki/Function_(mathematics)
Halt decider H can only map elements of its domain specifying
sequences of configurations to {0,1}.
The domain of a halt decider is the set of computations (expressed by suitable representations)
It maps that domain to 1 for exactly that set of computations which halt
when run as independent computations and to 0 otherwise.
Since P(P) halts, H(P, P) must map that input to 1.
André
On 2021-11-20 18:35, olcott wrote:
On 11/20/2021 7:12 PM, André G. Isaak wrote:
On 2021-11-20 18:00, olcott wrote:
How do you tell H that it is not allowed to determine the halt
status of its input on the basis of the actual behavior of this
actual input?
The 'input' is a description of an independent computation.
descriptions don't *have* behaviour. It is required to base its
decision on the actual behaviour of the independent computation
described by its input.
This is really not that difficult.
Inputs specify sequences of configurations.
The input to a halt decider is a description of a computation, i.e. a description of a TM and an input string. If you want to call that a
'sequence of configurations', fine, but what's wrong with the standard terminology?
To put this bluntly: Every single computer scientist on earth agrees
on the definition of 'halt decider'. So does virtually every
competent undergraduate who has taken a course on computation. That's
because the definition is precisely defined with absolutely no
ambiguity regarding how it is to be interpreted.
To meet that definition, your H(P, P) *must* report on whether P(P)
halts when called directly from main.
Define the domain of the mathematical function H that says that.
The domain of H is the set of pairs consisting of the description of a
TM and an input string. I already answered that in another post.
The domain of H is the set of pairs consisting of
the description of a TM and an input string.
A TM *by definition* is an independent, self-contained entity, so there
is no need to specify this. Translating that to C, it means an
independent program (or the sole call inside main), not a function
called from within some other program.
The fact that you don't grasp this just reinforces the fact that you
have no idea what a computation is.
André
Sysop: | Keyop |
---|---|
Location: | Huddersfield, West Yorkshire, UK |
Users: | 365 |
Nodes: | 16 (2 / 14) |
Uptime: | 64:06:19 |
Calls: | 7,774 |
Files: | 12,908 |
Messages: | 5,749,824 |