Computability in Europe 2006
Logical Approaches to Computational Barriers

Print current page  Print this page

Special Session Talk:
Gödel's Conflicting Approaches to Effective Calculability

Speaker: Wilfried Sieg


Identifying the informal concept of effective calculability with a
rigorous mathematical notion like general recursiveness or Turing
computability is still viewed as problematic, and rightly
so.  In a 1934 conversation with Church, Gödel suggested
finding axioms for the notion of effective calculability and “doing
something on that basis.“  He introduced in his
contemporaneous Princeton lectures the class of general recursive
functions through the equational calculus, but was not convinced at the
time that this mathematical notion encompassed all effectively
calculable functions.  

Gödel articulated different
and conflicting approaches to the underlying methodological issues
during the subsequent three decades. In 1964, Gödel viewed
work as providing a correct analysis of mechanical procedures (and
thus  of effective calculability) and a proof of the fact
that the analyzed notion is equivalent to that of a Turing machine.
Gödel gave, however, no indication of the character of Turing's
analysis nor of that of the equivalence proof.  Turing
reduced mechanical procedures, carried out by a human computer, to
machine computations.  A deepened examination of Turing’s
reduction can serve as a springboard for the methodological approach
Gödel had recommended in 1934, but never followed up, namely an
axiomatic characterization of computability. 

websites: Arnold Beckmann 2006-04-20 Valid HTML 4.01! Valid CSS! eXTReMe Tracker hit counters by