LOGIC, PRIMES AND COMPUTATION: A TALE OF UNREST

Abstract

The early connections between Mathematical Logic and Computer Science date back to the thirties and to the birth itself of modern Theoretical Computer Science, and concern computability. This survey wishes to emphasize how alive and fruitful this relationship has been since then, and still is.

Keywords

• computability
• feasibility
• primality
• satisfiability