PSU Mark
Eberly College of Science Mathematics Department

Meeting Details

For more information about this meeting, contact Stephen Simpson.

Title:Translating computer programs into the predicate calculus
Seminar:Logic Seminar
Speaker:Stephen G. Simpson, Pennsylvania State University
Abstract:
We briefly review the register machine model of computation. We show how to associate to each register machine program P a sentence A_P of the predicate calculus, such that P halts if and only if A_P is logically valid. From this we deduce Church's Theorem: the problem of logical validity for sentences of the predicate calculus is algorithmically unsolvable. If time permits, we shall also deduce Trakhtenbrot's Theorem concerning validity in finite structures.

Room Reservation Information

Room Number:309 Boucke Building
Date:09 / 09 / 2008
Time:02:30pm - 03:45pm