Proving the Church-Turing Thesis
Church's Thesis asserts that the only numeric functions that can be calculated by effective means are the recursive ones, which are the same (extensionally) as the Turing-computable numeric functions.
Zusammenfassung
|
Was
|
Proving the Church-Turing Thesis
|
|
Wer
|
Nachum Dershowitz, Tel Aviv University
|
|
Wo
|
TU Wien EI3 Sahulka, Gusshausstr. 25, Altes EI, Stiege VIII, 2. Stock
|
|
Wann
|
15/10/09
12:15
|
|
Link
|
http://www.math.tau.ac.il/~nachumd/
|
Details
The Theory & Logic Group / Institute of Computer Languages and the Kurt Goedel Society (KGS) cordially invite to the talk.
Abstract
Church's Thesis asserts that the only numeric functions that can be calculated by effective means are the recursive ones, which are the same (extensionally) as the Turing-computable numeric functions. Yuri Gurevich's Abstract State Machine Theorem states that every classical algorithm is emulated (step for step) by an abstract state machine, which is a most generic model of sequential computation. That theorem presupposes three natural postulates about algorithmic computation. By augmenting those postulates with an additional requirement regarding basic operations, a natural axiomatization of computability and a proof of Church's Thesis obtain, as Goedel and others suggested may be possible. In a similar way, but with a different set of basic operations, one can prove Turing's Thesis, characterizing the effective string functions, and - in particular - the effectively- computable functions on string representations of numbers. (Joint work with Udi Boker and Yuri Gurevich.)
Biography
Nachum Dershowitz has been a professor of computer science at Tel Aviv University since 1998. Prior to that, he was on the faculty of the University of Illinois at Urbana-Champaign. His graduate degrees, in Applied Mathematics, are from the Weizmann Institute (M.Sc. 1975; Ph.D. 1979). He coauthored the book, Calendrical Calculations (Cambridge University Press, 1997), with Edward Reingold, which won Choice's Outstanding Academic Title Award (2002) and is now in its third edition (2008). He is also the author of The Evolution of Programs (Birkhäuser, 1983), coauthor of Calendrical Tabulations (Cambridge University Press, 2002), and editor of six other works. His research interests include foundations of computing, software and hardware verification, machine inference, term-rewriting systems, combinatorial enumeration, and calendar algorithms.
