Re: Linz's proofs.

Andy Walker <anw@cuboid.co.uk> writes:

On 05/03/2024 11:59, Ben Bacarisse wrote:

I started this thread and now find myself with little time to talk about
the replies.  Sorry.

>
Join the club!
>

I'm not exactly sure what your objection to the second form is.

>
I don't have an "objection";  I merely think it's a little
harder for the non-mathematical student.  That's a /little/, not a
/lottle/.
>

    All of
the forms require some conditional reasoning.  For example, if TM#1 does
not always halt then it's not a decider of anything and we can move on
to TM#2.

>
Yes, but we don't in general know whether TM#n always halts, never
halts or sometimes halts.  At some level it doesn't matter, for the reasons
we all know.  But we're left trying to explain to the student how and why
our ignorance doesn't matter.  That's why it's slightly easier in some other
versions.  If you claim that TM#123456 /is/ a HD, then you are already
[tho' you may not have realised it] claiming that it always halts, and so
the usual construction proves that it /isn't/ a HD, and your claim fails.
If you don't make the claim, then we don't know whether this TM halts on
particular inputs, in particular the "self-contradictory" input, and we
get into a bit of a conditional mess.  Yes, it's all very easy for you
and me and Mike and ..., but we're not the target weak students.

Well I see what you mean, but I don't think that ever came up a source
of confusion, but it was, now, a long time ago.

    We don't have to *know* if it halts or not, all we need to
know is that if it always does, then there is a constructable input for
which the result of TM#1 does not match that of the halting function.

>
"Please, Sir, how do we know whether it always does?"

The students I taught seemed to have no problem with this sort of case
analysis.  But the "assume H does X" argument lead to lots of "but H1
could be better" arguments.
--
Ben.