Path: csiph.com!eternal-september.org!reader02.eternal-september.org!.POSTED!not-for-mail From: Ben Bacarisse Newsgroups: comp.theory Subject: Re: Clarification of Linz =?utf-8?Q?=C4=A4?= Description [ Are we there yet ? ] (V3) Date: Sat, 02 Oct 2021 23:00:54 +0100 Organization: A noiseless patient Spider Lines: 75 Message-ID: <877devf5nt.fsf@bsb.me.uk> References: <2436d983-22f8-4555-9a9f-1e9fb3044e9fn@googlegroups.com> <9f6dnVe1rdbIpsr8nZ2dnUU7-avNnZ2d@giganews.com> <1qmdnWxwZob91cr8nZ2dnUU7-LXNnZ2d@giganews.com> <871r54jwzc.fsf@bsb.me.uk> <87pmsoidwg.fsf@bsb.me.uk> <87r1d4guf9.fsf@bsb.me.uk> <_uudnTHi8b9L9MX8nZ2dnUU7-eHNnZ2d@giganews.com> <87lf3bh31u.fsf@bsb.me.uk> Mime-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: 8bit Injection-Info: reader02.eternal-september.org; posting-host="0f9923d1833c2f42daa3b77525dc9b37"; logging-data="18562"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1+hqb6P/1MkQ8E/gs90PY+26Q2dTmc9FhA=" Cancel-Lock: sha1:mWoVsrhz2soLU8gh/8rY5d83ISU= sha1:eaRGJ1ksbFK9F5uIvcJQRvcDAWQ= X-BSB-Auth: 1.4e34238e8f1c8c768320.20211002230054BST.877devf5nt.fsf@bsb.me.uk Xref: csiph.com comp.theory:40267 olcott writes: > On 10/2/2021 10:14 AM, Ben Bacarisse wrote: >> olcott writes: >> >>> On 10/2/2021 5:54 AM, Richard Damon wrote: >>>> On 10/2/21 12:10 AM, olcott wrote: >> >>>>> -----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 applied >>>> to 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. >> >> The TM described by ⟨Ĥ⟩ is Ĥ. (1) is Ĥ, the TM described by ⟨Ĥ⟩. (2) >> (the string to which (1), AKA Ĥ, is applied) is ⟨Ĥ⟩. The line describes >> what Ĥ applied to ⟨Ĥ⟩ should do but, crucially, only if Ĥ applied to ⟨Ĥ⟩ >> does not halt. You always leave this last part of the specification >> out for obvious reasons. > > The problem is that when Linz refers to wM he calls it M. No he does not. Can you quote him making this gross error? (I'm going to put the subscripts back in what follows). > The input to H will be the description in (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. Yes, there is no "M in H". (I'm going out on a limb here because it's not clear what you mean by that odd phrase. You don't understand bound and free variables so it would be hard to explain why it's such an odd thing to say.) All he refers to a string, w_M, as part of the input to H. That's not "[referring] to an M in H". That string, w_M, is the encoding of a TM. How else could H be presented with a halting problem instance? > To correct this error > if the TM described by wM applied to w does not halt. Or just "M applied to w does not halt". > There is no M in Ĥ, yet he refers to an M in Ĥ > q0 wM ⊢* qx wM wM ⊢* qn > if M applied to wM does not halt He refers to a string w_M as the sole input to Ĥ. (And you really should put the subscripts back on the ⊢*.) > To correct this error > if the TM described by wM applied to wM does not halt. Or just as Linz puts it, if M applied to wM does not halt. You seem not to have grasped what Linz is saying. How long have you been studying these three pages? Nine years? > There is only one instance of > TM described by wM applied to wM in the above: qx(wM, wM) There are none, in fact. This will take about six months for you work out, and that's only if you really try to work it out. -- Ben.