Hoping they release a tldr version called Sublinear Times.

One positive aspect is that it’s easier to see the proof as an algorithm. So i ask them to code it up and the tests give them feedback as to whether they understand the format of the proof. It also makes it much easier to scaffold for them.

I wrote up some notes at williamumboh.com/comp30026-20...

Yeah, we are marking the exams now. I think it went really well! I went with fooling sets instead of pumping lemma to prove non regularity. Feedback from the tutors and students have been positive.

Ah ok, good point, thanks!

The usual diagonalization proof avoids the encoding issue as it constructs a machine D that on input <M> runs H on <M>, <M> and does the opposite.

Clearly, L cannot exist since it accepts w iff it rejects w. QED.

Does this work?

Suppose, towards a contradiction, that there is a machine H that can decide if any given Turing machine M accepts any given input string w.

Consider the following machine L:

On input w:
Run H to see if L accepts w
Accept if H rejects
Reject if H accepts

Wow, outsold monopoly! youtu.be/Hxn0NUbIVbo?...

I spend way too much time grep-pling text files as well

launch party when?

English is an unpossible language