2011/11/29 by Kajetan Młynarski, Młynarski, Kajetan
Computer Science · #Computability, Logic, AI Algorithms #Computational Complexity (cs.CC) #FOS: Computer and information sciences #Logic in Computer Science (cs.LO) #Logic, Reasoning, and Knowledge #Logic, programming, and type systems #cs.CC #cs.LO
paper · pdf · doi:10.48550/arxiv.1111.6954
10 pages, 2 figures
arxiv created 2011/11/29 · openalex publication_date 2011/11/29 · arxiv updated 2015/03/19 · openalex created_date 2024/04/11 · openalex updated_date 2026/07/28
This paper discusses limitations of reflexive and diagonal arguments as methods of proof of limitative theorems (e.g. Gödel's theorem on Entscheidungsproblem, Turing's halting problem or Chaitin-Gödel's theorem). The fact, that a formal system contains a sentence, which introduces reflexitivity, does not imply, that the same system does not contain a sentence or a proof procedure which solves this problem. Second basic method of proof - diagonal argument (i.e. showing non-eqiunumerosity of a program set with the set of real numbers) does not exclude existance of a single program, capable of computing all real numbers. In this work, we suggest an algorithm generating real numbers (arbitrary, infinite in the limit, binary strings), and we speculate it's meaning for theoretical computer science.