No Title
Next:
Contents
Back:
to main list of student notes
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 ...
Next:
Contents
Back:
to main list of student notes
Jocelyn Ireson-Paine
Wed Feb 14 23:47:23 GMT 1996