View Related Documents

Abstract

The conventional wisdom presented in most computability books and historical papers is that there were several researchers in the early 1930’s working on various precise definitions and demonstrations of a function specified by a finite procedure and that they should all share approximately equal credit. This is incorrect. It was Turing alone who achieved the characterization, in the opinion of Gödel. We also explore Turing’s oracle machine and its analogous properties in analysis.

Keywords  Turing a-machine - computability - Church-Turing Thesis - Kurt Gödel - Alan Turing - Turing o-machine - computable approximations - effectively continuous functions on reals - computability in analysis - strong reducibilities reexamined

Fulltext Preview

Image of the first page of the fulltext document