O'Reilly logo

Effective Mathematics of the Uncountable by Joel David Hamkins, Denis Hirschfeldt, Noam Greenberg

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

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

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required