Last week, in the class I’m teaching, we talked about the basics of deterministic finite automata. In week two we moved on to more interesting and slightly less basic material. In particular we introduced the notion of a nondeterministic finite automata and, by the end of the week, had showed that the class of languages accepted by deterministic finite automata is exactly the same class of languages accepted by nondeterministic finite automata.
What I love about this basic material is that you take a seemingly crazy idea: machines that can follow multiple computational paths at the same time, and it turns out to be useful! But, even more amazing, at least to me, is that it doesn’t give you any more “expressive” power beyond deterministic automata: anything recognizable by deterministic finite automata is also recognizable by a nondeterministic finite automata and vice versa. This kind of thinking: “imagine a computing device that works this way, yes I know the world doesn’t work that way, but just imagine and see where it goes” is, to me, very cool, and almost enough to make me believe what those crazy Platonic realists talk about when they mumble about mathematics and reality.
Processes like this are also one of the reasons that I think theoretical computer science isn’t as far from theoretical physics as many would have you believe. The best of theoretical physics involves thinking up seemingly crazy explanations (would you have written down asymptotic freedom? Okay, if your t’Hooft, maybe! How about quantum mechanics, would you have gotten that one?) and then following through what these crazy ideas imply. More often than not they lead to dead ends. But, in both fields, when they do lead to new ideas, they are revolutionary ideas: quantum physics, nondeterministic Turing machines, special relativity, interactive proofs, and more.
For those with nothing more to do than read my notes, this weeks are pasted below:
O brave new quantum world!
Why not introduce something about the quantum finite automata,quantum cellular automata and etc ?:)
and ..Your lecture slices are somewhat boring,not like the style of Sipher’s book–introduction to the theory of computation,which can easily trigger our interests..:)
I like your comparison of Theoretical CS and Physics and it is something i would like you to also write about more. Not many folks like to give thought to at such an abstract level 🙂
Zhimin Hua: this is a theory course for computer science majors. I suspect that I would introduce Markov networks before I tried quantum finite automata! What are “slices” and who is “Sipher”?