A Formal Axiomatization of Computation

2019/07/04 by Ramezanian, Rasoul
#Computation and Language (cs.CL) #Computational Complexity (cs.CC) #FOS: Computer and information sciences #Logic in Computer Science (cs.LO)

paper · doi:10.48550/arxiv.1907.03533

Abstract

We introduce an axiomatization for the notion of computation. Based on the idea of Brouwer choice sequences, we construct a model, denoted by E, which satisfies our axioms and E \models P ≠ NP. In other words, regarding "effective computability" in Brouwer intuitionism viewpoint, we show P ≠ NP.

Related

• Axiomatic Theory of Algorithms: Computability and Decidability in Algorithmic Classes
• Between Turing and Kleene
• Sets, the Axiom of Choice, And All That: A Tutorial
• Three computational models and its equivalence
• Computation Environments, An Interactive Semantics for Turing Machines (which P is not equal to NP considering it)