80-619 Computability and Learnibility

Units: 12.0 Department: Philosophy Cross-listed: 80-319 Related URLs: http://www.hss.cmu.edu/philosophy This course is conceived as an alternative way to fulfill the 80-311, Computability and Incompleteness requirement for students who are more interested in rationality, learning, and scientific method than in logic and the foundations of mathematics. A solid grounding in the theory of computability will be provided, but the applications will concern computational learning theory, which studies what can be learned or discovered by computational agents from empirical data rather than what can be proved in a logical system. The application is more natural than it might seem at first. The problem of induction is that a general law may be refuted by the next observation, no matter how long it has withstood test. But there is a parallel problem about algorithmic halting: no matter how long a computation fails to halt, it may halt as soon as a world-be decision procedure concludes that it never will. In both cases, the difficulty can be sidestepped by entertaining methods that converge to the right answer without announcing when they have done so. We will delve into this analogy, using the theory of computability to investigate such questions as what machines can learn, whether machines could discover uncomputable truths, why irrational machines may be smarter, and what good it would do to have an infinite regress of methods, each of which checks whether its predecessor will find the truth. All topics covered are self-contained, but students are expected to have some basic background in logic, computation, or discrete mathematics. The text will consist of handout lecture notes. The course grade will be based on exercises and two short papers that will provide vital practice in writing articles for conference proceedings.

Popularity index Rank for this semester: #1446 Rank in this department: #39

Spring 2005 times

Sec	Time	Day	Instructor	Location
A	10:30 - 11:50 am	M	Kelly	BH 150
		W	Kelly	BH 150