"Identify something that you liked in COS 487 (Theory of Computation) in F'00. Express your thoughts in prose or verse."
Excerpts from the class's responses:
All NP problems
Here comes digital security
Reliability, scalability, efficiency --we want
all these services...
Of Goedel, laughing, did I dream
I never imagined that taking a random walk in a
graph can be of
Take a math system..
Perhaps the coolest, most unbelievable thing I
learnt in class was
Caesar encoded messages for protection
|Jared Kramer (in the style of "The Waste Land")
Of what use is a Pushdown Automaton? I know of no living adventurer who has claimed to see a nondeterministic
creature with a stack of infinite capacity...
How to make a Hamiltonian Path out of a boolean formula. I wanted to know how to make a subset sum problem
out of a boolean formula...
...in the eyes of "God," everything is deterministic (if God exists and determines everything), while a human, unable to understand precisely what happens in the world (as Physics shows, there are limitations on how humans can understand the world), can only handle this unpredictability with a probability model: that's what we call "randomness."
It would be incredibly difficult and mind boggling to think about the computation histories or configurations of a modern PC...with gigabytes of memory, we quickly approach a state size bigger than we could ever use in all of our lifetimes put together. ...(Yet) we could, in theory, detect if our machine is caught in a loop..
CS487 has begun to make me wonder whether the theory of computation is approaching its boundaries of constructive observation, particularly its ability to prove some of the hierarchy conjectures. When does a theoretical framework exhaust its ability to give constructive and innovative insights into human intellectual ability?
..makes me wonder if a human being is ultimately one giant Turing machine. If so, one day it should be possible for us to get a complete description of ourselves and then simulate ourselves!...
..because modern computers are unsuccessful in emulating human intelligence, I do believe there exists a kind of computation model that is more powerful than a Turing machine...
The more you learn, the more puzzled you are. Something decidable, but we cannot give a direct answer to it, such as whether God exists. Something intuitively obvious, but we..have no proof, such as NP ?= P...
Several sets of problems
..how to measure parallel complexity? ...Systems people always argue whether message passing or shared variables is better. If we could find a lowerbound, they could stop this arguing...
My imagination was fired by the relationship
between P and NP.