2017/08/18 by Mark Inman, Inman, Mark · 2 voices
Computer Science · #Algorithms and Data Compression #Artificial Intelligence (cs.AI) #Computability, Logic, AI Algorithms #Computational Complexity (cs.CC) #F.1.1 #F.1.3 #F.4.0 #FOS: Computer and information sciences #I.2.0 #I.2.4 #Logic in Computer Science (cs.LO) #cs.AI #cs.CC #cs.LO #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1708.05714
13 pages, 1 figure
openalex publication_date 2017/08/18 · arxiv published 2017/08/18 · arxiv created 2018/04/23 · arxiv updated 2018/04/24 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
This article describes a Turing machine which can solve for β' which is RE-complete. RE-complete problems are proven to be undecidable by Turing's accepted proof on the Entscheidungsproblem. Thus, constructing a machine which decides over β' implies inconsistency in ZFC. We then discover that unrestricted use of the axiom of substitution can lead to hidden assumptions in a certain class of proofs by contradiction. These hidden assumptions create an implied axiom of incompleteness for ZFC. Later, we offer a restriction on the axiom of substitution by introducing a new axiom which prevents impredicative tautologies from producing theorems. Our discovery in regards to these foundational arguments, disproves the SPACE hierarchy theorem which allows us to solve the P vs NP problem using a TIME-SPACE equivalence oracle.