Niveau: Supérieur, Doctorat, Bac+8
Some Topologies for Computations? Giuseppe Longo CNRS and Dept. d'Informatique Ecole Normale Superieure 45, rue d'Ulm 75005 Paris, France September 18, 2003 1 Introduction 1.1 Computations The applications of topological and order structures in Theory of Computa- tion, a key aspect of Foundations of Mathematics and of Theoretical Computer Science, has various origins and it is largely due to the relevance of these struc- tures for Intuitionistic (constructive) Systems: their Logic underlies theoretical as well as applied Computability. Computability Theory was born in the '30's as a formalization of the in- formal notion of “potentially mechanizable” deduction, which was at the core of foundational analysis, since late '800, and resulted from the happy marriage of a Formalist and Intuitionistic understanding of effectiveness. For Peano, Hilbert and many others, foundation and certainty, in Mathematics, had to be found in stepwise deductions within “finitistic” system. For these leading mathematicians, the abstract and symbolic nature of Mathematics, but rigor as well, were identified and all coincided with formalism or with the “yet-to- be-specified” notion of potentially mechanizable process. At the core of it, there was the newly invented formal Theory of Numbers, Peano Arithmetic (PA), based on Peano-Dedekind formal rule for induction.
- peano-dedekind formal rule
- potentially mechanizable
- computability theory
- then
- godel
- logic since
- fully motivated
- his locus
- peano arithmetic
- formal machine