Local computability and uncountable structures
Russell Miller · Cambridge University Press eBooks · 2013
§1. Introduction . Turing computability has always been restricted to maps on countable sets. This restriction is inherent in the nature of a Turing machine: a computation is performed in a finite length of time, so that even if the available input was a countable binary sequence, only a finite initial segment of that sequence was actually used in the computation. The Use Principle then says that an input of any other infinite sequence with that same initial segment will result in the same computation and the same output. Thus, while the domain might have been viewed as the (uncountable) set of infinite binary sequences, the countable domain containing all finite initial segments would have sufficed. To be sure, there are approaches that have defined natural notions of computable functions on uncountable sets. The bitmap model, detailed in [3] and widely used in computable analysis, is an excellent model for computability on Cantor space 2 ω . On the real numbers ℝ, however, it fails to compute even the simplest discontinuous functions, which somewhat limits its utility. The Blum-Shub-Smale model (see [2]) expands the set of functions which we presuppose to be computable. Having done so, it gives an elegant account of computable functions on the reals, with nice analogies to computability on ω, but the initial assumption immediately distances it from Turing's original concept of computability.