Contents

• Introduction - The limits to computation
• Some limits on neural networks - linear associator
• Some limits on neural networks - Hopfield net
• Limits on learnability
• Limits on space
• Limits on speed - complexity theory
  • Sorting
  • The travelling salesman problem
• Complexity theory and psychology
• Complete impossibilities
• The decision problem
• Turing-equivalent computers, and Turing-computable problems
• The halting problem
  • A short proof
  • Other proofs
• What is computation? The Turing machine
  • The Universal Turing Machine
• Uncomputable numbers
• Uncomputable numbers and infinity
• About this document ...

AI lecture 7

Jocelyn Ireson-Paine