For all I know, this sort of thing could be a common technique (perhaps on the order of “Why did the chicken cross the road?” for this crowd), but I found it amusing. (After a little searching, I think my class experiences were likely related to MAX-SAT.)

]]>Indeed, for each M_i there are infinitely many strings s on which M_i gives the “wrong” answer: s in L but not in L(M_i), or s not in L but in L(M_i). Consider M_0 and feed it one after the other strings from the standard string enumeration until you find an s as above; call it s_0. Consider M_1 and do the same until you find an s as above and different from s_0; call it s_1. And so on. Every string eventually appears in the sequence s_0, s_1, … (since any single string is accepted by infinitely many M_i and rejected by infinitely many M_i). Thus s_0, s_1,… is a permutation of the original enumeration of strings and when fed into M_0, M_1, … the diagonalization criterion produces L.

It is safe to say that the above joke teaches us nothing whatsoever about P, NP, PSPACE… or for that matter anything else. ðŸ™‚

]]>The Law Teacher advertised that he was so good, that his students were all guaranteed to win their first lawsuit, or their tuition money would be returned.

His first student sued the teacher immediately after graduating.

Student: “This is my first case. If I win, then I win, so I get my money back. If, on the other hand, I lose, then I will have lost my first case, so then I win, because according to the contract, I get my money back. Hence, whether I win or lose, I get my money back. QED.”

In front of the judge, the teacher waits his turn, and then speaks in his defense.

Teacher: “My student has learned a little, but not enough. It is not germane whether that is my fault or his. Be that as it may, if I win the case, then I win, he loses, and he collects nothing besides the experience. Not a drachma of mine need be forked over. If, to the contrary, I lose the case, then, per the contract, the student did NOT lose the first case, and thus is not entitled to the money back. Hence, if I win, he loses, and if I lose, he loses. Either way, I need pay nothing. QED.”

So, what does the judge do?

[Comment: the Law is not axiom-based, but precedent-based]

]]>In particular, $P^A\not=NP^A$ with probability 1.

]]>Mathematical neophytes might also be amused by “joke theorems” like this (and variations):

Theorem: Every natural number is interesting.

Proof: If not, then by well-ordering, the set of uninteresting natural numbers has a least element n. The number n, being the smallest uninteresting natural number, is therefore pretty interesting. Hence the theorem follows by contradiction.

No, it means I agree with you that there is something we disagree upon, but we might both be wrong, in which case we would think we disagreed about something even though in fact we always agreed.

This could actually occur in practice:

You: “Hey, didn’t we disagree about something years ago?”

Me: “Yeah, that sounds familiar, although I can’t remember what it was. I guess this means there is indeed at least one thing we disagree about.”

Even assuming our opinions haven’t changed (let’s assume we’re both terribly set in our ways), we could be wrong. For example, we could be hazily remembering a time when we disagreed vehemently with some third party.

The upshot is that agreeing on something doesn’t mean it must be true. ðŸ™‚

]]>A proof that there is at least one thing we will both disagree upon.

Claim: There is at least one thing we will both disagree upon.

Proof: You can either agree or disagree with the claim.

If you agree then QED.

If you disagree then QED.