Doctoral Program in Computer Science
365 5th Avenue
New York City 10016
Room 4319
Phone: 212.817.8190
Fax: 212.817.1510
compsci@gc.cuny.edu
  Click here to go to the Graduate Center main page.

Computer Science Colloquium
 


Thursday, October 9, 4:15pm, 9206
 
Dan E. Willard  
(SUNY, Albany)
 
"Generalizations and Boundary Case Exceptions for the
Second Incompleteness Theorem — Viewed from a Computer Science Perspective"

 

Gödel's 1931 paper about Incompleteness contained two results. Its Second Incompleteness Theorem stated that sufficiently strong axiom systems are unable to internally verify their own consistency. During the last 10 years, we have published several papers about this topic. They have identified Boundary Cases where adequately weak axiom systems can recognize their own internal consistency, and we have also developed new generalizations of the Second Incompleteness Theorem that more precisely identify the exact threshold where the Second Incompleteness Effect takes place. This talk will summarize the contents of our four papers [1,2,3,4] plus discuss further results that are scheduled to be published in the near future.

Our talk will include an explanation about why we believe the study of the Second Incompleteness Theorem and its Boundary-Case Exceptions will become increasingly relevant to Computer Science as the 21-st Century progresses. We will also examine this topic from Epistemological perspectives of Mathematics and Philosophy. The initial part of our talk will have a sufficiently simple and introductory nature so that the thrust of this talk should be comprehensible to an audience that is not fully familiar with Gödel's Second Incompleteness Theorem.

 

References

  1. D. Willard, "Self-Verifying Axiom Systems", Third Kurt Gödel Colloquium (1993), Springer-Verlag LNCS #713, pp. 325-336.
  2. D. E. Willard, "Self-Verifying Systems, the Incompleteness Theorem and the Tangibility Reflection Principle", in Journal of Symbolic Logic 66 (2001) pp. 536-596.
  3. D. E. Willard, "How to Extend The Semantic Tableaux And Cut-Free Versions of the Second Incompleteness Theorem Almost to Robinson's Arithmetic Q", Journal of Symbolic Logic 67 (2002) pp. 465-496.
  4. D. E. Willard, "Some New Exceptions for the Semantic Tableaux Version of the Second Incompleteness Theorem", in Proceedings of Automated Reasoning with Analytic Tableaux Conference (July 2002 in Copenhagen), Springer Verlag Lecture Notes in Computer Science} Vol # 2381, pp. 281-297.

 
The Colloquium is supported by generous contributions from the CUNY Faculty Development Program, Bloomberg, Information Builders, Inc. and qbt Systems, Inc.
 

 

Computer Science Colloquium Start page

Next Talk

Schedule

Past events

Pictures