Paradoxes and the Limits of Knowledge

CORE CURRICULUM 30.10

Class meets: . Tuesdays, 6:30 to 9:15 pm. Room 3424 N.

Office: 1432N; Telephone: 718 – 951 – 5000 x 2055

Office hours : Mondays 5 :00 – 7:00 pm Thursdays 6 :00 – 7 :00 pm

Paradoxes and limitations arising in the computer science, the physical sciences, and mathematics. Paradoxes created by using reason alone. Linguistic and philosophical paradoxes like “This sentence is a lie.” Limitations of reason, logic and computers. Reasoning about infinity. The inability to prove everything that is true. Problems that can not be solved by computers in a reasonable amount of time. Unsolvable problems. The boundary between what can and cannot be known

Prerequisite: Junior standing and completion of all lower-tier requirements in Scientific Inquiry.

Required Text:

William Poundstone, Labyrinths of Reason, Anchor Books, 1988, New York.

ISBN: 0 – 385 – 242 71 – 9 ppbk. (we will cover selected Chapters)

There will be a course-pack available in the book store. The following Materials will be in the course pack.

Davis, Martin and Hersh, Reuben, "Hilbert's 10th Problem," Scientific American, November, 1971.
Dawson, John W., “Gödel and the limits of logic”, Scientific American, June 1999.
Kopec, D. Chapter 6: “Knowledge Representation”. From an AI Text (in preparation).

Ross, Kenneth A., Wright, Charles R.B.,Section 13.3 “Infinite Sets” of Discrete Mathematics, Fifth Edition. Prentice Hall, 2003.

Sainsbury, R.M., Paradoxes 2^nd ed., Cambridge University Press, 1995. (Parts of Chapters 1,2 and 5).

Yanofsky, Noson S., “Hard Computer Problems.”
Yanofsky, Noson S., “Impossible Computer Problems.”

Tentative Schedule:

Week / Date		Title	Reading(s)
1	9/1	Introduction	Some Problems for You
2	9/8	Paradoxes: Linguistic, etc.	Poundstone - Ch 1: Paradox Sainsbury 5:1 – 5:3
3	9/15	Paradoxes:Philosophical and Beyond	Poundstone – Ch 2: Induction Sainsbury 1.1-1.4 and 2.1-2.3
4	9/22	Knowledge Representation	Kopec: Ch 6: Sections 1-6
5	10/6	Knowledge Represenation	Kopec : Ch 6: Sections 7-12
6	10/13	INDIVIDUAL CASE STUDY	Paradoxes and People / Knowledge
7	10/20	Midterm	ALL CLASS and READING MATERIAL TO DATE: 25%
8	10/27	Infinities	Ross and Wright; Poundstone: Ch 8
9	11/3	Complexity	“Hard Computer Problems” Yanofsky: Sections 1-4
10-11	11/10, 11/17	Computability	Poundstone: Ch 7 Yanofsky: “Impossible Computer Problems” Sections 1-3,5
12	11/24	Mathematical Limits	Dawson, Davis and Hersh
13	12/1	Scientific Limits
14	12/8	GROUP PROJECTS	HARD AND IMPOSSIBLE PROBLEMS

Grading: Case Studies: 10%

Midterm: 25%

Group Projects: 20%

Final: 35%

Homework: 10%

There will be homework most weeks. You must hand in the H.W. at the beginning of the next class or when due. Exams will be based on in class material, homework, and readings. Attendance is essential; Participation is expected; both will affect course grade.

CASE STUDIES: There will be individual Case Studies to be presented to the class in the 6^th week of the course. The topics for the case studies are usually wide open but should be related to “knowledge representation”, “paradoxes”, and “limits” to computation”. Problems, methods, and people not covered in the course (or course readings) may be used as topics for the case studies. Students are required to propose a topic for Case Study by September 20^th, which includes a Your Name, a Title, the Course Title / Number, a date, and a paragraph with references describing what you propose to cover. A double-spaced 5 page paper is required at the time of presentations which will begin on October 13^th.

GROUP PROJECTS: Ideally group projects will be extensions of projects done individually and will involve 2-4 people. A presentation and a 20-page paper representing the work of group members is expected, with references and a Project Proposal due by November 1, 2009. Proposals should be a few paragraphs long, including a title, group members and responsibilities, along with references.

In this course group projects can cover a class of problems, books, scientists (including engineers, computer scientists, and mathematicians) as well as inventors, who have addressed the kinds of problems that have been presented in the course.
Goals Addressed by Core Course:

Be able to think critically and creatively, to reason logically, to reason quantitatively, and to express their thoughts orally and in writing with clarity and precision.

Acquire the tools that are required to understand and respect the natural universe.

Understand what knowledge is and how it is acquired by the use of differing methods in different disciplines.

Objectives of this Core Course:

1. Students will be able to recognize and create self-referential paradoxes.

2. Students will be able to understand the difficulties of certain famous philosophical problems.

3. Students will be able to determine whether a set is finite, countably infinite or uncountably infinite.

4. Students will be able to tell if certain computer problems are solvable or unsolvable.

5. Students will be able to tell if a solvable problem is effectively solvable or not.

6. Students will be able to describe Gödel’s incompleteness theorem.

Outcomes:

1. Students will understand many self-referential paradoxes.

2. Students will know the power and the limitations of many parts of modern science.

3. Students will learn the effective and absolute limits of computers.

4. Students will be able to describe their work both orally and in writing.