Theory of computation and philosophy

Kant's denial of the legitimacy of noesis and abstract objects which can be known through it started another debate about mathematical objects and nature of mathematics. His own account of mathematics as synthetic a priori knowledge has been criticized as well which simultaneously brought about discussions concerning the foundations of mathematics. On the one hand Frege tried to reduce mathematics to logic, on the other hand formalist project which was led by Hilbert tried to establish mathematics as a syntactic manipulation of concrete objects given in intuition and tried to cover all mathematics as a formal system. While Gödel's incompleteness theorems pointed out the boundaries of formalist project, a complete representation of a formal system could only be given with Turing machine conceptualization. Therefore, it can be said that theory of computation and Turing machine, which is the theoretical foundations of modern computers, are products of a philosophical debate. Theory of computation, complexity theory and modern cryptography -which are continuations of theory of computation- are regarded as mostly technical fields, however they are actually related to philosophical issues in more than one way. Therefore, it is necessary to take into consideration the contributions these fields and philosophy can make to one another. Keywords: Mathematical objects, formalism, Hilbert, Turing machine, theory of computation, pure intuition, complexity theory, P vs. NP problem, cryptography, zero-knowledge proofs