HEXAGONbeta

On the scope of computability and formal axiomatic systems

Primarily human-written textHuman understanding: all partscs.LO — Logic in Computer Science

Contributed by Jon Bohlin ↗

Version 1 / Oct 29, 2026 / CC BY 4.0

Abstract

This survey explores the theoretical scope of effective computation and formal axiomatic systems, emphasizing a constructive perspective based on computable trees and their associated path spaces. No new technical results are presented; rather, the aim is to synthesize established results from computability theory and mathematical logic into a unified framework that clarifies what can be computed in principle, complementing the classical emphasis on undecidability results. It is argued that standard models of computation, such as Turing machines and equivalent formalisms, are computationally saturated: any effective extension of their instruction sets does not enlarge the class of effectively computable functions and algorithms. This saturation corresponds, on the logical side, to the representational completeness of Robinson arithmetic, which is sufficient to encode all computable functions despite being finitely axiomatized. The survey proceeds by showing how standard models of computation give rise to computable trees whose infinite paths correspond to complete and consistent, but typically non-computable, extensions. This construction links effectively closed classes in Cantor space with spaces of completions of formal theories and clarifies the boundary between effective computability and logical possibility. Since Cantor space is homeomorphic to the classical Cantor set, this framework provides a natural bridge between discrete computability-theoretic and logical structures on the one hand, and continuous topology on the other.

References

  1. Cooper, S Barry. Computability theory. Chapman and Hall/CRC. 2017
  2. Cutland, Nigel. Computability: An introduction to recursive function theory. Cambridge university press. 1980
  3. Post, Emil L. Recursively enumerable sets of positive integers and their decision problems. Bull. Amer. Math. Soc., vol. 50, pp. 284–316. 1944
  4. Rautenberg, Wolfgang. A concise introduction to mathematical logic. Springer. 2006
  5. Simpson, Stephen George. Subsystems of second order arithmetic. Cambridge University Press, vol. 1. 2009
  6. Soare, Robert I. Turing computability: theory and applications. Theory Appl. Comput. 2016
  7. Stillwell, John. Reverse mathematics: Proofs from the inside out. Princeton University Press. 2018
  8. Turing, Alan Mathison; others. On computable numbers, with an application to the Entscheidungsproblem. J. of Math, vol. 58, no. 345-363, pp. 5. 1936

Version history

  1. v1Submitted by Jon BohlinInitial depositCurrentOct 27, 2026