LOCAL COMPUTABILITY AND UNCOUNTABLE STRUCTURES

RUSSELL MILLER

**§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 ...

Start Free Trial

No credit card required