Earlier in the spring, I went to St. Anselm's to see the Priory Players put on scenes from plays by Neil Simon and David Ives. It was my impression that Ives makes Simon look like Chekhov; a neighbor active in the local theatre community says that this was very early Ives, so perhaps it was as if I were to judge Jane Austen by Love and Freindship.
.I did enjoy the pieces by Ives, though. And in watching "Words, Words, Words", three chimpanzees trying to write Hamlet, I found myself suddenly recalling a computability class taking about 20 years ago, in particular what I find are theorem 7.7 and lemma 7.2 of Hopcroft and Ullman, on Turing machines as enumerators::
Theorem 7.7 A language is [recursively enumerable] if and only if it is G(M1) for some [Turing machine] M1.
Lemma 7.2 If L is recursive, then there is a generator for L that prints the words of L in canonical order and no other words.
I blame this on a neighbor, since moved to Australia, who selected Charles Stross's Accelerando for the neighborhood book club. Among the many technical terms--Thompson hack, anyone?--was Turing complete; just to check that I remembered correctly, I pulled the Hopcroft & Ullman off the shelf and spent a little, enjoyable time going through chapters 7 and 8. And I enjoyed Accelerando.
(By the way, the items above certainly do not appear as such in more recent editions of Introduction to Automata Theory, Languages, and Computation, which has been beefed up--I'm guessing they're in Chapter 9..)
No comments:
Post a Comment