A universal Turing kernel?

At the end of my talk, someone asked why I focus exclusively on DFAs. After all, my result that any countable concept class over a countable sample space is linearly separable (in this sense) works equally well for push-down automata or even Turing machines. My first (mildly petulant) answer is that DFAs are the only automata I'm comfortable with and I won't be ready to move on to more powerful automata until someone resolves the star-height problem (at which point I'll grudgingly grant humanity the right to graduate on to higher machines).

Someone else was quick to suggested that the analogous kernel for Turing machines, T_n(x,y), would have to count the number of Turing machines on n states that accept both x and y -- and surely this is undecidable. But is that obvious? Might there not be some clever way of computing the kernel without solving the halting problem?

Turns out, there is not; this was shown by Jeremiah Blocki, a student in my class -- who, incidentally, has taken up the challenge of the notorious problem #3.

Proofs by induction

When we teach proofs by induction in high school or early undergrad, they tend to be rather simple. Or rather, the induction tends to be "trivial" in the sense that it's obvious
1. what structure to do the induction over
2. how to decompose the claim for n+1 so as to invoke the inductive hypothesis

Examples of such simple uses of induction include proving the sum-of-squares-(cubes, etc.) formula, and proving that if a language L is context-free then so is its reversal L^R.

We the instructors somewhat lament this state of affairs, as it gives a misleading impression of induction. A student might dismiss induction as trivial and vacuous, or on the contrary, come away believing that induction is a magical, all-powerful tool that does proofs for you, relieving you of the burden of thought.

So we looked hard for examples of clever use of induction. Here's a good problem to start with:
Let f_p(n) be the sum of the first n powers of p:
f_p(n) = 1^p + 2^p + 3^p + ... + n^p.
For any given p (say, p=3), it is straightforward to verify (by trivial induction!) the f_3(n) is a 4th degree polynomial in n. It's a lot trickier to prove that for all p, f_p(n) is a polynomial in n of degree (p+1). Can you do it? No need to invoke Bernoulli numbers here -- we're not asking for the coefficients of that polynomial. There are a couple of elementary, self-contained proofs -- using clever induction! -- can you find one?

Actually, all of my difficult proofs have been by induction. Various concentration of measure results (Talagrand, Marton, yours truly) have induction at their core. It's a shame we can't present these in a typical undergraduate class (too much overhead), since their use of induction is rather non-trivial.

Do people have more examples of nontrivial proofs by induction?

Quantum disinformation

Check out the discussion over at Scott's blog. It covers a wide range of topics, including: the (typically) shoddy mainstream journalistic coverage of technical material, the powers/limitations of quantum computing, and finally, something near and dear to my heart -- the nature and role of mathematical proofs.

Minimal consistent DFA revisited

I'm glad we ended up putting this problem on the midterm (as extra credit). A handful of folks nailed it dead-on, but it's still causing confusion for some -- which means it's a good one to work out! Now that it's been assigned and graded, the readers are invited to say anything and everything they want about it in the comments.

BTW, the problem of finding the minimal consistent DFA is NP-hard; this fact more or less motivates the line of research I'll be presenting at this talk tomorrow (today).

Linear/convex programming in infinite dimensions?

I'm sure I'll find the answer in Rudin's Functional Analysis, but perhaps a helpful reader will educate me and the rest; otherwise, what's the point of blogging?

Say we have a Hilbert space H -- so it's locally convex and the Krein-Milman theorem applies. Let K be a compact convex set in H. Is it still true that linear functionals achieve their maxima on extreme points of K? What about convex functionals? [I should really look up the latter in the last chapter of Borwein and Lewis.]

Seems like these should be true, but I've learned to mistrust my intuition in high (and a fortiori infinite) dimensions. Anyone have an answer handy?

Arbitrarily large vs. infinite

Infinity is a subtle mathematical notion, which is logically related to -- but not synonymous with! -- the notion of "arbitrarily large". Actually, when dealing with limiting values of magnitudes, the two more or less coincide. When we say that the series
1 + 1/2 + 1/3 + 1/4 + ... = Infinity
what we mean is that no matter now big of an N you pick, I can always find enough terms in that series whose sum will exceed N. In this case, infinite really is shorthand for "increasing without bound" or becoming "arbitrarily large".

When dealing with cardinalities -- as opposed to magnitudes -- all bets are off. That was the crux of the closure under star question. [BTW, I think I've found the bug in Ivan's proof that closure under concatenation implies closure under star. The set U need not be a complete lattice. Otherwise, your argument could be used to show that the function f:Z->Z defined on the integers by f(x)=x+1 has a fixed point.] Set theory is rife with examples where some property P holds for arbitrary finite collections but not infinite ones:

• in point-set topology, a finite (but not necessarily countable) intersection of open sets is open
• in analysis, there are finitely (but not countably) additive measures
• etc

There are techniques, most (all?) of them based on transfinite induction, for proving that P holds for infinite collections given that it holds for arbitrary finite ones. Knaster-Tarski is one; Hausdorff maximality principle and Zorn's lemma are other favorites. All are equivalent to the axiom of choice.

"Progressive" math

Alexandre Borovik's blog is my usual source of examples of semi-literate math-is-being-used-for-evil hysteria. Staying true to this blog's mission statement, I sincerely endeavor not to excessively dilute the mathematical content with politics. I also make it a general principle to rebuke outrageous claims only if they are championed by a reasonably reputable source; life is too short to engage in reasoned intellectual discourse with every obscenity-shouting hobo in the street.

For this reason, though I had seen the unhinged, lunatic rants quoted here about a week ago, I didn't see fit to address them, basically relegating this to the hobo-in-the-street category. Brief synopsis: math has cryptographic and defense applications, and we all know these are tools of imperialistic oppression to keep down the working class, man. (I am hoping that the quote by Rabelais about the evil use of frontal lobes is meant to parody Ken Burch and Kevin Laddle, but one can't know for sure.)