Computation

• What do the terms "NP", "P", and "NP-complete" refer to?
  NP.pdf
• What is a finite state machine? What is a Turing machine? What is the Church/Turing thesis?
  FSM.pdf
• Marr described three levels at which an information processing device might be understood: computational, representation/algorithmic, and hardware implementation. Describe, with examples, each level.
• How would you compare the computational power of a cortical pyramidal cell with that of a desktop computer? Be specific about your criteria for computational power.
• Show how to compute the Boolean functions AND and OR using a linear threshold element.
  lt.pdf
• Prove that XOR can not be computed by a single linear threshold element. Show how to compute XOR using a two-layered circuit of AND, OR and NOT gates. Is this construction optimal in size?
  lt.pdf
• What characterizes "Von Neumann" computing? Discuss its plausibility as a metaphor for the human brain.
• We can read everywhere that the brain is a "complex adaptive system". What is meant by this vague statement? In what context has complexity be defined?

Return to regular view	Text-only	Updated: 11/16/2009