+---------------------------------------------------------------------------+
|                              Computation                                  |
+---------------------------------------------------------------------------+

Theory of Computation
	What can and cannot be calculated by a computer?
	Models
		Turing machine
		Lambda Calculus
		Equivalency tests between models
	Computability Theory
		Godel's Incompleteness Theorem
			* Implies that not all mathematical questions are computable
			What does this mean?
			"Godel's first incompleteness theorem shows that any such system
			that allows you to define the natural numbers is necessarily
			incomplete: it contains statements that are neither provably true
			nor provably false."
			Books
				The Undecidable : Basic Papers on Undecidable Propositions,
				Unsolvable Problems and Computable Functions
				by Martin Davis (Editor) ISBN: 0486432289
		Decidability
			Decidable problem: A decision problem that can be solved by an
			algorithm that halts on all inputs in a finite number of steps.
			Undecidable problem: A problem that cannot be solved for all cases
			by any algorithm whatsoever.
			(http://www.nist.gov/dads/HTML/undecidableProblem.html)
			* Whether or not there exists an algorithm for a class S of questions
			  requiring a Boolean answer
			* Halting problem
			* Entscheidungsproblem
			* Post correspondence problem
				One of the easiest examples
				I don't understand why this is undecidable... researching...
				http://www.cs.ualberta.ca/~zhao/PCP/intro.htm
					http://www.tucs.fi/publications/techreports/TR357.ps.gz
					Morphisms
				http://encyclopedia.laborlawtalk.com/Post_correspondence_problem
					"The Post correspondence problem is an undecidable
					decision problem that was introduced by Emil Post. Because
					it is simpler than the Halting problem and the
					Entscheidungsproblem it is often used in proofs of
					undecidability."
				http://www.nist.gov/dads/HTML/postsCorrespondProb.html
				http://www.comp.nus.edu.sg/~gem1501/assignment12.html
			* Rice's Theorem
				
					
	Complexity Theory
		Questions regarding time or space requirements
		P vs NP

----------------------------------------------------------------------------
# $Id$
# ex: set tabstop=4 noet textwidth=78:
----------------------------------------------------------------------------