Turing or Cantor: That is the Question

A mathematical concept is identified and analyzed that is implicit in the 2012 paper Turing Incomputable Computation, presented at the Alan Turing Centenary Conference (Turing-100, Manchester). The concept, called dynamic level sets, is distinct from mathematical concepts in the standard literature on dynamical systems, topology, and computability theory. A new mathematical object is explained and why it may have escaped prior characterizations, including the classical result of de Leeuw, Moore, Shannon, and Shapiro that probabilistic Turing machines (with bias $p$ where $p$ is Turing computable) compute no more than deterministic ones. A key mechanism underlying the concept is the Principle of Self-Modifiability, whereby the physical realization of an invariant logical level set is reconfigured at each computational step by an incomputable physical process.

The theory of computation was built to answer Turing's question: what is effectively calculable by an unbounded, immortal, disembodied agent following rules? Intelligence answers a different question (nature's): what can a finite, mortal, energy-limited agent do quickly enough to survive in a non-stationary world? We argue that a complete answer requires two operators: computation and memorizaion. Computation, $\dpar$, transforms structure toward closure; memorization, $\kap$, condenses a validated closed cycle into a reusable token. Turing formalized $\dpar$ and abstracted $\kap$ away, because his agent had infinite time and never needed to amortize. The new insight of our position paper is that the coupling of the two is not optional but forced, and forced by a precise mathematical fact: neither operator alone can be complete. We prove that symbolic computation confined to a discrete sector suffers Gödel's diagonalization incompleteness, that geometric descent confined to a continuous sector suffers a Morse forced-saddle incompleteness, and that these two are not analogies but the parity-conjugate faces of a single obstruction on a coherent complex with $\dpar^2=0$ - the even face realized by diagonalization, the odd by the topologically forced saddle, and no resolution confined to one parity able to come full circle. Intelligence must therefore couple both modes. We then locate the price of the coupling: its hinge operation, context-identification (the recognize-versus-discover decision), is exactly where the two incompletenesses coincide, hence undecidable and carrying an irreducible error floor. Finally we argue that the coupling is a universal law, realized, in the emergent sense of Anderson's ``more is different,'' at every scale from genes to thoughts to cultures, and give its falsifiable core and honest scope.

This chapter discusses the Solomonoff approach to universal prediction. The crucial ingredient in the approach is the notion of computability, and I present the main idea as an attempt to meet two plausible computability desiderata for a universal predictor. This attempt is unsuccessful, which is shown by a generalization of a diagonalization argument due to Putnam. I then critically discuss purported gains of the approach, in particular it providing a foundation for the methodological principle of Occam's razor, and it serving as a theoretical ideal for the development of machine learning methods.