Logical Approaches to Computational Barriers

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 Turing's 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 |