On 2022-04-01 12:36, olcott wrote:
MUTUAL AGREEMENT ON THIS IS MANDATORY FOR FURTHER DIALOGUE
(2) The direct execution of a Turing machine is computationally
equivalent to the UTM simulation of its Turing machine description.
I am willing to accept this, though it really should be written more
clearly. The UTM simulation of a computation is equivalent to that computation in some respects but not in others; so you need to better
define what is meant by 'computationally equivalent'.
(3) Halt deciders compute the mapping of their input finite strings to
an accept or reject state on the basis of the actual behavior
specified by their input.
This is horrendously worded. The input to a halt decider doesn't specify behaviour at all. It is a concatenation of two strings, one which
encodes a TM and the other which encodes an input string. You only get behaviour when you actually apply that Turing Machine to that input
string. You'll almost certainly get people who will agree to this but
only because they interpret it as meaning something reasonable whereas
you interpret it to mean something entirely different. A correct wording would be
Halt deciders compute the mapping of their input string to an accept or reject state based on whether the Turing Machine which is encoded by the first portion of the input string would halt when applied to the string encoded by the second portion of the input string.
Strings don't have behaviours, let alone halting behaviours.
Inputs to simulators don't have behaviours. The simulation does, but the inputs do not, but the halting problem is not concerned with the
behaviour of simulations; only of actual computations. In the case of a
true simulation these should be the same, but your H is not a true
simulator, nor can it act as a proxy for one.
(4) The actual behavior specified by the input is measured by the
behavior of a UTM simulation of this input at the same point in the
execution trace as the simulating halt decider. (defined in (2) above)
This is simply incoherent gibberish. How can a UTM and a halt decider
have a 'same point in the execution trace' given that they are entirely different computations with entirely different 'execution traces'?
Simplified Ĥ directly calls H --- infinite loop has been removed.
Why has the infinite loop been removed? What purpose does that serve?
Ĥ.q0 ⟨Ĥ⟩ ⊢* H ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* H.qy
Ĥ.q0 ⟨Ĥ⟩ ⊢* H ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* H.qn
In other words every H remains in pure UTM mode until the outermost H
has complete proof that its simulated input would never reach its own
final state.
Turing Machines don't have 'modes' under any standard definition. If you
want to talk about 'modes' you need to define this term.
And your H *never* operates as a UTM so I fail to see how it can ever
operate in 'UTM mode'.
A UTM simulates the execution of each step in the computation which it
is given as an input.
It does *not* look for 'halting patterns' in that input. Any TM which
does look for these is not acting as a UTM. It does *not* make decisions about whether to abort its simulation of its input. Any TM which does
this is *not* acting as a UTM.
So unless you are claiming that your H starts simulating its input
without attempting to identify any halting patterns which might cause it
to abort, it is *never* acting as a UTM.
A simulating halt decider is in UTM mode while the behavior of its
input remains computationally equivalent to the behavior of this same
input when simulated by a UTM.
The above is meaningless. There is no 'UTM mode'.
(5) Linz: computation that halts … the Turing machine will halt
whenever it enters a final state. (Linz:1990:234)
Yes. When a turing machine enters its final state it halts.
When a simulation of a turing machine is aborted, it does not reach a
final state but that has no bearing at all on whether the computation is halting since halting is a property of computations, not of aborted simulations.
(6) A correct simulation of a Turing machine description that would
never reach its final state is computationally equivalent to the
direct execution of this same Turing machine never reaching its final
state and thus specifies a non-halting sequence of configurations.
Not if it never reaches its final state merely because it was aborted.
Claiming that your H can determine that the input is non-halting and
then abort it based on that determination presupposes the existence of a halting decider, which means you are assuming your own conclusion as
part of the assumptions you expect everyone else to agree to. This
assumption is exactly the one that the Linz proof demonstrates is false.
On Saturday, April 2, 2022 at 12:20:19 PM UTC-4, olcott wrote:Ĥ.q0 ⟨Ĥ⟩ ⊢* H ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* H.qy
On 4/1/2022 2:20 PM, André G. Isaak wrote:
On 2022-04-01 12:36, olcott wrote:
MUTUAL AGREEMENT ON THIS IS MANDATORY FOR FURTHER DIALOGUE
(2) The direct execution of a Turing machine is computationally
equivalent to the UTM simulation of its Turing machine description.
I am willing to accept this, though it really should be written more
clearly. The UTM simulation of a computation is equivalent to that
computation in some respects but not in others; so you need to better
define what is meant by 'computationally equivalent'.
Exactly the same as means equivalent in all respects, whereas equivalent
means not exactly the same in all respects.
The key elements of equivalence are a bijection between executed and
simulated states on the same inputs thus deriving the same halting or
non-halting sequence of configurations.
(3) Halt deciders compute the mapping of their input finite strings to >>>> an accept or reject state on the basis of the actual behavior
specified by their input.
This is horrendously worded. The input to a halt decider doesn't specify >>> behaviour at all. It is a concatenation of two strings, one which
encodes a TM and the other which encodes an input string. You only get
behaviour when you actually apply that Turing Machine to that input
string. You'll almost certainly get people who will agree to this but
only because they interpret it as meaning something reasonable whereas
you interpret it to mean something entirely different. A correct wording >>> would be
I have to find some way to word this such that the actual behavior of
the correct simulation of the actual input to the simulating halt
decider is understood to be the only measure of behavior that counts.
Everyone tests the behavior at the wrong place in the execution trace
that has different behavior than the behavior that must be tested.
Halt deciders compute the mapping of their input string to an accept or
reject state based on whether the Turing Machine which is encoded by the >>> first portion of the input string would halt when applied to the string
encoded by the second portion of the input string.
Strings don't have behaviours, let alone halting behaviours.
Simulated Turing machine descriptions have behaviors that either reach
their own simulated final state in a finite number of correctly
simulated steps or not.
Inputs to simulators don't have behaviours. The simulation does, but the >>> inputs do not, but the halting problem is not concerned with the
behaviour of simulations; only of actual computations. In the case of a
true simulation these should be the same, but your H is not a true
simulator, nor can it act as a proxy for one.
The simulation of the input by H contains all of the exact same steps
performed step-by-step in the exact same way as the UTM simulation of
these same steps.
(4) The actual behavior specified by the input is measured by the
behavior of a UTM simulation of this input at the same point in the
execution trace as the simulating halt decider. (defined in (2) above)
This is simply incoherent gibberish. How can a UTM and a halt decider
have a 'same point in the execution trace' given that they are entirely
different computations with entirely different 'execution traces'?
How can a C compiler also be a Fortran compiler? Its not that hard.
H contains all of the code of a complete UTM thus can exactly duplicate
the behavior of the simulation of a finite sequence of configurations of
any input...
Simplified Ĥ directly calls H --- infinite loop has been removed.
Why has the infinite loop been removed? What purpose does that serve?
It is never reached in any of my analysis thus is purely extraneous.
Ĥ.q0 ⟨Ĥ⟩ ⊢* H ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* H.qy
Ĥ.q0 ⟨Ĥ⟩ ⊢* H ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* H.qn
In other words every H remains in pure UTM mode until the outermost H
has complete proof that its simulated input would never reach its own
final state.
Turing Machines don't have 'modes' under any standard definition. If you >>> want to talk about 'modes' you need to define this term.
While H is using the functionality of its embedded UTM every simulated
step of any finite sequence of simulated configurations has exactly the
same behavior as if it was simulated by a UTM.
And your H *never* operates as a UTM so I fail to see how it can ever
operate in 'UTM mode'.
A UTM simulates the execution of each step in the computation which it
is given as an input.
It does *not* look for 'halting patterns' in that input. Any TM which
does look for these is not acting as a UTM. It does *not* make decisions >>> about whether to abort its simulation of its input. Any TM which does
this is *not* acting as a UTM.
So unless you are claiming that your H starts simulating its input
without attempting to identify any halting patterns which might cause it >>> to abort, it is *never* acting as a UTM.
All of the halt deciding aspects of H are totally irrelevant when
accurately evaluating that the behavior of the simulated input by H or
by a UTM is 100% exactly the same for a finite number of simulated steps
of sequences of configurations.
It is only when a step of this simulated behavior diverges from the UTM
simulated sequence that H is no longer in UTM mode.
A simulating halt decider is in UTM mode while the behavior of its
input remains computationally equivalent to the behavior of this same
input when simulated by a UTM.
The above is meaningless. There is no 'UTM mode'.
That I had not previously sufficiently defined the term certainly does
not mean that there is no UTM mode.
(5) Linz: computation that halts … the Turing machine will halt
whenever it enters a final state. (Linz:1990:234)
Yes. When a turing machine enters its final state it halts.
When a simulation of a turing machine is aborted, it does not reach a
final state but that has no bearing at all on whether the computation is >>> halting since halting is a property of computations, not of aborted
simulations.
In computability theory, the halting problem is the problem of
determining, from a description of an arbitrary computer program and an
input, whether the program will finish running, or continue to run
forever. https://en.wikipedia.org/wiki/Halting_problem
In other words whether or not the sequence of configurations specified
by an input pair: "will finish running, or continue to run forever."
(6) A correct simulation of a Turing machine description that would(6) A correct simulation of a Turing machine description that would
never reach its final state is computationally equivalent to the
direct execution of this same Turing machine never reaching its final
state and thus specifies a non-halting sequence of configurations.
Not if it never reaches its final state merely because it was aborted.
never reach its final state ...
under any conditions what-so-ever
specifies a non-halting sequence of configurations.
Let's test this on a specific example. But first some definitions:
Hn: a simulating halt decider that never aborts its simulation (effectively a UTM, so it can't recognize non-halting and doesn't qualify as a SHD)
Hn^: built from Hn as per the Linz template. By its construction, Hn^ applied to <Hn^> does not halt
Ha: a simulating halt decider that you claim can recognize infinite simulation in Hn^ and Ha^ and refute the Linz proof
Ha^: built from Ha as per the Linz template
You claim that Ha is correct to reject <Ha^><Ha^>. Given your claim above:
---
A correct simulation of a Turing machine description that would
never reach its final state ...
under any conditions what-so-ever
specifies a non-halting sequence of configurations.
---
This means that under *no circumstances* will the simulation of <Ha^><Ha^> even reach a final state. We can test this by passing this input to another simulating halt decider.
On Saturday, April 2, 2022 at 1:28:03 PM UTC-4, olcott wrote:
On 4/2/2022 12:21 PM, Dennis Bush wrote:
On Saturday, April 2, 2022 at 12:20:19 PM UTC-4, olcott wrote:Ĥ.q0 ⟨Ĥ⟩ ⊢* H ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* H.qy
On 4/1/2022 2:20 PM, André G. Isaak wrote:
On 2022-04-01 12:36, olcott wrote:
MUTUAL AGREEMENT ON THIS IS MANDATORY FOR FURTHER DIALOGUEI am willing to accept this, though it really should be written more >>>>> clearly. The UTM simulation of a computation is equivalent to that
(2) The direct execution of a Turing machine is computationally
equivalent to the UTM simulation of its Turing machine description. >>>>>
computation in some respects but not in others; so you need to better >>>>> define what is meant by 'computationally equivalent'.
Exactly the same as means equivalent in all respects, whereas equivalent >>>> means not exactly the same in all respects.
The key elements of equivalence are a bijection between executed and
simulated states on the same inputs thus deriving the same halting or
non-halting sequence of configurations.
(3) Halt deciders compute the mapping of their input finite strings to >>>>>> an accept or reject state on the basis of the actual behavior
specified by their input.
This is horrendously worded. The input to a halt decider doesn't specify >>>>> behaviour at all. It is a concatenation of two strings, one which
encodes a TM and the other which encodes an input string. You only get >>>>> behaviour when you actually apply that Turing Machine to that input
string. You'll almost certainly get people who will agree to this but >>>>> only because they interpret it as meaning something reasonable whereas >>>>> you interpret it to mean something entirely different. A correct wording >>>>> would be
I have to find some way to word this such that the actual behavior of
the correct simulation of the actual input to the simulating halt
decider is understood to be the only measure of behavior that counts.
Everyone tests the behavior at the wrong place in the execution trace
that has different behavior than the behavior that must be tested.
Halt deciders compute the mapping of their input string to an accept or >>>>> reject state based on whether the Turing Machine which is encoded by the >>>>> first portion of the input string would halt when applied to the string >>>>> encoded by the second portion of the input string.
Strings don't have behaviours, let alone halting behaviours.
Simulated Turing machine descriptions have behaviors that either reach >>>> their own simulated final state in a finite number of correctly
simulated steps or not.
Inputs to simulators don't have behaviours. The simulation does, but the >>>>> inputs do not, but the halting problem is not concerned with the
behaviour of simulations; only of actual computations. In the case of a >>>>> true simulation these should be the same, but your H is not a true
simulator, nor can it act as a proxy for one.
The simulation of the input by H contains all of the exact same steps
performed step-by-step in the exact same way as the UTM simulation of
these same steps.
(4) The actual behavior specified by the input is measured by theThis is simply incoherent gibberish. How can a UTM and a halt decider >>>>> have a 'same point in the execution trace' given that they are entirely >>>>> different computations with entirely different 'execution traces'?
behavior of a UTM simulation of this input at the same point in the >>>>>> execution trace as the simulating halt decider. (defined in (2) above) >>>>>
How can a C compiler also be a Fortran compiler? Its not that hard.
H contains all of the code of a complete UTM thus can exactly duplicate >>>> the behavior of the simulation of a finite sequence of configurations of >>>> any input...
Simplified Ĥ directly calls H --- infinite loop has been removed.
Why has the infinite loop been removed? What purpose does that serve? >>>>>
It is never reached in any of my analysis thus is purely extraneous. >>>>>> Ĥ.q0 ⟨Ĥ⟩ ⊢* H ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* H.qy
Ĥ.q0 ⟨Ĥ⟩ ⊢* H ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* H.qn
In other words every H remains in pure UTM mode until the outermost H >>>>>> has complete proof that its simulated input would never reach its own >>>>>> final state.
Turing Machines don't have 'modes' under any standard definition. If you >>>>> want to talk about 'modes' you need to define this term.
While H is using the functionality of its embedded UTM every simulated >>>> step of any finite sequence of simulated configurations has exactly the >>>> same behavior as if it was simulated by a UTM.
And your H *never* operates as a UTM so I fail to see how it can ever >>>>> operate in 'UTM mode'.
A UTM simulates the execution of each step in the computation which it >>>>> is given as an input.
It does *not* look for 'halting patterns' in that input. Any TM which >>>>> does look for these is not acting as a UTM. It does *not* make decisions >>>>> about whether to abort its simulation of its input. Any TM which does >>>>> this is *not* acting as a UTM.
So unless you are claiming that your H starts simulating its input
without attempting to identify any halting patterns which might cause it >>>>> to abort, it is *never* acting as a UTM.
All of the halt deciding aspects of H are totally irrelevant when
accurately evaluating that the behavior of the simulated input by H or >>>> by a UTM is 100% exactly the same for a finite number of simulated steps >>>> of sequences of configurations.
It is only when a step of this simulated behavior diverges from the UTM >>>> simulated sequence that H is no longer in UTM mode.
A simulating halt decider is in UTM mode while the behavior of its >>>>>> input remains computationally equivalent to the behavior of this same >>>>>> input when simulated by a UTM.
The above is meaningless. There is no 'UTM mode'.
That I had not previously sufficiently defined the term certainly does >>>> not mean that there is no UTM mode.
(5) Linz: computation that halts … the Turing machine will halt
whenever it enters a final state. (Linz:1990:234)
Yes. When a turing machine enters its final state it halts.
When a simulation of a turing machine is aborted, it does not reach a >>>>> final state but that has no bearing at all on whether the computation is >>>>> halting since halting is a property of computations, not of aborted
simulations.
In computability theory, the halting problem is the problem of
determining, from a description of an arbitrary computer program and an >>>> input, whether the program will finish running, or continue to run
forever. https://en.wikipedia.org/wiki/Halting_problem
In other words whether or not the sequence of configurations specified >>>> by an input pair: "will finish running, or continue to run forever." >>>>>> (6) A correct simulation of a Turing machine description that would >>>>>> never reach its final state is computationally equivalent to the
never reach its final state ...direct execution of this same Turing machine never reaching its final >>>>>> state and thus specifies a non-halting sequence of configurations.
Not if it never reaches its final state merely because it was aborted. >>>> (6) A correct simulation of a Turing machine description that would
under any conditions what-so-ever
specifies a non-halting sequence of configurations.
Let's test this on a specific example. But first some definitions:
Hn: a simulating halt decider that never aborts its simulation (effectively a UTM, so it can't recognize non-halting and doesn't qualify as a SHD)
Hn^: built from Hn as per the Linz template. By its construction, Hn^ applied to <Hn^> does not halt
Ha: a simulating halt decider that you claim can recognize infinite simulation in Hn^ and Ha^ and refute the Linz proof
Ha^: built from Ha as per the Linz template
You claim that Ha is correct to reject <Ha^><Ha^>. Given your claim above: >>>
---
A correct simulation of a Turing machine description that would
never reach its final state ...
under any conditions what-so-ever
specifies a non-halting sequence of configurations.
---
This means that under *no circumstances* will the simulation of <Ha^><Ha^> even reach a final state. We can test this by passing this input to another simulating halt decider.
Ĥ.q0 ⟨Ĥ⟩ ⊢* H ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* H.qn
That is off topic until after this is fully understood to be correct:
H ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* H.qn
On the basis of the above analysis
I don't think you understand. I started with the assumption that that is correct and then proved that it's not. Again:
---
A correct simulation of a Turing machine description that would
never reach its final state ...
under any conditions what-so-ever
specifies a non-halting sequence of configurations.
---
On Saturday, April 2, 2022 at 2:57:29 PM UTC-4, olcott wrote:
On 4/2/2022 1:34 PM, Dennis Bush wrote:
On Saturday, April 2, 2022 at 1:28:03 PM UTC-4, olcott wrote:You are not analyzing the same sequence of configurations:
On 4/2/2022 12:21 PM, Dennis Bush wrote:
On Saturday, April 2, 2022 at 12:20:19 PM UTC-4, olcott wrote:Ĥ.q0 ⟨Ĥ⟩ ⊢* H ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* H.qy
On 4/1/2022 2:20 PM, André G. Isaak wrote:
On 2022-04-01 12:36, olcott wrote:
MUTUAL AGREEMENT ON THIS IS MANDATORY FOR FURTHER DIALOGUEI am willing to accept this, though it really should be written more >>>>>>> clearly. The UTM simulation of a computation is equivalent to that >>>>>>> computation in some respects but not in others; so you need to better >>>>>>> define what is meant by 'computationally equivalent'.
(2) The direct execution of a Turing machine is computationally >>>>>>>> equivalent to the UTM simulation of its Turing machine description. >>>>>>>
Exactly the same as means equivalent in all respects, whereas equivalent >>>>>> means not exactly the same in all respects.
The key elements of equivalence are a bijection between executed and >>>>>> simulated states on the same inputs thus deriving the same halting or >>>>>> non-halting sequence of configurations.
(3) Halt deciders compute the mapping of their input finite strings to >>>>>>>> an accept or reject state on the basis of the actual behavior
specified by their input.
This is horrendously worded. The input to a halt decider doesn't specify
behaviour at all. It is a concatenation of two strings, one which >>>>>>> encodes a TM and the other which encodes an input string. You only get >>>>>>> behaviour when you actually apply that Turing Machine to that input >>>>>>> string. You'll almost certainly get people who will agree to this but >>>>>>> only because they interpret it as meaning something reasonable whereas >>>>>>> you interpret it to mean something entirely different. A correct wording
would be
I have to find some way to word this such that the actual behavior of >>>>>> the correct simulation of the actual input to the simulating halt
decider is understood to be the only measure of behavior that counts. >>>>>>
Everyone tests the behavior at the wrong place in the execution trace >>>>>> that has different behavior than the behavior that must be tested. >>>>>>
Halt deciders compute the mapping of their input string to an accept or >>>>>>> reject state based on whether the Turing Machine which is encoded by the
first portion of the input string would halt when applied to the string >>>>>>> encoded by the second portion of the input string.
Strings don't have behaviours, let alone halting behaviours.
Simulated Turing machine descriptions have behaviors that either reach >>>>>> their own simulated final state in a finite number of correctly
simulated steps or not.
Inputs to simulators don't have behaviours. The simulation does, but the
inputs do not, but the halting problem is not concerned with the >>>>>>> behaviour of simulations; only of actual computations. In the case of a >>>>>>> true simulation these should be the same, but your H is not a true >>>>>>> simulator, nor can it act as a proxy for one.
The simulation of the input by H contains all of the exact same steps >>>>>> performed step-by-step in the exact same way as the UTM simulation of >>>>>> these same steps.
(4) The actual behavior specified by the input is measured by the >>>>>>>> behavior of a UTM simulation of this input at the same point in the >>>>>>>> execution trace as the simulating halt decider. (defined in (2) above) >>>>>>>This is simply incoherent gibberish. How can a UTM and a halt decider >>>>>>> have a 'same point in the execution trace' given that they are entirely >>>>>>> different computations with entirely different 'execution traces'? >>>>>>>
How can a C compiler also be a Fortran compiler? Its not that hard. >>>>>> H contains all of the code of a complete UTM thus can exactly duplicate >>>>>> the behavior of the simulation of a finite sequence of configurations of >>>>>> any input...
Simplified Ĥ directly calls H --- infinite loop has been removed. >>>>>>>Why has the infinite loop been removed? What purpose does that serve? >>>>>>>
It is never reached in any of my analysis thus is purely extraneous. >>>>>>>> Ĥ.q0 ⟨Ĥ⟩ ⊢* H ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* H.qy
Ĥ.q0 ⟨Ĥ⟩ ⊢* H ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* H.qn
In other words every H remains in pure UTM mode until the outermost H >>>>>>>> has complete proof that its simulated input would never reach its own >>>>>>>> final state.
Turing Machines don't have 'modes' under any standard definition. If you
want to talk about 'modes' you need to define this term.
While H is using the functionality of its embedded UTM every simulated >>>>>> step of any finite sequence of simulated configurations has exactly the >>>>>> same behavior as if it was simulated by a UTM.
And your H *never* operates as a UTM so I fail to see how it can ever >>>>>>> operate in 'UTM mode'.
A UTM simulates the execution of each step in the computation which it >>>>>>> is given as an input.
It does *not* look for 'halting patterns' in that input. Any TM which >>>>>>> does look for these is not acting as a UTM. It does *not* make decisions
about whether to abort its simulation of its input. Any TM which does >>>>>>> this is *not* acting as a UTM.
So unless you are claiming that your H starts simulating its input >>>>>>> without attempting to identify any halting patterns which might cause it
to abort, it is *never* acting as a UTM.
All of the halt deciding aspects of H are totally irrelevant when
accurately evaluating that the behavior of the simulated input by H or >>>>>> by a UTM is 100% exactly the same for a finite number of simulated steps >>>>>> of sequences of configurations.
It is only when a step of this simulated behavior diverges from the UTM >>>>>> simulated sequence that H is no longer in UTM mode.
A simulating halt decider is in UTM mode while the behavior of its >>>>>>>> input remains computationally equivalent to the behavior of this same >>>>>>>> input when simulated by a UTM.
The above is meaningless. There is no 'UTM mode'.
That I had not previously sufficiently defined the term certainly does >>>>>> not mean that there is no UTM mode.
(5) Linz: computation that halts … the Turing machine will halt >>>>>>>> whenever it enters a final state. (Linz:1990:234)
Yes. When a turing machine enters its final state it halts.
When a simulation of a turing machine is aborted, it does not reach a >>>>>>> final state but that has no bearing at all on whether the computation is
halting since halting is a property of computations, not of aborted >>>>>>> simulations.
In computability theory, the halting problem is the problem of
determining, from a description of an arbitrary computer program and an >>>>>> input, whether the program will finish running, or continue to run >>>>>> forever. https://en.wikipedia.org/wiki/Halting_problem
In other words whether or not the sequence of configurations specified >>>>>> by an input pair: "will finish running, or continue to run forever." >>>>>>>> (6) A correct simulation of a Turing machine description that would >>>>>>>> never reach its final state is computationally equivalent to the >>>>>>>> direct execution of this same Turing machine never reaching its final >>>>>>>> state and thus specifies a non-halting sequence of configurations. >>>>>>>
Not if it never reaches its final state merely because it was aborted. >>>>>> (6) A correct simulation of a Turing machine description that would >>>>>> never reach its final state ...under any conditions what-so-ever
specifies a non-halting sequence of configurations.
Let's test this on a specific example. But first some definitions:
Hn: a simulating halt decider that never aborts its simulation (effectively a UTM, so it can't recognize non-halting and doesn't qualify as a SHD)
Hn^: built from Hn as per the Linz template. By its construction, Hn^ applied to <Hn^> does not halt
Ha: a simulating halt decider that you claim can recognize infinite simulation in Hn^ and Ha^ and refute the Linz proof
Ha^: built from Ha as per the Linz template
You claim that Ha is correct to reject <Ha^><Ha^>. Given your claim above:
---
A correct simulation of a Turing machine description that would
never reach its final state ...
under any conditions what-so-ever
specifies a non-halting sequence of configurations.
---
This means that under *no circumstances* will the simulation of <Ha^><Ha^> even reach a final state. We can test this by passing this input to another simulating halt decider.
Ĥ.q0 ⟨Ĥ⟩ ⊢* H ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* H.qn
That is off topic until after this is fully understood to be correct:
H ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* H.qn
On the basis of the above analysis
I don't think you understand. I started with the assumption that that is correct and then proved that it's not. Again:
When we examine embedded_H applied to ⟨Ĥ⟩ ⟨Ĥ⟩ we determine that its
input meets this criteria:
---Therefore its rejection of its input is necessarily correct.
A correct simulation of a Turing machine description that would
never reach its final state ...
under any conditions what-so-ever
specifies a non-halting sequence of configurations.
---
--
But Ha and embedded_Ha are the same, per the construction of Ha^.
On Saturday, April 2, 2022 at 5:31:19 PM UTC-4, olcott wrote:
On 4/2/2022 4:28 PM, Dennis Bush wrote:
On Saturday, April 2, 2022 at 5:22:20 PM UTC-4, olcott wrote:
As stated previously, the input does NOT meet that criteria as per the proof below
------
A correct simulation of a Turing machine description that would
never reach its final state ...
under any conditions what-so-ever
specifies a non-halting sequence of configurations.
------
On 2022-04-02 10:20, olcott wrote:
On 4/1/2022 2:20 PM, André G. Isaak wrote:
On 2022-04-01 12:36, olcott wrote:
MUTUAL AGREEMENT ON THIS IS MANDATORY FOR FURTHER DIALOGUE
(2) The direct execution of a Turing machine is computationally
equivalent to the UTM simulation of its Turing machine description.
I am willing to accept this, though it really should be written more
clearly. The UTM simulation of a computation is equivalent to that
computation in some respects but not in others; so you need to better
define what is meant by 'computationally equivalent'.
Exactly the same as means equivalent in all respects, whereas
equivalent means not exactly the same in all respects.
The key elements of equivalence are a bijection between executed and
simulated states on the same inputs thus deriving the same halting or
non-halting sequence of configurations.
There's little point in belabouring this point since I've already agreed
with what you are claiming. I merely would have said they have
equivalent halting statuses rather than that they were 'computationally equivalent'.
(3) Halt deciders compute the mapping of their input finite strings
to an accept or reject state on the basis of the actual behavior
specified by their input.
This is horrendously worded. The input to a halt decider doesn't
specify behaviour at all. It is a concatenation of two strings, one
which encodes a TM and the other which encodes an input string. You
only get behaviour when you actually apply that Turing Machine to
that input string. You'll almost certainly get people who will agree
to this but only because they interpret it as meaning something
reasonable whereas you interpret it to mean something entirely
different. A correct wording would be
I have to find some way to word this such that the actual behavior of
the correct simulation of the actual input to the simulating halt
decider is understood to be the only measure of behavior that counts.
The problem is that you are trying to find a wording to convey a meaning which is simply wrong. What a halt decider does is well-defined. A Halt decider H applied to <M> I must accept this input if and only if M
applied to I halts. It is about the behaviour of actual, independent computations, not about what some input string does inside a SHD
(whatever that even means).
Everyone tests the behavior at the wrong place in the execution trace
that has different behavior than the behavior that must be tested.
Halting is a property of a computation. It doesn't hold at some
particular 'place'. It holds for the entire computation.
Halt deciders compute the mapping of their input string to an accept
or reject state based on whether the Turing Machine which is encoded
by the first portion of the input string would halt when applied to
the string encoded by the second portion of the input string.
Strings don't have behaviours, let alone halting behaviours.
Simulated Turing machine descriptions have behaviors that either reach
their own simulated final state in a finite number of correctly
simulated steps or not.
Again, the simulation has behaviour.
The description does not. You don't
seem to understand the relationship between strings and what they encode which is why you think you can get away with your misguided notion of
what the halting criterion is.
Inputs to simulators don't have behaviours. The simulation does, but
the inputs do not, but the halting problem is not concerned with the
behaviour of simulations; only of actual computations. In the case of
a true simulation these should be the same, but your H is not a true
simulator, nor can it act as a proxy for one.
The simulation of the input by H contains all of the exact same steps
performed step-by-step in the exact same way as the UTM simulation of
these same steps.
(4) The actual behavior specified by the input is measured by the
behavior of a UTM simulation of this input at the same point in the
execution trace as the simulating halt decider. (defined in (2) above)
This is simply incoherent gibberish. How can a UTM and a halt decider
have a 'same point in the execution trace' given that they are
entirely different computations with entirely different 'execution
traces'?
How can a C compiler also be a Fortran compiler? Its not that hard.
H contains all of the code of a complete UTM thus can exactly
duplicate the behavior of the simulation of a finite sequence of
configurations of any input...
As usual, you are responding with something entirely *irrelevant* to my point. UTMs applied to an input and SHDs applied to the same input are *different* computations,
therefore they will have *different*
'execution traces', so it makes no sense to talk about the 'same point'
in the two traces.
Simplified Ĥ directly calls H --- infinite loop has been removed.
Why has the infinite loop been removed? What purpose does that serve?
It is never reached in any of my analysis thus is purely extraneous.
Ĥ.q0 ⟨Ĥ⟩ ⊢* H ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* H.qy
Ĥ.q0 ⟨Ĥ⟩ ⊢* H ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* H.qn
In other words every H remains in pure UTM mode until the outermost
H has complete proof that its simulated input would never reach its
own final state.
Turing Machines don't have 'modes' under any standard definition. If
you want to talk about 'modes' you need to define this term.
While H is using the functionality of its embedded UTM every simulated
step of any finite sequence of simulated configurations has exactly
the same behavior as if it was simulated by a UTM.
No, it does not. If it were simulated by a UTM there would be no pattern matching between steps. Which means the 'execution traces' of both will
be entirely different from one another.
And your H *never* operates as a UTM so I fail to see how it can ever
operate in 'UTM mode'.
A UTM simulates the execution of each step in the computation which
it is given as an input.
It does *not* look for 'halting patterns' in that input. Any TM which
does look for these is not acting as a UTM. It does *not* make
decisions about whether to abort its simulation of its input. Any TM
which does this is *not* acting as a UTM.
So unless you are claiming that your H starts simulating its input
without attempting to identify any halting patterns which might cause
it to abort, it is *never* acting as a UTM.
All of the halt deciding aspects of H are totally irrelevant when
accurately evaluating that the behavior of the simulated input by H or
by a UTM is 100% exactly the same for a finite number of simulated
steps of sequences of configurations.
Of course the are relevant because the input string to embedded_H has
exactly the same halt deciding aspects as your embedded_H, and these
effect how the machine which that input represents behaves.
You
consistently ignore the fact that the simulated input to embedded_H is
just as capable of aborting the simulation which it performs as
embedded_H is.
It is only when a step of this simulated behavior diverges from the
UTM simulated sequence that H is no longer in UTM mode.
If it is a SHD, it was never in UTM mode to begin with.
A simulating halt decider is in UTM mode while the behavior of its
input remains computationally equivalent to the behavior of this
same input when simulated by a UTM.
The above is meaningless. There is no 'UTM mode'.
That I had not previously sufficiently defined the term certainly does
not mean that there is no UTM mode.
So then provide some coherent definition of 'UTM Mode'.
Usually when programs have different modes it means they can run in one
of two ways. For instance, bash can be run interactively or non-interactively. It doesn't switch from one mode to another.
Obviously, you mean something entirely different by 'mode', but you have never defined this.
(5) Linz: computation that halts … the Turing machine will halt
whenever it enters a final state. (Linz:1990:234)
Yes. When a turing machine enters its final state it halts.
When a simulation of a turing machine is aborted, it does not reach a
final state but that has no bearing at all on whether the computation
is halting since halting is a property of computations, not of
aborted simulations.
In computability theory, the halting problem is the problem of
determining, from a description of an arbitrary computer program and
an input, whether the program will finish running, or continue to run
forever. https://en.wikipedia.org/wiki/Halting_problem
In other words whether or not the sequence of configurations specified
by an input pair: "will finish running, or continue to run forever."
The input pair does not specify a sequence of configurations. It encodes
a Turing Machine followed by an input string.
(6) A correct simulation of a Turing machine description that would
never reach its final state is computationally equivalent to the
direct execution of this same Turing machine never reaching its
final state and thus specifies a non-halting sequence of
configurations.
Not if it never reaches its final state merely because it was aborted.
(6) A correct simulation of a Turing machine description that would
never reach its final state ...
under any conditions what-so-ever
specifies a non-halting sequence of configurations.
And your "SHD" aborts an input string which *does* reach its final
state. It's just the simulation inside the SHD ends prematurely before
it reaches this point.
Claiming that your H can determine that the input is non-halting and
then abort it based on that determination presupposes the existence
of a halting decider, which means you are assuming your own
conclusion as part of the assumptions you expect everyone else to
agree to. This assumption is exactly the one that the Linz proof
demonstrates is false.
When we mutually agree that all of the above is correct then we add
one more single piece and we know that embedded H does correctly
decide the halt status of its input: ⟨Ĥ⟩ ⟨Ĥ⟩ and correctly transition
to H.qn.
But you're never going to get mutual agreement on points which are
patently wrong.
The actual algorithm that H would use is quite obvious for humans to
see from what has already been shown. Enormously more difficult to
show as the actual steps of an actual RASP machine. Possibly far too
cumbersome to ever show as all of the actual steps of an actual Turing
machine.
And yet this is the task you have set out for yourself. 'TMs can solve halting but it is far too cumbersome to show how' is not an argument.
André
On Saturday, April 2, 2022 at 6:15:15 PM UTC-4, olcott wrote:
On 4/2/2022 4:53 PM, Dennis Bush wrote:
On Saturday, April 2, 2022 at 5:31:19 PM UTC-4, olcott wrote:Ĥ.q0 ⟨Ĥ⟩ ⊢* H ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* H.qy
On 4/2/2022 4:28 PM, Dennis Bush wrote:
On Saturday, April 2, 2022 at 5:22:20 PM UTC-4, olcott wrote:
As stated previously, the input does NOT meet that criteria as per the proof below
------
A correct simulation of a Turing machine description that would
never reach its final state ...
under any conditions what-so-ever
specifies a non-halting sequence of configurations.
------
Ĥ.q0 ⟨Ĥ⟩ ⊢* H ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* H.qn
The input: ⟨Ĥ⟩ ⟨Ĥ⟩ simulated by embedded_H would not reach a final state
of ⟨Ĥ.H.qy⟩ or ⟨Ĥ.H.qn⟩ whether or not its simulation is aborted or not
aborted. Aborted or not Aborted are the only two possible conditions
therefore:
The correct simulation of ⟨Ĥ⟩ ⟨Ĥ⟩ would never reach its final state
under any conditions what-so-ever.
As demonstrated in the proof, Hb does a correct simulation of <Ha^><Ha^> to a final state. So your claim that the simulation of <H^><H^>, which is the same as <Ha^><Ha^> if H has abort logic, would never reach its final state is false.
------
A correct simulation of a Turing machine description that would
never reach its final state ...
under any conditions what-so-ever
specifies a non-halting sequence of configurations.
------
On 2022-04-02 16:15, olcott wrote:
On 4/2/2022 4:53 PM, Dennis Bush wrote:
On Saturday, April 2, 2022 at 5:31:19 PM UTC-4, olcott wrote:
On 4/2/2022 4:28 PM, Dennis Bush wrote:
On Saturday, April 2, 2022 at 5:22:20 PM UTC-4, olcott wrote:
As stated previously, the input does NOT meet that criteria as per
the proof below
------
A correct simulation of a Turing machine description that would
never reach its final state ...
under any conditions what-so-ever
specifies a non-halting sequence of configurations.
------
Ĥ.q0 ⟨Ĥ⟩ ⊢* H ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* H.qy
Ĥ.q0 ⟨Ĥ⟩ ⊢* H ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* H.qn
The input: ⟨Ĥ⟩ ⟨Ĥ⟩ simulated by embedded_H would not reach a final >> state of ⟨Ĥ.H.qy⟩ or ⟨Ĥ.H.qn⟩ whether or not its simulation is aborted
or not aborted. Aborted or not Aborted are the only two possible
conditions therefore:
The problem here is that you have asserted the above many times but have never shown it to be true.
---
A correct simulation of a Turing machine description that would
never reach its final state ...
under any conditions what-so-ever
specifies a non-halting sequence of configurations.
---
On 2022-04-02 16:52, olcott wrote:
On 4/2/2022 5:29 PM, André G. Isaak wrote:
On 2022-04-02 16:15, olcott wrote:
On 4/2/2022 4:53 PM, Dennis Bush wrote:
On Saturday, April 2, 2022 at 5:31:19 PM UTC-4, olcott wrote:
On 4/2/2022 4:28 PM, Dennis Bush wrote:
On Saturday, April 2, 2022 at 5:22:20 PM UTC-4, olcott wrote:
As stated previously, the input does NOT meet that criteria as per
the proof below
------
A correct simulation of a Turing machine description that would
never reach its final state ...
under any conditions what-so-ever
specifies a non-halting sequence of configurations.
------
Ĥ.q0 ⟨Ĥ⟩ ⊢* H ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* H.qy
Ĥ.q0 ⟨Ĥ⟩ ⊢* H ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* H.qn
The input: ⟨Ĥ⟩ ⟨Ĥ⟩ simulated by embedded_H would not reach a final
state of ⟨Ĥ.H.qy⟩ or ⟨Ĥ.H.qn⟩ whether or not its simulation is >>>> aborted or not aborted. Aborted or not Aborted are the only two
possible conditions therefore:
The problem here is that you have asserted the above many times but
have never shown it to be true.
---
A correct simulation of a Turing machine description that would
never reach its final state ...
under any conditions what-so-ever
specifies a non-halting sequence of configurations.
---
It is the case that embedded_H does correctly reject its input on the
basis that this input meets the criteria.
It is proven to be totally correct entirely on the basis of the
meaning of its words.
It follows this model:
If "an X is a Y" and Z says that "an X is a Y" then anything in the
universe that disagrees is necessarily incorrect.
Repeating a claim doesn't qualify as an argument.
And your duplicitous snipping of the final line of my post just makes
you look like a deceitful liar desperately trying to avoid a point.
André
On 4/2/22 8:36 PM, olcott wrote:
On 4/2/2022 7:23 PM, André G. Isaak wrote:
On 2022-04-02 18:12, olcott wrote:
On 4/2/2022 6:58 PM, André G. Isaak wrote:
Yes, if you abort the simulation, the simulation does not reach a
final state, but it is obvious that if your 'SHD' had not aborted
the simulation, it *would* have ultimately reached a final state.
So an infinite loop eventually halts if you just wait long enough.
Of course not. But there is no such loop involved in the case under
consideration. This is obvious to everyone participating in this
thread other than you.
André
Even Richard knows that this never stops running unless aborted:
When Ĥ is applied to ⟨Ĥ⟩
Ĥ copies its input ⟨Ĥ0⟩ to ⟨Ĥ1⟩ then embedded_H simulates ⟨Ĥ0⟩ ⟨Ĥ1⟩
Then these steps would keep repeating:
Ĥ0 copies its input ⟨Ĥ1⟩ to ⟨Ĥ2⟩ then embedded_H0 simulates ⟨Ĥ1⟩ ⟨Ĥ2⟩
Ĥ1 copies its input ⟨Ĥ2⟩ to ⟨Ĥ3⟩ then embedded_H1 simulates ⟨Ĥ2⟩ ⟨Ĥ3⟩
Ĥ2 copies its input ⟨Ĥ3⟩ to ⟨Ĥ4⟩ then embedded_H2 simulates ⟨Ĥ3⟩
⟨Ĥ4⟩...
But the loop isn't an infinite 'Do Loop', so Anre is RIGHT, there is no infinite Do Loop involved.
You are just being sloppy.
it is obvious that if your 'SHD' had not aborted the
simulation, it *would* have ultimately reached a final state.
On 4/2/22 9:20 PM, olcott wrote:
On 4/2/2022 8:17 PM, Richard Damon wrote:
On 4/2/22 9:06 PM, olcott wrote:
On 4/2/2022 7:48 PM, Richard Damon wrote:
On 4/2/22 8:36 PM, olcott wrote:
On 4/2/2022 7:23 PM, André G. Isaak wrote:
On 2022-04-02 18:12, olcott wrote:
On 4/2/2022 6:58 PM, André G. Isaak wrote:Of course not. But there is no such loop involved in the case
Yes, if you abort the simulation, the simulation does not reach >>>>>>>>> a final state, but it is obvious that if your 'SHD' had not
aborted the simulation, it *would* have ultimately reached a >>>>>>>>> final state.
So an infinite loop eventually halts if you just wait long enough. >>>>>>>
under consideration. This is obvious to everyone participating in >>>>>>> this thread other than you.
André
Even Richard knows that this never stops running unless aborted:
When Ĥ is applied to ⟨Ĥ⟩
Ĥ copies its input ⟨Ĥ0⟩ to ⟨Ĥ1⟩ then embedded_H simulates ⟨Ĥ0⟩
⟨Ĥ1⟩
Then these steps would keep repeating:
Ĥ0 copies its input ⟨Ĥ1⟩ to ⟨Ĥ2⟩ then embedded_H0 simulates
⟨Ĥ1⟩ ⟨Ĥ2⟩
Ĥ1 copies its input ⟨Ĥ2⟩ to ⟨Ĥ3⟩ then embedded_H1 simulates
⟨Ĥ2⟩ ⟨Ĥ3⟩
Ĥ2 copies its input ⟨Ĥ3⟩ to ⟨Ĥ4⟩ then embedded_H2 simulates
⟨Ĥ3⟩ ⟨Ĥ4⟩...
But the loop isn't an infinite 'Do Loop', so Anre is RIGHT, there
is no infinite Do Loop involved.
You are just being sloppy.
Here is the context of the mistake that I was responding to:
On 4/2/2022 6:58 PM, André G. Isaak wrote:
it is obvious that if your 'SHD' had not aborted the
simulation, it *would* have ultimately reached a final state.
"it *would* have ultimately reached a final state."
refers to the simulated input.
But a PROPERLY simulated input WOULD reach the final state.
Ĥ.q0 ⟨Ĥ⟩ ⊢* UTM ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* H.qy
Ĥ.q0 ⟨Ĥ⟩ ⊢* UTM ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* H.qn
No so much
But that isn't what H^ is.
On 4/2/22 9:06 PM, olcott wrote:
On 4/2/2022 7:48 PM, Richard Damon wrote:
On 4/2/22 8:36 PM, olcott wrote:
On 4/2/2022 7:23 PM, André G. Isaak wrote:
On 2022-04-02 18:12, olcott wrote:
On 4/2/2022 6:58 PM, André G. Isaak wrote:
Yes, if you abort the simulation, the simulation does not reach a >>>>>>> final state, but it is obvious that if your 'SHD' had not aborted >>>>>>> the simulation, it *would* have ultimately reached a final state. >>>>>>So an infinite loop eventually halts if you just wait long enough.
Of course not. But there is no such loop involved in the case under
consideration. This is obvious to everyone participating in this
thread other than you.
André
Even Richard knows that this never stops running unless aborted:
When Ĥ is applied to ⟨Ĥ⟩
Ĥ copies its input ⟨Ĥ0⟩ to ⟨Ĥ1⟩ then embedded_H simulates ⟨Ĥ0⟩ ⟨Ĥ1⟩
Then these steps would keep repeating:
Ĥ0 copies its input ⟨Ĥ1⟩ to ⟨Ĥ2⟩ then embedded_H0 simulates ⟨Ĥ1⟩
⟨Ĥ2⟩
Ĥ1 copies its input ⟨Ĥ2⟩ to ⟨Ĥ3⟩ then embedded_H1 simulates ⟨Ĥ2⟩
⟨Ĥ3⟩
Ĥ2 copies its input ⟨Ĥ3⟩ to ⟨Ĥ4⟩ then embedded_H2 simulates ⟨Ĥ3⟩
⟨Ĥ4⟩...
But the loop isn't an infinite 'Do Loop', so Anre is RIGHT, there is
no infinite Do Loop involved.
You are just being sloppy.
Here is the context of the mistake that I was responding to:
On 4/2/2022 6:58 PM, André G. Isaak wrote:
it is obvious that if your 'SHD' had not aborted the
simulation, it *would* have ultimately reached a final state.
"it *would* have ultimately reached a final state."
refers to the simulated input.
But a PROPERLY simulated input WOULD reach the final state.
On 4/2/22 9:53 PM, olcott wrote:
On 4/2/2022 8:31 PM, Richard Damon wrote:
On 4/2/22 9:20 PM, olcott wrote:
On 4/2/2022 8:17 PM, Richard Damon wrote:
On 4/2/22 9:06 PM, olcott wrote:
On 4/2/2022 7:48 PM, Richard Damon wrote:
On 4/2/22 8:36 PM, olcott wrote:
On 4/2/2022 7:23 PM, André G. Isaak wrote:
On 2022-04-02 18:12, olcott wrote:
On 4/2/2022 6:58 PM, André G. Isaak wrote:
Yes, if you abort the simulation, the simulation does not >>>>>>>>>>> reach a final state, but it is obvious that if your 'SHD' had >>>>>>>>>>> not aborted the simulation, it *would* have ultimately
reached a final state.
So an infinite loop eventually halts if you just wait long >>>>>>>>>> enough.
Of course not. But there is no such loop involved in the case >>>>>>>>> under consideration. This is obvious to everyone participating >>>>>>>>> in this thread other than you.
André
Even Richard knows that this never stops running unless aborted: >>>>>>>>
When Ĥ is applied to ⟨Ĥ⟩
Ĥ copies its input ⟨Ĥ0⟩ to ⟨Ĥ1⟩ then embedded_H simulates
⟨Ĥ0⟩ ⟨Ĥ1⟩
Then these steps would keep repeating:
Ĥ0 copies its input ⟨Ĥ1⟩ to ⟨Ĥ2⟩ then embedded_H0 simulates
⟨Ĥ1⟩ ⟨Ĥ2⟩
Ĥ1 copies its input ⟨Ĥ2⟩ to ⟨Ĥ3⟩ then embedded_H1 simulates
⟨Ĥ2⟩ ⟨Ĥ3⟩
Ĥ2 copies its input ⟨Ĥ3⟩ to ⟨Ĥ4⟩ then embedded_H2 simulates
⟨Ĥ3⟩ ⟨Ĥ4⟩...
But the loop isn't an infinite 'Do Loop', so Anre is RIGHT, there >>>>>>> is no infinite Do Loop involved.
You are just being sloppy.
Here is the context of the mistake that I was responding to:
On 4/2/2022 6:58 PM, André G. Isaak wrote:
it is obvious that if your 'SHD' had not aborted the
simulation, it *would* have ultimately reached a final state.
"it *would* have ultimately reached a final state."
refers to the simulated input.
But a PROPERLY simulated input WOULD reach the final state.
Ĥ.q0 ⟨Ĥ⟩ ⊢* UTM ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* H.qy
Ĥ.q0 ⟨Ĥ⟩ ⊢* UTM ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* H.qn
No so much
But that isn't what H^ is.
You are the one that continues to insist that only a UTM can properly
simulate an input and that this simulated input must never be aborted
or it becomes an incorrect simulation.
Right, but that doesn't mean you put a UTM there. H^ has a copy of H
there (that you are calling embedded_H), so that is wha must be there.
You are confusing the REQUIREMENTS of H with the algorithm H itself.
H <M> w needs to go to Qy if M w (or UTM <M> w) will halt and Qn if it doesn't, but that doesn't mean you get to put a UTM there, because a UTM doesn't meet the requirements, since it doesn't give the non-halting
answer in finite time.
H is NOT 'Computationally Equivalent' to a UTM, because its behavior IS DIFFERENT.
For the non-halting case, UTM will be non-halting, but H MUST be a
'halting computation' that goes to the 'Non-Halting Answer State'
These are DIFFERENT.
Is that the confusion what you wasted 17 years on?
We need to put the actual algorithm of H at the point that was prevously labled Qx (Linz names it HQ0 to distinguish it from the Q0 starting
state of H^), so that is what is in the representation of H^ there, the representation of its copy of H, and that is what a UTM will see, and presumably what your SHD will see.
The only point we pull out the UTM, is when AS DESIGNERS/TESTERS we want
to check if the answer that H gave was correct.
And, we are effectively doing that when we are just running H^ applied
to <H^>, as that is BY DEFINITION the behavior of UTM <H^> <H^>.
Yes, one (perhaps you will call UNFAIR) aspect of this is that H can't
just evaluate the requirements to get the right answer, but you should
know from any actually useful programming that rarely can you just code
'The Requirements' to implement the program, as if you could, then there would be no need to hire a programmer.
H can get SOME non-halting cases with a list of patterns, but it turns
out that there is no finite exhaustive list of patterns, which is why a
Halt Decider is not possible (or the answer WOULD be to just use a SHD
with that list of patterns).
On 4/2/22 11:09 PM, olcott wrote:
On 4/2/2022 9:34 PM, Richard Damon wrote:
On 4/2/22 9:53 PM, olcott wrote:
On 4/2/2022 8:31 PM, Richard Damon wrote:
On 4/2/22 9:20 PM, olcott wrote:
On 4/2/2022 8:17 PM, Richard Damon wrote:
On 4/2/22 9:06 PM, olcott wrote:
On 4/2/2022 7:48 PM, Richard Damon wrote:
On 4/2/22 8:36 PM, olcott wrote:
On 4/2/2022 7:23 PM, André G. Isaak wrote:
On 2022-04-02 18:12, olcott wrote:
On 4/2/2022 6:58 PM, André G. Isaak wrote:
Yes, if you abort the simulation, the simulation does not >>>>>>>>>>>>> reach a final state, but it is obvious that if your 'SHD' >>>>>>>>>>>>> had not aborted the simulation, it *would* have ultimately >>>>>>>>>>>>> reached a final state.
So an infinite loop eventually halts if you just wait long >>>>>>>>>>>> enough.
Of course not. But there is no such loop involved in the case >>>>>>>>>>> under consideration. This is obvious to everyone
participating in this thread other than you.
André
Even Richard knows that this never stops running unless aborted: >>>>>>>>>>
When Ĥ is applied to ⟨Ĥ⟩
Ĥ copies its input ⟨Ĥ0⟩ to ⟨Ĥ1⟩ then embedded_H simulates
⟨Ĥ0⟩ ⟨Ĥ1⟩
Then these steps would keep repeating:
Ĥ0 copies its input ⟨Ĥ1⟩ to ⟨Ĥ2⟩ then embedded_H0 simulates
⟨Ĥ1⟩ ⟨Ĥ2⟩
Ĥ1 copies its input ⟨Ĥ2⟩ to ⟨Ĥ3⟩ then embedded_H1 simulates
⟨Ĥ2⟩ ⟨Ĥ3⟩
Ĥ2 copies its input ⟨Ĥ3⟩ to ⟨Ĥ4⟩ then embedded_H2 simulates
⟨Ĥ3⟩ ⟨Ĥ4⟩...
But the loop isn't an infinite 'Do Loop', so Anre is RIGHT,
there is no infinite Do Loop involved.
You are just being sloppy.
Here is the context of the mistake that I was responding to:
On 4/2/2022 6:58 PM, André G. Isaak wrote:
it is obvious that if your 'SHD' had not aborted the"it *would* have ultimately reached a final state."
simulation, it *would* have ultimately reached a final state. >>>>>>>>
refers to the simulated input.
But a PROPERLY simulated input WOULD reach the final state.
Ĥ.q0 ⟨Ĥ⟩ ⊢* UTM ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* H.qy
Ĥ.q0 ⟨Ĥ⟩ ⊢* UTM ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* H.qn
No so much
But that isn't what H^ is.
You are the one that continues to insist that only a UTM can
properly simulate an input and that this simulated input must never
be aborted or it becomes an incorrect simulation.
Right, but that doesn't mean you put a UTM there. H^ has a copy of H
there (that you are calling embedded_H), so that is wha must be there.
But (according to you) H cannot be there or it will get the simulation
wrong.
You are confusing the REQUIREMENTS of H with the algorithm H itself.
H <M> w needs to go to Qy if M w (or UTM <M> w) will halt and Qn if
it doesn't, but that doesn't mean you get to put a UTM there, because
a UTM doesn't meet the requirements, since it doesn't give the
non-halting answer in finite time.
H is NOT 'Computationally Equivalent' to a UTM, because its behavior
IS DIFFERENT.
H simulates finite sequences of configurations 100% exactly the same
way that a UTM does because it invokes its own internal UTM one step
at a time.
For the non-halting case, UTM will be non-halting, but H MUST be a
'halting computation' that goes to the 'Non-Halting Answer State'
These are DIFFERENT.
Is that the confusion what you wasted 17 years on?
We need to put the actual algorithm of H at the point that was
prevously labled Qx (Linz names it HQ0 to distinguish it from the Q0
starting
No he did not: https://www.liarparadox.org/Linz_Proof.pdf
I remembereded his notation wrong. He call the state that is the
beginning of the orignial code for H starting at q0 with the name H^q0
Which is why the string execution paths are listed as:
q0 wM -> H^q0 wM wM -> H^ infinity [If M applied to wM Halts]
q0 wM -> H^q0 wM wM -> H^y1Qny2 [If M applied to wM never halts]
My latest notation is much better than his:
Ĥ.q0 ⟨Ĥ⟩ ⊢* H ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* H.qy
Ĥ.q0 ⟨Ĥ⟩ ⊢* H ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* H.qn
Except that you drop the conditions
state of H^), so that is what is in the representation of H^ there,
the representation of its copy of H, and that is what a UTM will see,
and presumably what your SHD will see.
The only point we pull out the UTM, is when AS DESIGNERS/TESTERS we
want to check if the answer that H gave was correct.
And, we are effectively doing that when we are just running H^
applied to <H^>, as that is BY DEFINITION the behavior of UTM <H^> <H^>. >>>
Yes, one (perhaps you will call UNFAIR) aspect of this is that H
can't just evaluate the requirements to get the right answer, but you
should know from any actually useful programming that rarely can you
just code 'The Requirements' to implement the program, as if you
could, then there would be no need to hire a programmer.
H can get SOME non-halting cases with a list of patterns, but it
turns out that there is no finite exhaustive list of patterns, which
is why a Halt Decider is not possible (or the answer WOULD be to just
use a SHD with that list of patterns).
All patterns are entirely comprised of a small set of elemental
patterns this is very well known stuff.
Nope. Care to provide a reference that lists a COMPLETE set of
non-halting patterns?
Yes, there are a number of basic loops that can become unending, but no COMPLETE list (as has been proven).
An algorithm is made up of three basic building blocks: sequencing,
selection, and iteration.
https://www.khanacademy.org/computing/ap-computer-science-principles/algorithms-101/building-algorithms/a/the-building-blocks-of-algorithms
So, what does that prove.
Simple blocks can create enormous complexity.
That also isn't really a complete definition, maybe right for a 101
level introductory course, but not for rigorous application.
If THAT is you source for Computer Science Definitions no wonder you are
so messed up.
| Sysop: | Keyop |
|---|---|
| Location: | Huddersfield, West Yorkshire, UK |
| Users: | 297 |
| Nodes: | 16 (2 / 14) |
| Uptime: | 100:34:13 |
| Calls: | 6,659 |
| Calls today: | 1 |
| Files: | 12,208 |
| Messages: | 5,334,754 |