On Non-Computable Functions

DOI10.1002/j.1538-7305.1962.tb00480.xzbMath1497.68176OpenAlexW2044633287WikidataQ56095831 ScholiaQ56095831MaRDI QIDQ5046182

No author found.

Publication date: 28 October 2022

Published in: Bell System Technical Journal (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/j.1538-7305.1962.tb00480.x

Mathematics Subject Classification ID

Turing machines and related notions (03D10) Classical models of computation (Turing machines, etc.) (68Q04)

Related Items (35)

Busy beaver machines and the observant otter heuristic (or how to tame dreadful dragons) ⋮ Autopoietic and \((\boldsymbol{M,R})\) systems ⋮ On the rate of decrease in logical depth ⋮ Generating candidate busy beaver machines (or how to build the zany zoo) ⋮ Machines that perform measurements ⋮ Expository notes on computability and complexity in (arithmetical) games ⋮ Weight-reducing Turing machines ⋮ On Completeness of Cost Metrics and Meta-Search Algorithms in $-Calculus ⋮ On measuring the complexity of networks: Kolmogorov complexity versus entropy ⋮ Non-recursive trade-offs between two-dimensional automata and grammars ⋮ A computable measure of algorithmic probability by finite approximations with an application to integer sequences ⋮ Some undecidability results for asynchronous transducers and the Brin-Thompson group $2V$ ⋮ Some rapidly growing functions ⋮ A Study on Complexity Measure of Diamond Tile Self-assembly System ⋮ Several results in program size complexity ⋮ Unnamed Item ⋮ Superintelligence Cannot be Contained: Lessons from Computability Theory ⋮ Fractal dimension versus process complexity ⋮ Finding the Hardest Formulas for Resolution ⋮ Numerical evaluation of algorithmic complexity for short strings: a glance into the innermost structure of randomness ⋮ Effective Computability of Solutions of Ordinary Differential Equations The Thousand Monkeys Approach ⋮ Computational universes ⋮ Dynamical systems approach to the busy beaver problem ⋮ Small Turing machines and generalized busy beaver competition ⋮ An automated approach to the Collatz conjecture ⋮ Pushdown automata and constant height: decidability and bounds ⋮ On a problem in the collective behavior of automata ⋮ A new Gödelian argument for hypercomputing minds based on the busy beaver problem ⋮ The many forms of hypercomputation ⋮ Correlation of automorphism group size and topological properties with program-size complexity evaluations of graphs and complex networks ⋮ Rosen's \((M,R)\) system as an X-machine ⋮ Model discovery and discrete inverse problems with cellular automata and Boolean networks ⋮ Finite degree clones are undecidable ⋮ Introduction to the Zambelli Festschrift ⋮ Observations on Computability, Uncertainty, and Technology

This page was built for publication: On Non-Computable Functions