On 1/15/22 4:47 PM, olcott wrote:
Most people that try to form a rebuttal of my halting problem proof
refutation lack sufficient basic understanding of the computer science
involved.
The primary reason for this short-coming is that none of the textbook
explanations of the halting problem are sufficiently precise.
No, your understanding is not sufficient for the task.
Every decider computes the mapping from its input(s) to an accept or
reject state.
A halt decider H computes the mapping from a P/I finite string pair
(where P is a machine description) to an accept or reject state.
H must compute this mapping on the basis of the actual behavior that
P/I specifies.
AND, that mapping MUST match the ACTUAL behavior of the computation it
is deciding on.
The most definite way to determine N steps of the behavior that P/I
actually specifies is to perform a pure simulation of N steps of P/I.
Ĥ.q0 ⟨Ĥ⟩ ⊢* Ĥ.qx ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* Ĥ.qy ∞
Ĥ.q0 ⟨Ĥ⟩ ⊢* Ĥ.qx ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* Ĥ.qn
The copy of H at Ĥ.qx referred to as embedded_H must compute
the mapping from its own inputs: ⟨Ĥ⟩ ⟨Ĥ⟩ to Ĥ.qy or Ĥ.qn.
It must do this on the basis of the actual behavior specified by these
inputs.
The actual behavior specified by these inputs is the behavior of the
pure simulation of N steps of ⟨Ĥ⟩ applied to ⟨Ĥ⟩ until:
(a) The simulated ⟨Ĥ⟩ reaches its final state or
(b) embedded_H recognizes that simulated ⟨Ĥ⟩ would never reach its
final state.
WRONG. The actual behavior specifie by these inputs is the behavior of
the pure simulation until it completes, or forever if it never halts.
Linz, Peter 1990. An Introduction to Formal Languages and Automata.
Lexington/Toronto: D. C. Heath and Company. (317-320)
https://www.liarparadox.org/Peter_Linz_HP_317-320.pdf
On 1/16/22 5:25 PM, olcott wrote:
On 1/16/2022 4:15 PM, Richard Damon wrote:
On 1/16/22 4:39 PM, olcott wrote:
On 1/16/2022 2:55 PM, Richard Damon wrote:
On 1/16/22 3:26 PM, olcott wrote:
On 1/16/2022 2:04 PM, Richard Damon wrote:
On 1/16/22 2:12 PM, olcott wrote:
On 1/16/2022 1:00 PM, Richard Damon wrote:
On 1/16/22 1:11 PM, olcott wrote:
On 1/16/2022 11:48 AM, Richard Damon wrote:WRONG.
On 1/16/22 11:05 AM, olcott wrote:
On 1/15/2022 4:26 PM, Richard Damon wrote:
On 1/15/22 4:47 PM, olcott wrote:
Most people that try to form a rebuttal of my halting >>>>>>>>>>>>>> problem proof refutation lack sufficient basic
understanding of the computer science involved.
The primary reason for this short-coming is that none of >>>>>>>>>>>>>> the textbook explanations of the halting problem are >>>>>>>>>>>>>> sufficiently precise.
No, your understanding is not sufficient for the task. >>>>>>>>>>>>>
Every decider computes the mapping from its input(s) to an >>>>>>>>>>>>>> accept or reject state.
A halt decider H computes the mapping from a P/I finite >>>>>>>>>>>>>> string pair
(where P is a machine description) to an accept or reject >>>>>>>>>>>>>> state.
H must compute this mapping on the basis of the actual >>>>>>>>>>>>>> behavior that P/I specifies.
AND, that mapping MUST match the ACTUAL behavior of the >>>>>>>>>>>>> computation it is deciding on.
The most definite way to determine N steps of the behavior >>>>>>>>>>>>>> that P/I actually specifies is to perform a pure
simulation of N steps of P/I.
Ĥ.q0 ⟨Ĥ⟩ ⊢* Ĥ.qx ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* Ĥ.qy ∞ >>>>>>>>>>>>>> Ĥ.q0 ⟨Ĥ⟩ ⊢* Ĥ.qx ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* Ĥ.qn >>>>>>>>>>>>>>
The copy of H at Ĥ.qx referred to as embedded_H must compute >>>>>>>>>>>>>> the mapping from its own inputs: ⟨Ĥ⟩ ⟨Ĥ⟩ to Ĥ.qy or Ĥ.qn.
It must do this on the basis of the actual behavior >>>>>>>>>>>>>> specified by these inputs.
The actual behavior specified by these inputs is the >>>>>>>>>>>>>> behavior of the pure simulation of N steps of ⟨Ĥ⟩ applied >>>>>>>>>>>>>> to ⟨Ĥ⟩ until:
(a) The simulated ⟨Ĥ⟩ reaches its final state or >>>>>>>>>>>>>> (b) embedded_H recognizes that simulated ⟨Ĥ⟩ would never >>>>>>>>>>>>>> reach its final state.
WRONG. The actual behavior specifie by these inputs is the >>>>>>>>>>>>> behavior of the pure simulation until it completes, or >>>>>>>>>>>>> forever if it never halts.
That is correct. In those cases where the input specifies an >>>>>>>>>>>> infinite sequence of configurations a halt decider either: >>>>>>>>>>>>
(a) Recognizes that this sequence would never reach its >>>>>>>>>>>> final state in any finite number of steps
and aborts its simulation of this input
and transitions to its reject state. >
(b) Fails to be a decider at all.
computation that halts … the Turing machine will halt >>>>>>>>>>>> whenever it enters a final state. (Linz:1990:234)
According to Linz any sequence of configurations that would >>>>>>>>>>>> never reach its final state in any finite number of steps is >>>>>>>>>>>> a non halting sequence.
Except that as has been shown, if H aborts its simulation and >>>>>>>>>>> returns non-halting, then BY CONSTRUCTION, H^ will halt. >>>>>>>>>>> Thus, there exists no finite sequence of states that
correctly prove that H^ will not halt.
For ANY finite number of states that H might simulate the >>>>>>>>>>> computation of H^ <H^>, and abort it and return
Non-Halting, there exists another finite but larger number of >>>>>>>>>>> states that H^ <H^> will halt in.
You are confusing yourself with your own double talk.
If when embedded_H makes its decision the pure simulation of >>>>>>>>>> its own input cannot possibly reach any final state of this >>>>>>>>>> input in any finite number of steps then embedded_H is
necessarily correct to abort the simulation of this input and >>>>>>>>>> transition to Ĥ.qn.
Once embedded_H has made this decision subsequent evaluation >>>>>>>>>> is cut off because Ĥ applied to ⟨Ĥ⟩ has stopped running. >>>>>>>>>
H^ applied to <H^> can NEVER stop running until it hits its
final state.
THAT IS THE DEFINITION OF HALTING/Non-Halting.
The fact that H (aka embedded_H) has aborted it simulation of >>>>>>>>> this string does NOT affect the actual behavior of the string >>>>>>>>> as the behavior is based on what a REAL UTM does with it, not >>>>>>>>> your 'fake' UTM that aborts.
You already understand that if the simulating halt decider
embedded_H never stopped simulating its input that its input
would never reach its final state.
Right IF the simulating Halt Decider never stopped simulating,
then H^ would never halt, but that is only true IF H never aborts. >>>>>>>
There is no 'unless' here, either H does or it doesn't abort its >>>>>>> simulation. If H doesn't abort, then H^ in non-halting.
You already understand that when a simulated input can never
reach its final state that this input specifies a sequence of
configurations that never halts.
Right, if the simulate input WHEN SIMULTED BY A NON-ABORTING UTM, >>>>>>> can never reach its final state, ths input specifies a sequnce of >>>>>>> configuration that never halts.
If H aborts its simulation, then you no longer have any 'proof'
that the input doesn't halt, and your proof was based on an H
that never aborted its simulation, so it isn't applicable here.
You don't seem to be able to put these two ideas together.
Because you are making incompatible assumptions.
If the simulated input to embedded_H cannot possibly ever reach
its final state then this conclusively proves that this input
meets the Linz definition of a sequence of configuration that does >>>>>> not halt.
WRONG. That applies only IF you define your H to actually BE a UTM,
and yes, if H IS a UTM, then H^ is non-halting, but H also doesn't
answer, so fails to be a correct decider.
So, your system only meets the requirements for a configuration
that does not halt if H doesn't abort its simulation.
Because the simulated input to embedded_H cannot possibly ever reach
its final state whether or not embedded_H aborts its simulation then
we know that this input meet the Linz definition of a sequence of
configurations that does not halt.
NO, WE DON'T.
It only meet the requirement if H doesn't abort.
The fact that an aborted simulation doesn't reach its final state
does NOT say that the input would never reach a final state if it was
simulated farther.
So, yes, you have proven that if you H is defined as a simulator that
never aborts its simulation, then H^ will be a non-halting
computation and the correct answer for a Halting Decider would be
non-halting, but by the conditions you just imposed on H to prove
that, H can not give that answer. Once you remove the constraint on H
that it never aborts its simulation, then your proof for the new H^
that is created from this new H becomes invalid and doesn't actually
prove anything like what you want. At best it proves that H can never
actually prove that H^ is halting (not that it isn't halting, just
that H can't actually prove it).
If halting was defined as "does not keep running forever" then you
would be right as soon as embedded_H aborts its simulation then its
input halts. Because this is not the way that halting is defined you
are wrong.
WRONG. Linz definition refers to the ACTUAL running of the machine,
not its simulation by a partial simulator.
Just because H has aborted its simulation does NOT mean that if the
input was actually simulated by a UTM it would not reach that final
state.
The fact that the input to embedded_H demonstrates an infinitely
repeating pattern that can be recognized by embedded_H as infinitely
repeating is what provides embedded_H with its "never reaches its
final state" halt status criterion measure.
But if H 'recognizes' it as an infinitely repeating pattern and goes to
H.Qn then the input it is looking at is KNOWN to Halt,
as it will also
go to H^.Qn and Halt in the not too distant future. This shows that
whatever pattern H used was incorrect.
This can be seen by running H and a real UTM in parallel and compare
there results. The way you have been describing your H, at the point
that H decides to abort, it will be at an entry to a copy of H, and we
know that when the UTM continues for just one more cycle that the top
level of H inside H^ will ALSO decide to abort its simulation, and
return the non-halting answer to the top level of H^ and H^ will halt.
This is guaranteed by the fact that this top level H is given the exact
same input as this H we are matching, so it MUST behave exactly the same.
Until you can show what is wrong with that logic, you are just making
false claims.
You are claiming that a lot of stuff 'Exists' that if they did should be
easy for you to provide an actual working example to prove that it does
exist since you claim you have a working program that does this.
Your failure to provide such evidence just seems to prove that you don't actually have the program working, and you can't actually prove that
these things exist.
All it proves is that you are incapable of understanding the logic of
the problem and are working out of your league and need to just claim
stuff to try and make it seem like you have something, which you don't.
Halting is a PURE Binary attribute. A given computation must either
Halt, or Never Halt. You H has shown that its input 'has not yet
halted' but that isn't either of the final states allowed as an answer.
When you examine the actual computation of H^ applied to <H^> you
will find that if H answers Non-Halting by going to H.Qn, then H^
will, by construction, end up halting. The fact that H's PARTIAL
simulation didn't reach that point is NOT any sort of evidence that
H^ is non-halting.
H needs to examine H^ with the H that it has. The 'hypothetical' of
assuming what happens if H doesn't abort is a red herring, as that is
not the H that it was built on, so that is looking at a DIFFERENT
machine H^, not the one that it has.
Since the input contains a copy of H in it, you can't change H to
now abort its simulation to give that answer, as now the input to
this new H is something different that you haven't proven anything
about.
The act of aborting the simulation of this input does not cause
this simulated input to reach its final state thus it continues to >>>>>> specify a sequence of configurations that does not halt.
WRONG. Since the input has a copy of this H inside it, the actions
of that copy of this H DO affect the behavior of the input, and
thus the actions of THIS copy of this H do affect the behavior of
its input.
Once you 'break' the rules by starting to vary the algorithm of the
decider as it is processing, you have lost the property that the
input has a fixed behavior too.
FAIL.
Please look at the sources of your definitions and make sure you
understand the restrictions assumed by them.
You keep on forgetting that your input has a copy of your decider
in it so if you start to argue over versions of the decider, you
are also changing the input.
H^ is non-halting if H doesn't abort. This doesn't mean H^ is
non-halting if H does abort.
The fact that H^'s behavior depends on H's behavior means
arguments based on varying the behavior of H to determine the
behavior of H^ are invalid.
Basically, you have ZERO grounds for your claim, as all you have >>>>>>> done is proven that Hn^ <Hn^> is non-halting and ignoring the
difference between Hn/Hn^ andHa/Ha^. You just want to ASSUME that >>>>>>> they behave the same with ZERO evidence.
FAIL.
RED HERRING.
It is like I say that cats are animals you agree
and animals are living things and you agree
then I say this means that cats are living things you disagree. >>>>>>>
That is not an accurate analogy.
It is more like the following:
If all the answers on the test are correct, the test is perfect. >>>>>>>
None of the answers I gave were incorrect.
(omit the fact that I didn't answer any of the questions).
Therefore, my test was perfect.
And THAT is the grade you get, a perfect ZERO on your proof.
FAIL.
If you disagree with this, please provide an actual source for >>>>>>>>> what seems to be your own made up fairy tale.
You even recently agreed that the 'behavior of the input' was >>>>>>>>> defined as the results of applying this input to a UTM. After >>>>>>>>> all, we need an 'unbiased' opinion of the behavior, not just >>>>>>>>> H's opinion of what it does, which is why we need the UTM to >>>>>>>>> look at it, it is the defined source of Truth for behaviors of >>>>>>>>> inputs.
Remember, by construction H^ x will ALWAYS do the opposite of >>>>>>>>>>> what machine H x x answers, so H can NOT correctly answer for >>>>>>>>>>> H^ <H^>, since H <H^> <H^>, by definition, mean the behavior >>>>>>>>>>> of H^ <H^>, which by construction is always the opposite of H >>>>>>>>>>> <H^> <H^>.
This means that your H either must use an INCORRECT pattern >>>>>>>>>>> and abort its simulation when it hasn't actually proven that >>>>>>>>>>> this pattern will ALWAYS lead to a non-halting state, or it >>>>>>>>>>> just fails to decide.
Both lead to H not being a correct Halt Decider.
One normal failing of your proofs is that you conflate the >>>>>>>>>>> behavior of two different candidates for your H, the Hn that >>>>>>>>>>> doesn't abort and thus leads to an infinite recursion, but >>>>>>>>>>> doesn't answer, and the Ha that does abort, but seems to >>>>>>>>>>> assume that when it is given <Ha^> as an input that it must >>>>>>>>>>> actually mean <Hn^>, and thus gives the wrong answer.
There is no problem with Ha <Hn^> <Hn^> returning the right >>>>>>>>>>> answer, except when it was actaully asked about Ha <Ha^> >>>>>>>>>>> <Ha^>, and since Hn and Ha are actually different machines, >>>>>>>>>>> so are Hn^ and Ha^, so the answers can easily (and are)
different.
Hn^ <Hn^> IS a Non-Halting Computation, and Hn falls into >>>>>>>>>>> your case (b) and fails to decide, and thus is wrong.
Ha^ <Ha^> is a Halting Computation, because Ha INCORRECTLY >>>>>>>>>>> thought it recognized a non-halting sequence (by conflating >>>>>>>>>>> Hn/Hn^ with Ha/Ha^) and aborted its simulation and returned >>>>>>>>>>> the wrong answer.
Linz, Peter 1990. An Introduction to Formal Languages and >>>>>>>>>>>>>> Automata. Lexington/Toronto: D. C. Heath and Company. >>>>>>>>>>>>>> (317-320)
https://www.liarparadox.org/Peter_Linz_HP_317-320.pdf >>>>>>>>>>>>>>
On 1/16/22 10:26 PM, olcott wrote:
On 1/16/2022 9:01 PM, Richard Damon wrote:
On 1/16/22 9:54 PM, olcott wrote:
On 1/16/2022 6:46 PM, Richard Damon wrote:
On 1/16/22 7:16 PM, olcott wrote:
On 1/16/2022 6:12 PM, Richard Damon wrote:
On 1/16/22 6:57 PM, olcott wrote:
On 1/16/2022 5:47 PM, Richard Damon wrote:
On 1/16/22 6:09 PM, olcott wrote:
On 1/16/2022 5:00 PM, Richard Damon wrote:
On 1/16/22 5:25 PM, olcott wrote:
On 1/16/2022 4:15 PM, Richard Damon wrote:
On 1/16/22 4:39 PM, olcott wrote:
On 1/16/2022 2:55 PM, Richard Damon wrote:
On 1/16/22 3:26 PM, olcott wrote:
On 1/16/2022 2:04 PM, Richard Damon wrote:
On 1/16/22 2:12 PM, olcott wrote:If the simulated input to embedded_H cannot possibly >>>>>>>>>>>>>>>> ever reach its final state then this conclusively proves >>>>>>>>>>>>>>>> that this input meets the Linz definition of a sequence >>>>>>>>>>>>>>>> of configuration that does not halt.
On 1/16/2022 1:00 PM, Richard Damon wrote: >>>>>>>>>>>>>>>>>>> On 1/16/22 1:11 PM, olcott wrote:Right IF the simulating Halt Decider never stopped >>>>>>>>>>>>>>>>> simulating, then H^ would never halt, but that is only >>>>>>>>>>>>>>>>> true IF H never aborts.
On 1/16/2022 11:48 AM, Richard Damon wrote: >>>>>>>>>>>>>>>>>>>>> On 1/16/22 11:05 AM, olcott wrote:
On 1/15/2022 4:26 PM, Richard Damon wrote: >>>>>>>>>>>>>>>>>>>>>>> On 1/15/22 4:47 PM, olcott wrote: >>>>>>>>>>>>>>>>>>>>>>>> Most people that try to form a rebuttal of my >>>>>>>>>>>>>>>>>>>>>>>> halting problem proof refutation lack sufficient >>>>>>>>>>>>>>>>>>>>>>>> basic understanding of the computer science >>>>>>>>>>>>>>>>>>>>>>>> involved.
No, your understanding is not sufficient for the >>>>>>>>>>>>>>>>>>>>>>> task.
The primary reason for this short-coming is that >>>>>>>>>>>>>>>>>>>>>>>> none of the textbook explanations of the halting >>>>>>>>>>>>>>>>>>>>>>>> problem are sufficiently precise. >>>>>>>>>>>>>>>>>>>>>>>
AND, that mapping MUST match the ACTUAL behavior >>>>>>>>>>>>>>>>>>>>>>> of the computation it is deciding on. >>>>>>>>>>>>>>>>>>>>>>>
Every decider computes the mapping from its >>>>>>>>>>>>>>>>>>>>>>>> input(s) to an accept or reject state. >>>>>>>>>>>>>>>>>>>>>>>>
A halt decider H computes the mapping from a P/I >>>>>>>>>>>>>>>>>>>>>>>> finite string pair
(where P is a machine description) to an accept >>>>>>>>>>>>>>>>>>>>>>>> or reject state.
H must compute this mapping on the basis of the >>>>>>>>>>>>>>>>>>>>>>>> actual behavior that P/I specifies. >>>>>>>>>>>>>>>>>>>>>>>
The most definite way to determine N steps of >>>>>>>>>>>>>>>>>>>>>>>> the behavior that P/I actually specifies is to >>>>>>>>>>>>>>>>>>>>>>>> perform a pure simulation of N steps of P/I. >>>>>>>>>>>>>>>>>>>>>>>>
Ĥ.q0 ⟨Ĥ⟩ ⊢* Ĥ.qx ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* Ĥ.qy ∞
Ĥ.q0 ⟨Ĥ⟩ ⊢* Ĥ.qx ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* Ĥ.qn >>>>>>>>>>>>>>>>>>>>>>>>
The copy of H at Ĥ.qx referred to as embedded_H >>>>>>>>>>>>>>>>>>>>>>>> must compute
the mapping from its own inputs: ⟨Ĥ⟩ ⟨Ĥ⟩ to Ĥ.qy
or Ĥ.qn.
It must do this on the basis of the actual >>>>>>>>>>>>>>>>>>>>>>>> behavior specified by these inputs. >>>>>>>>>>>>>>>>>>>>>>>>
The actual behavior specified by these inputs is >>>>>>>>>>>>>>>>>>>>>>>> the behavior of the pure simulation of N steps >>>>>>>>>>>>>>>>>>>>>>>> of ⟨Ĥ⟩ applied to ⟨Ĥ⟩ until: >>>>>>>>>>>>>>>>>>>>>>>> (a) The simulated ⟨Ĥ⟩ reaches its final state or >>>>>>>>>>>>>>>>>>>>>>>> (b) embedded_H recognizes that simulated ⟨Ĥ⟩ >>>>>>>>>>>>>>>>>>>>>>>> would never reach its final state. >>>>>>>>>>>>>>>>>>>>>>>>
WRONG. The actual behavior specifie by these >>>>>>>>>>>>>>>>>>>>>>> inputs is the behavior of the pure simulation >>>>>>>>>>>>>>>>>>>>>>> until it completes, or forever if it never halts. >>>>>>>>>>>>>>>>>>>>>>>
That is correct. In those cases where the input >>>>>>>>>>>>>>>>>>>>>> specifies an infinite sequence of configurations a >>>>>>>>>>>>>>>>>>>>>> halt decider either:
(a) Recognizes that this sequence would never >>>>>>>>>>>>>>>>>>>>>> reach its final state in any finite number of steps >>>>>>>>>>>>>>>>>>>>>> and aborts its simulation of this input >>>>>>>>>>>>>>>>>>>>>> and transitions to its reject state. > >>>>>>>>>>>>>>>>>>>>>> (b) Fails to be a decider at all.
computation that halts … the Turing machine will >>>>>>>>>>>>>>>>>>>>>> halt whenever it enters a final state. >>>>>>>>>>>>>>>>>>>>>> (Linz:1990:234)
According to Linz any sequence of configurations >>>>>>>>>>>>>>>>>>>>>> that would never reach its final state in any >>>>>>>>>>>>>>>>>>>>>> finite number of steps is a non halting sequence. >>>>>>>>>>>>>>>>>>>>>>
Except that as has been shown, if H aborts its >>>>>>>>>>>>>>>>>>>>> simulation and returns non-halting, then BY >>>>>>>>>>>>>>>>>>>>> CONSTRUCTION, H^ will halt. Thus, there exists no >>>>>>>>>>>>>>>>>>>>> finite sequence of states that correctly prove that >>>>>>>>>>>>>>>>>>>>> H^ will not halt.
For ANY finite number of states that H might >>>>>>>>>>>>>>>>>>>>> simulate the computation of H^ <H^>, and abort it >>>>>>>>>>>>>>>>>>>>> and return Non-Halting, there exists another finite >>>>>>>>>>>>>>>>>>>>> but larger number of states that H^ <H^> will halt in. >>>>>>>>>>>>>>>>>>>>>
You are confusing yourself with your own double talk. >>>>>>>>>>>>>>>>>>>>
If when embedded_H makes its decision the pure >>>>>>>>>>>>>>>>>>>> simulation of its own input cannot possibly reach >>>>>>>>>>>>>>>>>>>> any final state of this input in any finite number >>>>>>>>>>>>>>>>>>>> of steps then embedded_H is necessarily correct to >>>>>>>>>>>>>>>>>>>> abort the simulation of this input and transition to >>>>>>>>>>>>>>>>>>>> Ĥ.qn.
Once embedded_H has made this decision subsequent >>>>>>>>>>>>>>>>>>>> evaluation is cut off because Ĥ applied to ⟨Ĥ⟩ has >>>>>>>>>>>>>>>>>>>> stopped running.
WRONG.
H^ applied to <H^> can NEVER stop running until it >>>>>>>>>>>>>>>>>>> hits its final state.
THAT IS THE DEFINITION OF HALTING/Non-Halting. >>>>>>>>>>>>>>>>>>>
The fact that H (aka embedded_H) has aborted it >>>>>>>>>>>>>>>>>>> simulation of this string does NOT affect the actual >>>>>>>>>>>>>>>>>>> behavior of the string as the behavior is based on >>>>>>>>>>>>>>>>>>> what a REAL UTM does with it, not your 'fake' UTM >>>>>>>>>>>>>>>>>>> that aborts.
You already understand that if the simulating halt >>>>>>>>>>>>>>>>>> decider embedded_H never stopped simulating its input >>>>>>>>>>>>>>>>>> that its input would never reach its final state. >>>>>>>>>>>>>>>>>
There is no 'unless' here, either H does or it doesn't >>>>>>>>>>>>>>>>> abort its simulation. If H doesn't abort, then H^ in >>>>>>>>>>>>>>>>> non-halting.
You already understand that when a simulated input can >>>>>>>>>>>>>>>>>> never reach its final state that this input specifies >>>>>>>>>>>>>>>>>> a sequence of configurations that never halts. >>>>>>>>>>>>>>>>>>
Right, if the simulate input WHEN SIMULTED BY A >>>>>>>>>>>>>>>>> NON-ABORTING UTM, can never reach its final state, ths >>>>>>>>>>>>>>>>> input specifies a sequnce of configuration that never >>>>>>>>>>>>>>>>> halts.
If H aborts its simulation, then you no longer have any >>>>>>>>>>>>>>>>> 'proof' that the input doesn't halt, and your proof was >>>>>>>>>>>>>>>>> based on an H that never aborted its simulation, so it >>>>>>>>>>>>>>>>> isn't applicable here.
You don't seem to be able to put these two ideas >>>>>>>>>>>>>>>>>> together.
Because you are making incompatible assumptions. >>>>>>>>>>>>>>>>
WRONG. That applies only IF you define your H to actually >>>>>>>>>>>>>>> BE a UTM, and yes, if H IS a UTM, then H^ is non-halting, >>>>>>>>>>>>>>> but H also doesn't answer, so fails to be a correct decider. >>>>>>>>>>>>>>>
So, your system only meets the requirements for a >>>>>>>>>>>>>>> configuration that does not halt if H doesn't abort its >>>>>>>>>>>>>>> simulation.
Because the simulated input to embedded_H cannot possibly >>>>>>>>>>>>>> ever reach its final state whether or not embedded_H >>>>>>>>>>>>>> aborts its simulation then we know that this input meet >>>>>>>>>>>>>> the Linz definition of a sequence of configurations that >>>>>>>>>>>>>> does not halt.
NO, WE DON'T.
It only meet the requirement if H doesn't abort.
The fact that an aborted simulation doesn't reach its final >>>>>>>>>>>>> state does NOT say that the input would never reach a final >>>>>>>>>>>>> state if it was simulated farther.
So, yes, you have proven that if you H is defined as a >>>>>>>>>>>>> simulator that never aborts its simulation, then H^ will be >>>>>>>>>>>>> a non-halting computation and the correct answer for a >>>>>>>>>>>>> Halting Decider would be non-halting, but by the conditions >>>>>>>>>>>>> you just imposed on H to prove that, H can not give that >>>>>>>>>>>>> answer. Once you remove the constraint on H that it never >>>>>>>>>>>>> aborts its simulation, then your proof for the new H^ that >>>>>>>>>>>>> is created from this new H becomes invalid and doesn't >>>>>>>>>>>>> actually prove anything like what you want. At best it >>>>>>>>>>>>> proves that H can never actually prove that H^ is halting >>>>>>>>>>>>> (not that it isn't halting, just that H can't actually >>>>>>>>>>>>> prove it).
If halting was defined as "does not keep running forever" >>>>>>>>>>>>>> then you would be right as soon as embedded_H aborts its >>>>>>>>>>>>>> simulation then its input halts. Because this is not the >>>>>>>>>>>>>> way that halting is defined you are wrong.
WRONG. Linz definition refers to the ACTUAL running of the >>>>>>>>>>>>> machine, not its simulation by a partial simulator.
Just because H has aborted its simulation does NOT mean >>>>>>>>>>>>> that if the input was actually simulated by a UTM it would >>>>>>>>>>>>> not reach that final state.
The fact that the input to embedded_H demonstrates an
infinitely repeating pattern that can be recognized by >>>>>>>>>>>> embedded_H as infinitely repeating is what provides
embedded_H with its "never reaches its final state" halt >>>>>>>>>>>> status criterion measure.
But if H 'recognizes' it as an infinitely repeating pattern >>>>>>>>>>> and goes to H.Qn then the input it is looking at is KNOWN to >>>>>>>>>>> Halt,
Not at all.
Ĥ.q0 ⟨Ĥ⟩ ⊢* Ĥ.qx ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* Ĥ.qn
If and ONLY if H <H^> <H^> says Non-Halting.
The computation that embedded_H is a part of halts. The
computation specified by the simulated input is aborted before >>>>>>>>>> it ever gets past Ĥ.qx thus never reaches its own final state >>>>>>>>>> thus (according to Linz) never halts.
WRONG. Do you mean part of 'H'? (there is not 'halts' that you >>>>>>>>> have currently defined as a Turing Machine)
Remember, your requirement on H was H wM w -> H.Qn iff M w
never Halts (and -> H.Qy iff M w Halts).
This wasn't if the partial simulation of wM w never reached a >>>>>>>>> final state, but if the ACTUAL machine M applied to w does.
The issue is that the test of H^ <H^> Halting or not is NOT
based on the processing that H does on it, but what it does as >>>>>>>>> an independent entity, either what UTM(<H^>,<H^>) does or what >>>>>>>>> H^ <H^> does.
In both of these cases, that top level H^ being processed is >>>>>>>>> NOT 'aborted' by H (maybe what you call halts) and it will
continue on till it reaches that same H^.Qn and Halt, and thus >>>>>>>>> show that H^ <H^> is a halting computation.
Your probably next claim that H can't be responsible for the >>>>>>>>> actual machine because it wasn't the input isn't correct, it >>>>>>>>> can't use the actual machine to do its computation, but it IS >>>>>>>>> responsible for the behavior of that machine if it wants to
claim to compute the Halting Function which IS dependent on
that actual machine, for which it just gets a representation of. >>>>>>>>>
embedded_H computes the mapping from its input finite strings
⟨Ĥ⟩ ⟨Ĥ⟩ to Ĥ.qy or Ĥ.qn based on what the behavior of this
input would if embedded_H would continue to simulate this input >>>>>>>> forever.
Which is incorrect the way you do it, It needs to determine what >>>>>>> the input would do based on the copy of H embedded in H^ doing
what all copies of H will do. PERIOD. ASSUMING that the copy of H >>>>>>> embedded in H^ will continue simulating forever just makes an ASS >>>>>>> out of U, because that is NOT what it will do.
None of the copies of embedded_H do anything besides simulate
their input until the outermost copy recognizes the infinitely
repeating pattern.
But what would they do AFTER that? Won't they also abort their own
simulation?
When embedded_H recognizes that its input matches an infinite
behavior pattern it immediately stops simulating this input thus
terminating the entire call chain.
Not the part of the chain that is CALLING it.
You simply don't know enough computer science to understand that your
objection is totally irrelevant.
embedded_H is only accountable for computing the mapping from ⟨Ĥ⟩ ⟨Ĥ⟩
to Ĥ.qy and Ĥ.qn.
Everything else in the universe it totally irrelevant to the
correctness of the halt status decision of embedded_H.
No, it is accountable to compute the RIGHT answer per the
specifications. I mentioned this previously, and you have just ignored
this error of yours.
If you aren't using the official Halting Problem Specifications then you
are just talking about POOP.
The Official Halting Problem Specifications say that H applied to input
wM w needs to answer Halting (by going to H.Qy) for H applied to wM w if
and only if M applied to w will Halt in some finite time and to answer Non-Halting (by going to H.Qn) if M applied to w will NEVER Halt.
Since H^ w is designed so it will Halt if H w w goes to H.Qn and to loop forever if H w w goes to H.Qy, then we have that if H <H^> <H^> goes to
H.Qn as you claim, then H^ <H^> will by construction Halt, and thus H
failed to meet its requriements, since it said Non-Halting for a
computation that clearly Halted.
On 1/16/22 9:54 PM, olcott wrote:
On 1/16/2022 6:46 PM, Richard Damon wrote:
On 1/16/22 7:16 PM, olcott wrote:
On 1/16/2022 6:12 PM, Richard Damon wrote:
On 1/16/22 6:57 PM, olcott wrote:
On 1/16/2022 5:47 PM, Richard Damon wrote:
On 1/16/22 6:09 PM, olcott wrote:
On 1/16/2022 5:00 PM, Richard Damon wrote:
On 1/16/22 5:25 PM, olcott wrote:Not at all.
On 1/16/2022 4:15 PM, Richard Damon wrote:
On 1/16/22 4:39 PM, olcott wrote:
On 1/16/2022 2:55 PM, Richard Damon wrote:NO, WE DON'T.
On 1/16/22 3:26 PM, olcott wrote:
On 1/16/2022 2:04 PM, Richard Damon wrote:
On 1/16/22 2:12 PM, olcott wrote:
On 1/16/2022 1:00 PM, Richard Damon wrote:Right IF the simulating Halt Decider never stopped >>>>>>>>>>>>>>> simulating, then H^ would never halt, but that is only >>>>>>>>>>>>>>> true IF H never aborts.
On 1/16/22 1:11 PM, olcott wrote:
On 1/16/2022 11:48 AM, Richard Damon wrote: >>>>>>>>>>>>>>>>>>> On 1/16/22 11:05 AM, olcott wrote:
On 1/15/2022 4:26 PM, Richard Damon wrote: >>>>>>>>>>>>>>>>>>>>> On 1/15/22 4:47 PM, olcott wrote:
Most people that try to form a rebuttal of my >>>>>>>>>>>>>>>>>>>>>> halting problem proof refutation lack sufficient >>>>>>>>>>>>>>>>>>>>>> basic understanding of the computer science involved. >>>>>>>>>>>>>>>>>>>>>>
The primary reason for this short-coming is that >>>>>>>>>>>>>>>>>>>>>> none of the textbook explanations of the halting >>>>>>>>>>>>>>>>>>>>>> problem are sufficiently precise.
No, your understanding is not sufficient for the task. >>>>>>>>>>>>>>>>>>>>>
AND, that mapping MUST match the ACTUAL behavior of >>>>>>>>>>>>>>>>>>>>> the computation it is deciding on.
Every decider computes the mapping from its >>>>>>>>>>>>>>>>>>>>>> input(s) to an accept or reject state. >>>>>>>>>>>>>>>>>>>>>>
A halt decider H computes the mapping from a P/I >>>>>>>>>>>>>>>>>>>>>> finite string pair
(where P is a machine description) to an accept or >>>>>>>>>>>>>>>>>>>>>> reject state.
H must compute this mapping on the basis of the >>>>>>>>>>>>>>>>>>>>>> actual behavior that P/I specifies. >>>>>>>>>>>>>>>>>>>>>
The most definite way to determine N steps of the >>>>>>>>>>>>>>>>>>>>>> behavior that P/I actually specifies is to perform >>>>>>>>>>>>>>>>>>>>>> a pure simulation of N steps of P/I. >>>>>>>>>>>>>>>>>>>>>>
Ĥ.q0 ⟨Ĥ⟩ ⊢* Ĥ.qx ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* Ĥ.qy ∞
Ĥ.q0 ⟨Ĥ⟩ ⊢* Ĥ.qx ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* Ĥ.qn >>>>>>>>>>>>>>>>>>>>>>
The copy of H at Ĥ.qx referred to as embedded_H >>>>>>>>>>>>>>>>>>>>>> must compute
the mapping from its own inputs: ⟨Ĥ⟩ ⟨Ĥ⟩ to Ĥ.qy
or Ĥ.qn.
It must do this on the basis of the actual >>>>>>>>>>>>>>>>>>>>>> behavior specified by these inputs. >>>>>>>>>>>>>>>>>>>>>>
The actual behavior specified by these inputs is >>>>>>>>>>>>>>>>>>>>>> the behavior of the pure simulation of N steps of >>>>>>>>>>>>>>>>>>>>>> ⟨Ĥ⟩ applied to ⟨Ĥ⟩ until: >>>>>>>>>>>>>>>>>>>>>> (a) The simulated ⟨Ĥ⟩ reaches its final state or >>>>>>>>>>>>>>>>>>>>>> (b) embedded_H recognizes that simulated ⟨Ĥ⟩ would >>>>>>>>>>>>>>>>>>>>>> never reach its final state.
WRONG. The actual behavior specifie by these inputs >>>>>>>>>>>>>>>>>>>>> is the behavior of the pure simulation until it >>>>>>>>>>>>>>>>>>>>> completes, or forever if it never halts. >>>>>>>>>>>>>>>>>>>>>
That is correct. In those cases where the input >>>>>>>>>>>>>>>>>>>> specifies an infinite sequence of configurations a >>>>>>>>>>>>>>>>>>>> halt decider either:
(a) Recognizes that this sequence would never reach >>>>>>>>>>>>>>>>>>>> its final state in any finite number of steps >>>>>>>>>>>>>>>>>>>> and aborts its simulation of this input >>>>>>>>>>>>>>>>>>>> and transitions to its reject state. > >>>>>>>>>>>>>>>>>>>> (b) Fails to be a decider at all.
computation that halts … the Turing machine will >>>>>>>>>>>>>>>>>>>> halt whenever it enters a final state. (Linz:1990:234) >>>>>>>>>>>>>>>>>>>>
According to Linz any sequence of configurations >>>>>>>>>>>>>>>>>>>> that would never reach its final state in any finite >>>>>>>>>>>>>>>>>>>> number of steps is a non halting sequence. >>>>>>>>>>>>>>>>>>>>
Except that as has been shown, if H aborts its >>>>>>>>>>>>>>>>>>> simulation and returns non-halting, then BY >>>>>>>>>>>>>>>>>>> CONSTRUCTION, H^ will halt. Thus, there exists no >>>>>>>>>>>>>>>>>>> finite sequence of states that correctly prove that >>>>>>>>>>>>>>>>>>> H^ will not halt.
For ANY finite number of states that H might simulate >>>>>>>>>>>>>>>>>>> the computation of H^ <H^>, and abort it and return >>>>>>>>>>>>>>>>>>> Non-Halting, there exists another finite but larger >>>>>>>>>>>>>>>>>>> number of states that H^ <H^> will halt in. >>>>>>>>>>>>>>>>>>>
You are confusing yourself with your own double talk. >>>>>>>>>>>>>>>>>>
If when embedded_H makes its decision the pure >>>>>>>>>>>>>>>>>> simulation of its own input cannot possibly reach any >>>>>>>>>>>>>>>>>> final state of this input in any finite number of >>>>>>>>>>>>>>>>>> steps then embedded_H is necessarily correct to abort >>>>>>>>>>>>>>>>>> the simulation of this input and transition to Ĥ.qn. >>>>>>>>>>>>>>>>>>
Once embedded_H has made this decision subsequent >>>>>>>>>>>>>>>>>> evaluation is cut off because Ĥ applied to ⟨Ĥ⟩ has >>>>>>>>>>>>>>>>>> stopped running.
WRONG.
H^ applied to <H^> can NEVER stop running until it hits >>>>>>>>>>>>>>>>> its final state.
THAT IS THE DEFINITION OF HALTING/Non-Halting. >>>>>>>>>>>>>>>>>
The fact that H (aka embedded_H) has aborted it >>>>>>>>>>>>>>>>> simulation of this string does NOT affect the actual >>>>>>>>>>>>>>>>> behavior of the string as the behavior is based on what >>>>>>>>>>>>>>>>> a REAL UTM does with it, not your 'fake' UTM that aborts. >>>>>>>>>>>>>>>>>
You already understand that if the simulating halt >>>>>>>>>>>>>>>> decider embedded_H never stopped simulating its input >>>>>>>>>>>>>>>> that its input would never reach its final state. >>>>>>>>>>>>>>>
There is no 'unless' here, either H does or it doesn't >>>>>>>>>>>>>>> abort its simulation. If H doesn't abort, then H^ in >>>>>>>>>>>>>>> non-halting.
You already understand that when a simulated input can >>>>>>>>>>>>>>>> never reach its final state that this input specifies a >>>>>>>>>>>>>>>> sequence of configurations that never halts.
Right, if the simulate input WHEN SIMULTED BY A
NON-ABORTING UTM, can never reach its final state, ths >>>>>>>>>>>>>>> input specifies a sequnce of configuration that never halts. >>>>>>>>>>>>>>>
If H aborts its simulation, then you no longer have any >>>>>>>>>>>>>>> 'proof' that the input doesn't halt, and your proof was >>>>>>>>>>>>>>> based on an H that never aborted its simulation, so it >>>>>>>>>>>>>>> isn't applicable here.
You don't seem to be able to put these two ideas together. >>>>>>>>>>>>>>>Because you are making incompatible assumptions.
If the simulated input to embedded_H cannot possibly ever >>>>>>>>>>>>>> reach its final state then this conclusively proves that >>>>>>>>>>>>>> this input meets the Linz definition of a sequence of >>>>>>>>>>>>>> configuration that does not halt.
WRONG. That applies only IF you define your H to actually >>>>>>>>>>>>> BE a UTM, and yes, if H IS a UTM, then H^ is non-halting, >>>>>>>>>>>>> but H also doesn't answer, so fails to be a correct decider. >>>>>>>>>>>>>
So, your system only meets the requirements for a
configuration that does not halt if H doesn't abort its >>>>>>>>>>>>> simulation.
Because the simulated input to embedded_H cannot possibly >>>>>>>>>>>> ever reach its final state whether or not embedded_H aborts >>>>>>>>>>>> its simulation then we know that this input meet the Linz >>>>>>>>>>>> definition of a sequence of configurations that does not halt. >>>>>>>>>>>
It only meet the requirement if H doesn't abort.
The fact that an aborted simulation doesn't reach its final >>>>>>>>>>> state does NOT say that the input would never reach a final >>>>>>>>>>> state if it was simulated farther.
So, yes, you have proven that if you H is defined as a
simulator that never aborts its simulation, then H^ will be a >>>>>>>>>>> non-halting computation and the correct answer for a Halting >>>>>>>>>>> Decider would be non-halting, but by the conditions you just >>>>>>>>>>> imposed on H to prove that, H can not give that answer. Once >>>>>>>>>>> you remove the constraint on H that it never aborts its
simulation, then your proof for the new H^ that is created >>>>>>>>>>> from this new H becomes invalid and doesn't actually prove >>>>>>>>>>> anything like what you want. At best it proves that H can >>>>>>>>>>> never actually prove that H^ is halting (not that it isn't >>>>>>>>>>> halting, just that H can't actually prove it).
If halting was defined as "does not keep running forever" >>>>>>>>>>>> then you would be right as soon as embedded_H aborts its >>>>>>>>>>>> simulation then its input halts. Because this is not the way >>>>>>>>>>>> that halting is defined you are wrong.
WRONG. Linz definition refers to the ACTUAL running of the >>>>>>>>>>> machine, not its simulation by a partial simulator.
Just because H has aborted its simulation does NOT mean that >>>>>>>>>>> if the input was actually simulated by a UTM it would not >>>>>>>>>>> reach that final state.
The fact that the input to embedded_H demonstrates an
infinitely repeating pattern that can be recognized by
embedded_H as infinitely repeating is what provides embedded_H >>>>>>>>>> with its "never reaches its final state" halt status criterion >>>>>>>>>> measure.
But if H 'recognizes' it as an infinitely repeating pattern and >>>>>>>>> goes to H.Qn then the input it is looking at is KNOWN to Halt, >>>>>>>>
Ĥ.q0 ⟨Ĥ⟩ ⊢* Ĥ.qx ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* Ĥ.qn
If and ONLY if H <H^> <H^> says Non-Halting.
The computation that embedded_H is a part of halts. The
computation specified by the simulated input is aborted before >>>>>>>> it ever gets past Ĥ.qx thus never reaches its own final state >>>>>>>> thus (according to Linz) never halts.
WRONG. Do you mean part of 'H'? (there is not 'halts' that you
have currently defined as a Turing Machine)
Remember, your requirement on H was H wM w -> H.Qn iff M w never >>>>>>> Halts (and -> H.Qy iff M w Halts).
This wasn't if the partial simulation of wM w never reached a
final state, but if the ACTUAL machine M applied to w does.
The issue is that the test of H^ <H^> Halting or not is NOT based >>>>>>> on the processing that H does on it, but what it does as an
independent entity, either what UTM(<H^>,<H^>) does or what H^
<H^> does.
In both of these cases, that top level H^ being processed is NOT >>>>>>> 'aborted' by H (maybe what you call halts) and it will continue
on till it reaches that same H^.Qn and Halt, and thus show that
H^ <H^> is a halting computation.
Your probably next claim that H can't be responsible for the
actual machine because it wasn't the input isn't correct, it
can't use the actual machine to do its computation, but it IS
responsible for the behavior of that machine if it wants to claim >>>>>>> to compute the Halting Function which IS dependent on that actual >>>>>>> machine, for which it just gets a representation of.
embedded_H computes the mapping from its input finite strings ⟨Ĥ⟩ >>>>>> ⟨Ĥ⟩ to Ĥ.qy or Ĥ.qn based on what the behavior of this input >>>>>> would if embedded_H would continue to simulate this input forever.
Which is incorrect the way you do it, It needs to determine what
the input would do based on the copy of H embedded in H^ doing what
all copies of H will do. PERIOD. ASSUMING that the copy of H
embedded in H^ will continue simulating forever just makes an ASS
out of U, because that is NOT what it will do.
None of the copies of embedded_H do anything besides simulate their
input until the outermost copy recognizes the infinitely repeating
pattern.
But what would they do AFTER that? Won't they also abort their own
simulation?
When embedded_H recognizes that its input matches an infinite behavior
pattern it immediately stops simulating this input thus terminating
the entire call chain.
Not the part of the chain that is CALLING it.
On 1/16/22 11:43 PM, olcott wrote:
On 1/16/2022 10:35 PM, Richard Damon wrote:
On 1/16/22 11:20 PM, olcott wrote:
On 1/16/2022 10:13 PM, Richard Damon wrote:
On 1/16/22 11:00 PM, olcott wrote:
On 1/16/2022 9:48 PM, Richard Damon wrote:
On 1/16/22 10:26 PM, olcott wrote:
On 1/16/2022 9:01 PM, Richard Damon wrote:
On 1/16/22 9:54 PM, olcott wrote:
On 1/16/2022 6:46 PM, Richard Damon wrote:
On 1/16/22 7:16 PM, olcott wrote:
On 1/16/2022 6:12 PM, Richard Damon wrote:
On 1/16/22 6:57 PM, olcott wrote:
On 1/16/2022 5:47 PM, Richard Damon wrote:
On 1/16/22 6:09 PM, olcott wrote:
On 1/16/2022 5:00 PM, Richard Damon wrote:If and ONLY if H <H^> <H^> says Non-Halting.
On 1/16/22 5:25 PM, olcott wrote:
On 1/16/2022 4:15 PM, Richard Damon wrote: >>>>>>>>>>>>>>>>>>> On 1/16/22 4:39 PM, olcott wrote:
On 1/16/2022 2:55 PM, Richard Damon wrote: >>>>>>>>>>>>>>>>>>>>> On 1/16/22 3:26 PM, olcott wrote:
On 1/16/2022 2:04 PM, Richard Damon wrote: >>>>>>>>>>>>>>>>>>>>>>> On 1/16/22 2:12 PM, olcott wrote: >>>>>>>>>>>>>>>>>>>>>>>> On 1/16/2022 1:00 PM, Richard Damon wrote: >>>>>>>>>>>>>>>>>>>>>>>>> On 1/16/22 1:11 PM, olcott wrote: >>>>>>>>>>>>>>>>>>>>>>>>>> On 1/16/2022 11:48 AM, Richard Damon wrote: >>>>>>>>>>>>>>>>>>>>>>>>>>> On 1/16/22 11:05 AM, olcott wrote: >>>>>>>>>>>>>>>>>>>>>>>>>>>> On 1/15/2022 4:26 PM, Richard Damon wrote: >>>>>>>>>>>>>>>>>>>>>>>>>>>>> On 1/15/22 4:47 PM, olcott wrote: >>>>>>>>>>>>>>>>>>>>>>>>>>>>>> Most people that try to form a rebuttal of >>>>>>>>>>>>>>>>>>>>>>>>>>>>>> my halting problem proof refutation lack >>>>>>>>>>>>>>>>>>>>>>>>>>>>>> sufficient basic understanding of the >>>>>>>>>>>>>>>>>>>>>>>>>>>>>> computer science involved. >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
If the simulated input to embedded_H cannot >>>>>>>>>>>>>>>>>>>>>> possibly ever reach its final state then this >>>>>>>>>>>>>>>>>>>>>> conclusively proves that this input meets the Linz >>>>>>>>>>>>>>>>>>>>>> definition of a sequence of configuration that >>>>>>>>>>>>>>>>>>>>>> does not halt.WRONG.The primary reason for this short-coming >>>>>>>>>>>>>>>>>>>>>>>>>>>>>> is that none of the textbook explanations >>>>>>>>>>>>>>>>>>>>>>>>>>>>>> of the halting problem are sufficiently >>>>>>>>>>>>>>>>>>>>>>>>>>>>>> precise.
No, your understanding is not sufficient >>>>>>>>>>>>>>>>>>>>>>>>>>>>> for the task.
AND, that mapping MUST match the ACTUAL >>>>>>>>>>>>>>>>>>>>>>>>>>>>> behavior of the computation it is deciding on. >>>>>>>>>>>>>>>>>>>>>>>>>>>>>
Every decider computes the mapping from >>>>>>>>>>>>>>>>>>>>>>>>>>>>>> its input(s) to an accept or reject state. >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
A halt decider H computes the mapping from >>>>>>>>>>>>>>>>>>>>>>>>>>>>>> a P/I finite string pair >>>>>>>>>>>>>>>>>>>>>>>>>>>>>> (where P is a machine description) to an >>>>>>>>>>>>>>>>>>>>>>>>>>>>>> accept or reject state. >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
H must compute this mapping on the basis >>>>>>>>>>>>>>>>>>>>>>>>>>>>>> of the actual behavior that P/I specifies. >>>>>>>>>>>>>>>>>>>>>>>>>>>>>
The most definite way to determine N steps >>>>>>>>>>>>>>>>>>>>>>>>>>>>>> of the behavior that P/I actually >>>>>>>>>>>>>>>>>>>>>>>>>>>>>> specifies is to perform a pure simulation >>>>>>>>>>>>>>>>>>>>>>>>>>>>>> of N steps of P/I. >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
Ĥ.q0 ⟨Ĥ⟩ ⊢* Ĥ.qx ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* Ĥ.qy ∞
Ĥ.q0 ⟨Ĥ⟩ ⊢* Ĥ.qx ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* Ĥ.qn
The copy of H at Ĥ.qx referred to as >>>>>>>>>>>>>>>>>>>>>>>>>>>>>> embedded_H must compute >>>>>>>>>>>>>>>>>>>>>>>>>>>>>> the mapping from its own inputs: ⟨Ĥ⟩ ⟨Ĥ⟩
to Ĥ.qy or Ĥ.qn. >>>>>>>>>>>>>>>>>>>>>>>>>>>>>> It must do this on the basis of the actual >>>>>>>>>>>>>>>>>>>>>>>>>>>>>> behavior specified by these inputs. >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
The actual behavior specified by these >>>>>>>>>>>>>>>>>>>>>>>>>>>>>> inputs is the behavior of the pure >>>>>>>>>>>>>>>>>>>>>>>>>>>>>> simulation of N steps of ⟨Ĥ⟩ applied to >>>>>>>>>>>>>>>>>>>>>>>>>>>>>> ⟨Ĥ⟩ until:
(a) The simulated ⟨Ĥ⟩ reaches its final >>>>>>>>>>>>>>>>>>>>>>>>>>>>>> state or
(b) embedded_H recognizes that simulated >>>>>>>>>>>>>>>>>>>>>>>>>>>>>> ⟨Ĥ⟩ would never reach its final state. >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
WRONG. The actual behavior specifie by >>>>>>>>>>>>>>>>>>>>>>>>>>>>> these inputs is the behavior of the pure >>>>>>>>>>>>>>>>>>>>>>>>>>>>> simulation until it completes, or forever >>>>>>>>>>>>>>>>>>>>>>>>>>>>> if it never halts.
That is correct. In those cases where the >>>>>>>>>>>>>>>>>>>>>>>>>>>> input specifies an infinite sequence of >>>>>>>>>>>>>>>>>>>>>>>>>>>> configurations a halt decider either: >>>>>>>>>>>>>>>>>>>>>>>>>>>>
(a) Recognizes that this sequence would >>>>>>>>>>>>>>>>>>>>>>>>>>>> never reach its final state in any finite >>>>>>>>>>>>>>>>>>>>>>>>>>>> number of steps
and aborts its simulation of this input >>>>>>>>>>>>>>>>>>>>>>>>>>>> and transitions to its reject state. > >>>>>>>>>>>>>>>>>>>>>>>>>>>> (b) Fails to be a decider at all. >>>>>>>>>>>>>>>>>>>>>>>>>>>>
computation that halts … the Turing machine >>>>>>>>>>>>>>>>>>>>>>>>>>>> will halt whenever it enters a final state. >>>>>>>>>>>>>>>>>>>>>>>>>>>> (Linz:1990:234)
According to Linz any sequence of >>>>>>>>>>>>>>>>>>>>>>>>>>>> configurations that would never reach its >>>>>>>>>>>>>>>>>>>>>>>>>>>> final state in any finite number of steps is >>>>>>>>>>>>>>>>>>>>>>>>>>>> a non halting sequence. >>>>>>>>>>>>>>>>>>>>>>>>>>>>
Except that as has been shown, if H aborts >>>>>>>>>>>>>>>>>>>>>>>>>>> its simulation and returns non-halting, then >>>>>>>>>>>>>>>>>>>>>>>>>>> BY CONSTRUCTION, H^ will halt. Thus, there >>>>>>>>>>>>>>>>>>>>>>>>>>> exists no finite sequence of states that >>>>>>>>>>>>>>>>>>>>>>>>>>> correctly prove that H^ will not halt. >>>>>>>>>>>>>>>>>>>>>>>>>>>
For ANY finite number of states that H might >>>>>>>>>>>>>>>>>>>>>>>>>>> simulate the computation of H^ <H^>, and >>>>>>>>>>>>>>>>>>>>>>>>>>> abort it and return Non-Halting, there exists >>>>>>>>>>>>>>>>>>>>>>>>>>> another finite but larger number of states >>>>>>>>>>>>>>>>>>>>>>>>>>> that H^ <H^> will halt in. >>>>>>>>>>>>>>>>>>>>>>>>>>>
You are confusing yourself with your own >>>>>>>>>>>>>>>>>>>>>>>>>> double talk.
If when embedded_H makes its decision the pure >>>>>>>>>>>>>>>>>>>>>>>>>> simulation of its own input cannot possibly >>>>>>>>>>>>>>>>>>>>>>>>>> reach any final state of this input in any >>>>>>>>>>>>>>>>>>>>>>>>>> finite number of steps then embedded_H is >>>>>>>>>>>>>>>>>>>>>>>>>> necessarily correct to abort the simulation of >>>>>>>>>>>>>>>>>>>>>>>>>> this input and transition to Ĥ.qn. >>>>>>>>>>>>>>>>>>>>>>>>>>
Once embedded_H has made this decision >>>>>>>>>>>>>>>>>>>>>>>>>> subsequent evaluation is cut off because Ĥ >>>>>>>>>>>>>>>>>>>>>>>>>> applied to ⟨Ĥ⟩ has stopped running. >>>>>>>>>>>>>>>>>>>>>>>>>
H^ applied to <H^> can NEVER stop running until >>>>>>>>>>>>>>>>>>>>>>>>> it hits its final state.
THAT IS THE DEFINITION OF HALTING/Non-Halting. >>>>>>>>>>>>>>>>>>>>>>>>>
The fact that H (aka embedded_H) has aborted >>>>>>>>>>>>>>>>>>>>>>>>> it simulation of this string does NOT affect >>>>>>>>>>>>>>>>>>>>>>>>> the actual behavior of the string as the >>>>>>>>>>>>>>>>>>>>>>>>> behavior is based on what a REAL UTM does with >>>>>>>>>>>>>>>>>>>>>>>>> it, not your 'fake' UTM that aborts. >>>>>>>>>>>>>>>>>>>>>>>>>
You already understand that if the simulating >>>>>>>>>>>>>>>>>>>>>>>> halt decider embedded_H never stopped simulating >>>>>>>>>>>>>>>>>>>>>>>> its input that its input would never reach its >>>>>>>>>>>>>>>>>>>>>>>> final state.
Right IF the simulating Halt Decider never >>>>>>>>>>>>>>>>>>>>>>> stopped simulating, then H^ would never halt, but >>>>>>>>>>>>>>>>>>>>>>> that is only true IF H never aborts. >>>>>>>>>>>>>>>>>>>>>>>
There is no 'unless' here, either H does or it >>>>>>>>>>>>>>>>>>>>>>> doesn't abort its simulation. If H doesn't abort, >>>>>>>>>>>>>>>>>>>>>>> then H^ in non-halting.
You already understand that when a simulated >>>>>>>>>>>>>>>>>>>>>>>> input can never reach its final state that this >>>>>>>>>>>>>>>>>>>>>>>> input specifies a sequence of configurations >>>>>>>>>>>>>>>>>>>>>>>> that never halts.
Right, if the simulate input WHEN SIMULTED BY A >>>>>>>>>>>>>>>>>>>>>>> NON-ABORTING UTM, can never reach its final >>>>>>>>>>>>>>>>>>>>>>> state, ths input specifies a sequnce of >>>>>>>>>>>>>>>>>>>>>>> configuration that never halts.
If H aborts its simulation, then you no longer >>>>>>>>>>>>>>>>>>>>>>> have any 'proof' that the input doesn't halt, and >>>>>>>>>>>>>>>>>>>>>>> your proof was based on an H that never aborted >>>>>>>>>>>>>>>>>>>>>>> its simulation, so it isn't applicable here. >>>>>>>>>>>>>>>>>>>>>>>
You don't seem to be able to put these two ideas >>>>>>>>>>>>>>>>>>>>>>>> together.
Because you are making incompatible assumptions. >>>>>>>>>>>>>>>>>>>>>>
WRONG. That applies only IF you define your H to >>>>>>>>>>>>>>>>>>>>> actually BE a UTM, and yes, if H IS a UTM, then H^ >>>>>>>>>>>>>>>>>>>>> is non-halting, but H also doesn't answer, so fails >>>>>>>>>>>>>>>>>>>>> to be a correct decider.
So, your system only meets the requirements for a >>>>>>>>>>>>>>>>>>>>> configuration that does not halt if H doesn't abort >>>>>>>>>>>>>>>>>>>>> its simulation.
Because the simulated input to embedded_H cannot >>>>>>>>>>>>>>>>>>>> possibly ever reach its final state whether or not >>>>>>>>>>>>>>>>>>>> embedded_H aborts its simulation then we know that >>>>>>>>>>>>>>>>>>>> this input meet the Linz definition of a sequence of >>>>>>>>>>>>>>>>>>>> configurations that does not halt.
NO, WE DON'T.
It only meet the requirement if H doesn't abort. >>>>>>>>>>>>>>>>>>>
The fact that an aborted simulation doesn't reach its >>>>>>>>>>>>>>>>>>> final state does NOT say that the input would never >>>>>>>>>>>>>>>>>>> reach a final state if it was simulated farther. >>>>>>>>>>>>>>>>>>>
So, yes, you have proven that if you H is defined as >>>>>>>>>>>>>>>>>>> a simulator that never aborts its simulation, then H^ >>>>>>>>>>>>>>>>>>> will be a non-halting computation and the correct >>>>>>>>>>>>>>>>>>> answer for a Halting Decider would be non-halting, >>>>>>>>>>>>>>>>>>> but by the conditions you just imposed on H to prove >>>>>>>>>>>>>>>>>>> that, H can not give that answer. Once you remove the >>>>>>>>>>>>>>>>>>> constraint on H that it never aborts its simulation, >>>>>>>>>>>>>>>>>>> then your proof for the new H^ that is created from >>>>>>>>>>>>>>>>>>> this new H becomes invalid and doesn't actually prove >>>>>>>>>>>>>>>>>>> anything like what you want. At best it proves that H >>>>>>>>>>>>>>>>>>> can never actually prove that H^ is halting (not that >>>>>>>>>>>>>>>>>>> it isn't halting, just that H can't actually prove it). >>>>>>>>>>>>>>>>>>>
If halting was defined as "does not keep running >>>>>>>>>>>>>>>>>>>> forever" then you would be right as soon as >>>>>>>>>>>>>>>>>>>> embedded_H aborts its simulation then its input >>>>>>>>>>>>>>>>>>>> halts. Because this is not the way that halting is >>>>>>>>>>>>>>>>>>>> defined you are wrong.
WRONG. Linz definition refers to the ACTUAL running >>>>>>>>>>>>>>>>>>> of the machine, not its simulation by a partial >>>>>>>>>>>>>>>>>>> simulator.
Just because H has aborted its simulation does NOT >>>>>>>>>>>>>>>>>>> mean that if the input was actually simulated by a >>>>>>>>>>>>>>>>>>> UTM it would not reach that final state. >>>>>>>>>>>>>>>>>>>
The fact that the input to embedded_H demonstrates an >>>>>>>>>>>>>>>>>> infinitely repeating pattern that can be recognized by >>>>>>>>>>>>>>>>>> embedded_H as infinitely repeating is what provides >>>>>>>>>>>>>>>>>> embedded_H with its "never reaches its final state" >>>>>>>>>>>>>>>>>> halt status criterion measure.
But if H 'recognizes' it as an infinitely repeating >>>>>>>>>>>>>>>>> pattern and goes to H.Qn then the input it is looking >>>>>>>>>>>>>>>>> at is KNOWN to Halt,
Not at all.
Ĥ.q0 ⟨Ĥ⟩ ⊢* Ĥ.qx ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* Ĥ.qn >>>>>>>>>>>>>>>
WRONG. Do you mean part of 'H'? (there is not 'halts' >>>>>>>>>>>>>>> that you have currently defined as a Turing Machine) >>>>>>>>>>>>>>>
The computation that embedded_H is a part of halts. The >>>>>>>>>>>>>>>> computation specified by the simulated input is aborted >>>>>>>>>>>>>>>> before it ever gets past Ĥ.qx thus never reaches its own >>>>>>>>>>>>>>>> final state thus (according to Linz) never halts. >>>>>>>>>>>>>>>
Remember, your requirement on H was H wM w -> H.Qn iff M >>>>>>>>>>>>>>> w never Halts (and -> H.Qy iff M w Halts).
This wasn't if the partial simulation of wM w never >>>>>>>>>>>>>>> reached a final state, but if the ACTUAL machine M >>>>>>>>>>>>>>> applied to w does.
The issue is that the test of H^ <H^> Halting or not is >>>>>>>>>>>>>>> NOT based on the processing that H does on it, but what >>>>>>>>>>>>>>> it does as an independent entity, either what
UTM(<H^>,<H^>) does or what H^ <H^> does.
In both of these cases, that top level H^ being processed >>>>>>>>>>>>>>> is NOT 'aborted' by H (maybe what you call halts) and it >>>>>>>>>>>>>>> will continue on till it reaches that same H^.Qn and >>>>>>>>>>>>>>> Halt, and thus show that H^ <H^> is a halting computation. >>>>>>>>>>>>>>>
Your probably next claim that H can't be responsible for >>>>>>>>>>>>>>> the actual machine because it wasn't the input isn't >>>>>>>>>>>>>>> correct, it can't use the actual machine to do its >>>>>>>>>>>>>>> computation, but it IS responsible for the behavior of >>>>>>>>>>>>>>> that machine if it wants to claim to compute the Halting >>>>>>>>>>>>>>> Function which IS dependent on that actual machine, for >>>>>>>>>>>>>>> which it just gets a representation of.
embedded_H computes the mapping from its input finite >>>>>>>>>>>>>> strings ⟨Ĥ⟩ ⟨Ĥ⟩ to Ĥ.qy or Ĥ.qn based on what the
behavior of this input would if embedded_H would continue >>>>>>>>>>>>>> to simulate this input forever.
Which is incorrect the way you do it, It needs to determine >>>>>>>>>>>>> what the input would do based on the copy of H embedded in >>>>>>>>>>>>> H^ doing what all copies of H will do. PERIOD. ASSUMING >>>>>>>>>>>>> that the copy of H embedded in H^ will continue simulating >>>>>>>>>>>>> forever just makes an ASS out of U, because that is NOT >>>>>>>>>>>>> what it will do.
None of the copies of embedded_H do anything besides
simulate their input until the outermost copy recognizes the >>>>>>>>>>>> infinitely repeating pattern.
But what would they do AFTER that? Won't they also abort >>>>>>>>>>> their own simulation?
When embedded_H recognizes that its input matches an infinite >>>>>>>>>> behavior pattern it immediately stops simulating this input >>>>>>>>>> thus terminating the entire call chain.
Not the part of the chain that is CALLING it.
You simply don't know enough computer science to understand that >>>>>>>> your objection is totally irrelevant.
embedded_H is only accountable for computing the mapping from
⟨Ĥ⟩ ⟨Ĥ⟩ to Ĥ.qy and Ĥ.qn.
Everything else in the universe it totally irrelevant to the
correctness of the halt status decision of embedded_H.
No, it is accountable to compute the RIGHT answer per the
specifications. I mentioned this previously, and you have just
ignored this error of yours.
If you aren't using the official Halting Problem Specifications
then you are just talking about POOP.
The Official Halting Problem Specifications say that H applied to >>>>>>> input wM w needs to answer Halting (by going to H.Qy) for H
applied to wM w if and only if M applied to w will Halt in some
finite time and to answer Non-Halting (by going to H.Qn) if M
applied to w will NEVER Halt.
Since H^ w is designed so it will Halt if H w w goes to H.Qn and >>>>>>> to loop forever if H w w goes to H.Qy, then we have that if H
<H^> <H^> goes to H.Qn as you claim, then H^ <H^> will by
construction Halt, and thus H failed to meet its requriements,
since it said Non-Halting for a computation that clearly Halted. >>>>>>>
embedded_H is only accountable for computing the mapping of its
inputs ⟨Ĥ⟩ ⟨Ĥ⟩ to Ĥ.qy or Ĥ.qn because all deciders are only >>>>>> accountable for mapping their inputs to an accept or reject state. >>>>>>
When you object to this you are forgetting that all halt deciders
must be deciders.
But you are WRONG in your interpretation. DO you have a source to
back your meaning up.
H is accountable for computing the mapping of (wM, w) to match the
Halting property of M applied to w. The EXACT machine and input and
the EXACT behavior.
All halt deciders are deciders and are only accountable for mapping
their inputs to an accept or reject state. If you can't understand
this there is no sense proceeding further.
So, you don't understand that a decider needs to CORRECTLY compute
the function it is deciding?
Does that mean I can just make my halt decider always decide
non-halting and claim it is correct? That seems the logical
conclusion of your statment.
FAIL.
H <H^> <H^> means to answer on the behavior of H^ <H^>, which just
happens to also match UTM <H^> <H^> but that behaves exactly the same. >>>>>
Yes, it is only 'accountable' for the input it was given, but that
is the input string <H^> <H^>, and it is accountable for generating
the RIGHT answer based on the definition of the mapping it is
claiming to compute, which is that Halting Property of H^ applied
to <H^>,
No this is flatly incorrect. If this was the case then embedded_H
would be reporting the halt status of itself.
But it sort of needs to. It NEEDS to be able to report the halt
status of a computation that uses a copy of itself. THAT IS THE
REQUIREMENT.
It only reports on the halt status of its direct inputs.
If this input specifies an infinitely nested simulation chain
then the whole chain will be broken when the outermost invocation
is aborted.
You must have something strange defined then.
H's (and embedded_H's) 'direct' input is <H^> <H^> which represents the computation H^ applied to <H^>, which as pointed out if H <H^> <H^> says non-halting will Halt.
Since, if H <H^> <H^> -> H.Qn, we have that H^ <H^> will Halt, and you
have even admitted this in the past, and the correct answer for the
input (<H^>,<H^>) must match the behavior of H^ <H^>,
it is clear that
the correct answer for the behavior of the direct input for the question
H <H^> <H^> is Halting, it seems that H must be wrong here.
Now, if it will only abort it if KNOWS it will be right, then we may be
in the case that H doesn't abort its simulation and just doesn't answer,
and fails that way. But it can't do both, it either DOES abort, or it DOESN'T, we have no Schrodinger Turing Machines. Also, all copies of H
must give the same answer for the same input. If you want to claim
otherwise, you still haven't shown an actual Turing Macine capable of
giving two different results when run in two copies with identical
inputs. Go ahead, try to do it.
It needs to handle 'All Computations' that includes one that use a
copy of its algorithm.
FAIL
which as been shown, if H <H^> <H^> -> H.Qn is to HALT.
I can't see how you possible misunderstand that statement.
I understand that you keep making the same error that embedded_H
must report the halt status of itself.
Yep, if the input contains a copy of itself, it needs to report the
halt status affected by a copy of itself.
The entire chain is aborted when the outermost invocation is aborted.
So, does H go to H.Qn or not when it does this 'abort'
If it goes to H.Qn, then by definition the computation H^ will Halt.
If not, the H did not give the answer 'Non-Halting' and failed.
Even if H just Halts itself to 'abort the entire chain' then H^ halts,
since the H we are looking at is PART of H^.
You don't seem to understand what 'answering' seems to mean for a Turing Machine.
H wM w -> Qy or Qn based on the behaviof or M w.
If M constains a copy of H, then YES, H needs to decide on a copy of
itself.
The entire chain is aborted when the outermost invocation is aborted.
So, does H go to H.Qn or not when it does this 'abort'
If it goes to H.Qn, then by definition the computation H^ will Halt.
If not, the H did not give the answer 'Non-Halting' and failed.
Even if H just Halts itself to 'abort the entire chain' then H^ halts,
since the H we are looking at is PART of H^.
You don't seem to understand what 'answering' seems to mean for a Turing Machine.
WHAT IS WRONG WITH THAT?
This is part of one of the reason that it turns out impossible to do
this.
The REQUIREMENMTS are the REQUIREMENTS.
Don't meet the REQUIREMENTS, and you are wrong.
change the REQUIREMENTS, and you are solving a different problem, and
can't use it to talk about the original problem.
FAIL.
What is it that you think H doesn't need to be accountable for?
Remember, the algorithm of H^ includes a copy of the algorihm of H
in it, so that algorithm will be fulliy encoded inside <H^> too, so
H is accountable for correctly deciding what that part of the
machine does too. What make you think it isn't?
| Sysop: | Keyop |
|---|---|
| Location: | Huddersfield, West Yorkshire, UK |
| Users: | 456 |
| Nodes: | 16 (2 / 14) |
| Uptime: | 102:04:36 |
| Calls: | 9,320 |
| Files: | 13,530 |
| Messages: | 6,079,650 |