Introduction to the Baire space
Wadge, William W. (1982) Introduction to the Baire space. University of Warwick. Department of Computer Science. (Department of Computer Science Research Report). (Unpublished)
WRAP_cs-rr-045.pdf - Other - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader
Download (2252Kb) | Preview
This report reproduces the chapter 0 of my PhD dissertation, "Reducibility and determinateness on the Baire Space" . I have produced it as a Warwick Theory of Computation report because infinite games and the computational approach to topology presented here is, I feel, very relevant to computer science. The basic connection between topology and computability, explained in section E, is as follows: a function from the Baire space to itself is continuous if it can be computed by a continuously operating numeric 'filter' which has access to a countably infinite database.
It used to be thought that infinite computations (not to mention infinite games) were of little relevance to practical computing, which (it was thought) was inherently finitary. The emergence of the dataflow model of computation (among other factors) has changed all this; computer scientists are now keenly interested in the behaviour and properties of continuously operating (nonterminatinq) devices. The entire history of the input to, or output from, such a device will normally be an infinite sequence of finite objects. Such a history can be 'coded up' as an infinite sequence of natural numbers; i.e., as an element of the Baire Space. The study of this space could therefore prove to be as important in computer science as it has already proved to be in (say) statistics.
Of course I make no claims to have discovered the material presented here. It has been known for many years now that "computability" and "continuity" are closely related. However, I hope that this report will in a small way help to popularise the 'topological' approach to computation. I would like to thank John Addison for Introducing me to the 'operational' approach to topology.
Readers interested in the dissertation itself are referred to Theory of Computation report no 44, which ls a collection of the more important parts.
|Subjects:||Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software|
|Divisions:||Faculty of Science > Computer Science|
|Library of Congress Subject Headings (LCSH):||Baire spaces|
|Series Name:||Department of Computer Science Research Report|
|Publisher:||University of Warwick. Department of Computer Science|
|Official Date:||October 1982|
|Number of Pages:||45|
|Institution:||University of Warwick|
|Theses Department:||Department of Computer Science|
|Status:||Not Peer Reviewed|
Actions (login required)