On Non-Computable Functions

N/A

On Non-Computable Functions ByT. RADO (Manuscript received November 12, 1961) The construction of non-computable functions used in this paper is based on the principle that a finite, non-empty set of non-negative integers has a largest element. Also, this principle is used only for sets which are excep- tionally well-defined by current standards. No enumeration of computable functions is used, and in this sense the diagonal process is not employed. Thus, it appears that an apparently self-evident principle, of constant use in every area of…

related reading

• Computable function - Wikipediaen.wikipedia.org
• Computational Complexity Theory (Stanford Encyclopedia of Philosophy)plato.stanford.edu
• Shtetl-Optimized >> Blog Archive >> BusyBeaver(6) is really quite largescottaaronson.blog
• Shtetl-Optimized >> Blog Archive >> BusyBeaver(5) is now known to be 47,176,870scottaaronson.blog
• Computably enumerable set - Wikipediaen.wikipedia.org
• Chaitin's constant - Wikipediaen.wikipedia.org
• Computable number - Wikipediaen.wikipedia.org
• alan turing - computing machinery and intelligencecourses.cs.umbc.edu
• Church–Turing thesis - Wikipediaen.wikipedia.org
• [2501.02693] Any function I can actually write down is measurable, right?arxiv.org
• Primitive recursive function - Wikipediaen.wikipedia.org
• The Church-Turing Thesis (Stanford Encyclopedia of Philosophy)plato.stanford.edu