next up previous contents
Next: Pumping Lemma Up: Properties of Regular Sets Previous: Properties of Regular Sets

digression on nature of class

What questions do we want to answer -- what is computation? What do different architectures mean? Can we come up with a fundamental definition of computation.

Class is not limited to Turing machines or analogs, but it makes sense to start there.

Computation as algorithm

Computation as tool for reducing uncertainty (Han). Information theoretical take on computation. Is signal processing computation?

Information manipulation can be computation - what does it take? Are linear operations computation? Is there a computation phase transition?

Tie physics to operations as a way of narrowing computation - deal with non-infinite resources. (Ben)

Qbits mentioned - Qbit annihilation.