On 2021-10-02 09:31, olcott wrote:
The problem is that when Linz refers to wM he calls it M.
The input to H will be the description (encoded in some form) of M,
say wM, as well as the input w.
There is no M in H, yet he refers to an M in H
q0 wM w ⊢* qn
if M applied to w does not halt.
To correct this error
if the TM described by wM applied to w does not halt.
How on earth is this an "error"?
wM means the description of M.
"the TM described by wM" and "M" mean exactly the same thing. What need
is there for adding this extra verbiage?
André
On 10/2/21 1:32 PM, olcott wrote:
On 10/2/2021 12:04 PM, Richard Damon wrote:
On 10/2/21 12:39 PM, olcott wrote:
On 10/2/2021 11:02 AM, Richard Damon wrote:
On 10/2/21 11:29 AM, olcott wrote:
On 10/2/2021 10:08 AM, Richard Damon wrote:
On 10/2/21 10:26 AM, olcott wrote:
On 10/2/2021 9:16 AM, olcott wrote:
On 10/2/2021 5:54 AM, Richard Damon wrote:
On 10/2/21 12:10 AM, olcott wrote:
On 10/1/2021 7:08 PM, Ben Bacarisse wrote:
olcott <NoOne@NoWhere.com> writes:
On 10/1/2021 5:22 PM, Ben Bacarisse wrote:
olcott <NoOne@NoWhere.com> writes:
On 10/1/2021 3:44 PM, Ben Bacarisse wrote:Linz is not wrong about how he himself specifies the behaviour >>>>>>>>>>>>>> of Ĥ.
Oh dear, you've posted about TMs again...---1----2-----3-----4--5-----6
olcott <NoOne@NoWhere.com> writes:
Ĥ.q0 ⟨Ĥ⟩ ⊢* Ĥ.qx ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* Ĥ.qn >>>>>>>>>>>>>>>> And the correct annotation for this line is "if (and only >>>>>>>>>>>>>>>> if) Ĥapplied
to ⟨Ĥ⟩ does not halt".
Flat out totally incorrect.
It's his specification. You /could/ reject that
specification,
but in
fact you insist that you only ever use Ĥ to refer to Linz's Ĥ. >>>>>>>>>>>>>> You dishonestly leave off a key part of his specification >>>>>>>>>>>>>> because
you
don't want to keep seeing the problem.
Ĥ.qx(⟨Ĥ⟩, ⟨Ĥ⟩) the simulation of the input to Ĥ.qx never
reaches
its
final state whether or not Ĥ.qx aborts this simulation >>>>>>>>>>>>>>> therefore
the
transition of Ĥ.qx to Ĥ.qn is correct.
What is correct is determined by the annotation you keep >>>>>>>>>>>>>> dishonestly
omitting. Ĥ(⟨Ĥ⟩) transitions to Ĥ.qn if (and only if) Ĥ(⟨Ĥ⟩)
does not
halt.
That is flatly false.
No, it's right there in Linz. It's dishonest to remove the key >>>>>>>>>>>> thing
about the line you keep writing, but I know you have to >>>>>>>>>>>> remove it.
There is no other way for you to avoid Linz's conclusion. >>>>>>>>>>>>
Beginning with the Linz H
q0 wM w ⊢* qn
if M applied to w does not halt.
When Linz refers to M applied to wM there is no M in the Linz >>>>>>>>>>> template
so we have to go back to these words to see what M applied to wM >>>>>>>>>>> means:
NO. Maybe you don't understand what a 'Formal Parameter' is. Let >>>>>>>>>> us go
back to what Linz said:
The input to H will be the description (encoded in some form) >>>>>>>>>>> of M,
say WM, as well as the input w.
So M is the Turing Machine previous mentioned in the
description of
what
the Halting Problem's Question was:
Simply stated, the problem is: given the description of a Turing >>>>>>>>>>> machine M and an input w, does M, when started in the initial >>>>>>>>>>> configuration qow, perform a computation that eventually halts? >>>>>>>>>>So M is NOT an 'undefined term that we need to figure out what it >>>>>>>>>> means', that is a lie.
M is the machine that the decider is supposed to decider, it is in >>>>>>>>>> Software Engineering terms, a Formal Parameter to the Halting >>>>>>>>>> Decider.
Just like when we write the definition of H(P,I) as a function >>>>>>>>>> definition, the P and I are the names of the Formal Parameters, >>>>>>>>>> that
when we later call H(H_hat, H_hat) get filled in by the values >>>>>>>>>> from
the
calling site.
Is that why you suddenly changed the name of the machine to be >>>>>>>>>> decided,
because having the formal parameter named P and the passed >>>>>>>>>> parameter
named H_hat was too confusing for you?
The input to H will be the description (encoded in some form) of >>>>>>>>>>> M, say
wM, as well as the input w.
M applied to wM means: The TM described by wM applied to w. >>>>>>>>>>>
Right, the question is about the behavior of the ACTUAL Turing >>>>>>>>>> Machine
Now onto the Linz Ĥ
---1---2--------3---4---5-------6
q0 wM ⊢* qx wM wM ⊢* qn
if M applied to wM does not halt
is translated into
The TM described by wM applied to wM does not halt
is translated into
The TM described by ⟨Ĥ⟩ applied to ⟨Ĥ⟩ does not halt >>>>>>>>>>>
----1----2-----3-----4--5-----6
Ĥ.q0 ⟨Ĥ⟩ ⊢* Ĥ.qx ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* Ĥ.qn
There is only one place in the above where this exists:
The TM described by ⟨Ĥ⟩ applied to ⟨Ĥ⟩
Right, so the question is does the TM which is described by <H^> >>>>>>>>>> applied
to <H^> Halt, and that is exactly your (1) applied to (2) which >>>>>>>>>> you
show
The TM described by ⟨Ĥ⟩ applied to ⟨Ĥ⟩ does not halt >>>>>>>>> (1) is not a TM description, proving that you are wrong.
There is only one place where the TM described by ⟨Ĥ⟩ is applied to
⟨Ĥ⟩
and that is (4) and (5).
Is the problem honestly that you don't understand what Linz is
saying?
What is meant by a representation.
The problem is that when Linz refers to wM he calls it M.
No, he doesn't.
The input to H will be the description (encoded in some form) of M, >>>>>> say
wM, as well as the input w.
Read it again. M is the Turing Machine. wM is the description of M.
That is clear.
Yes, agreed.
There is no M in H, yet he refers to an M in H
q0 wM w ⊢* qn
if M applied to w does not halt.
H is given the input wM w, the representation of M w
and needs to decide what it will do.
Yes, agreed.
To correct this error
There is no error here (except by you)
if the TM described by wM applied to w does not halt.
Right, the TM described by wm is M.
The question is, does M w halt or not?
Yes, agreed.
There is no M in Ĥ, yet he refers to an M in Ĥ
Wrong.
M is the formal parameter, H^ is the actual parameter.
M cannot be any parameter at all, TMa are not allowed to be parameters, >>>> only TM descriptions are allowed to be parmeters.
Maybe I went above your head again. Yes, at the implementation level, H
needs to be given a representation. so it gets wM, but at the abstract
description of what it is being asked to do, it is being asked to decide >>> what Turing Machine M applied to input w will do. That make M a Formal
Parameter to the problem.
so, H taking Formal Parameters wM and w, is 'called' by the actual
parameters <H^> and <H^>
Yes, agreed.
Just like when we define H as H(P,I) and call it as H(H_hat, H_hat). >>>>>
q0 wM ⊢* qx wM wM ⊢* qn
if M applied to wM does not halt
To correct this error
if the TM described by wM applied to wM does not halt.
Right the TM described by wM is M which, is applied to w.
There is another one of your terrible careless mistakes.
There is no w in Ĥ.
Neither is there a wM, so you are being inconsistent.
----------1------------2---3----------
q0 wM ⊢* qx wM wM ⊢* qn
It is stupid mistakes like saying that there is no wM at (1) (2) and (3)
that cause me to not even glance at anything you say for several days.
Yes, H^ *ITSELF* does not have a w, but does have a wM, but the
definition of H still has a w as a formal parameter, as that is the definition of H.
When we look at what is supposed to happen at qx (which you are actually WRONG about Linz getting wrong here)
Linz state here is H^q0 not q0 so he gives it a unique name, there are
NOT two q0. (If we want to be pedantic).
So, at H^'s H^q0 which is essentially a copy of H's q0, we have as the
input tape wM wM which if we look at the definition of H, we see that H applied to wM w is supposed to predict what the machine M applied to w
will do. Appling these formal parameters we gets:
H's wM corresponds to H^'s wM
H's w corresponds to H^'s wM
Thus the sub-machine at H^q0 (aka PO-qx) is supposed to answer what the machine M, which is the machine described by H^s input wm would do when applied to the input wM to H^.
The next step in the proof, he applies this H^ machine to decide on H^,
by creating a w^ as the value for wM (so w^ is the description of H^)
and this means that H given w^ w^ needs to decide what H^ applied to w^
will do, which is the starting Computation of H^'s q0 being applied to w^.
From your claims, H^'s qx applied to w^ W^ will go to H^'s qn saying
that it is non-halting, (and thus that is exactly what H's q0 applied to
w^ w^ will say, since they are the same machine description with the
same inputs) but H^'s q0 applied to w^ will thus also end up in H^'s qn
which is a halting state.
Thus H says non-halting, but the actual machine is Halting.
Richard Damon <Richard@Damon-Family.org> writes:
On 10/2/21 12:34 PM, Ben Bacarisse wrote:
olcott <NoOne@NoWhere.com> writes:
<snip>M applied to wM means: The TM described by wM applied to w.
if M applied to wM does not halt
is translated into
The TM described by wM
I.e. M
applied to wM does not halt
You got it right this time. I think the w above is just a typo.
The q0 wM w ⊢* qn
is the specification of H, not H^.
H is applied to wM w as an input.
Yes, but that's not what I'm talking about. (And when I say he got it
right I juts mean it's not technically wrong. It's still a silly way to
put it.)
I'm talking about this line:
||| M applied to wM means: The TM described by wM applied to w.
I don't think he intended to write that lone w, but the whole digression
is peculiar so goodness knows what he meant.
But later on he does not use the same "translation", just a pointless renaming of M as "[t]he TM described by wM":
||| if M applied to wM does not halt
||| is translated into
|||
||| The TM described by wM applied to wM does not halt
| Sysop: | Keyop |
|---|---|
| Location: | Huddersfield, West Yorkshire, UK |
| Users: | 455 |
| Nodes: | 16 (2 / 14) |
| Uptime: | 97:26:11 |
| Calls: | 9,317 |
| Calls today: | 3 |
| Files: | 13,530 |
| Messages: | 6,079,030 |
| Posted today: | 1 |