4

Are there well-established applications of the Cantor space ($2^\omega$) in computer science, other than those connected with computable real arithmetic?

John Tucker's page Computation on Topological Data Types mentions applications of the general area in signal processing, 3d graphics, and semantics of process algebras: have these applications been fruitful?

Charles Stewart
  • 4,316
  • 28
  • 45

3 Answers3

5

It is used heavily in algorithmic information theory. For example, if you want to define random sequence with respect to a particular measure, you should first define this measure on Borel sets of cantor space.

Compactness of Cantor tree is used implicitly or explicitly in compactness arguments in combinatorics (in particular, it is used in the proof of compactness theorem for boolean functions).

ilyaraz
  • 1,569
  • 18
  • 33
  • The definitions of Martin-Löf randomness I've seen used recursion theory rather than topology. Do you have a reference for use of the Cantor space in AIT? – Charles Stewart Aug 23 '10 at 16:52
  • To define Martin-Löf randomness you should define some computable measure on Cantor space. Topology is not heavily used, though. – ilyaraz Aug 23 '10 at 20:00
  • The WP page lists three equivalent formulations of ML randomness, two of which don't explicitly appeal to topological concepts. Are there uses of compactness in combinatorics that get non-topological results in obviously better ways than non-topological arguments? This would count as a substantial application. (BTW, include @Charles if you reply to this, otherwise I'm not notified of your response). – Charles Stewart Aug 26 '10 at 11:33
  • @Charles, compactness in combinatorics is heavily used everywhere. Usually, to prove some infinitary result, you reduce to finite one using compacntness of infinite product of discrete spaces or so... – ilyaraz Aug 26 '10 at 16:25
4

Cantor space is used quite widely in the theory of representations of topological spaces in general, and not just the real numbers.

An important realizability model, namely Kleene's function realizability (also known as Type Two Effectivity) uses Cantor space (or equivalently the Baire space nat -> nat) as the underlying partial combinatory algebra. This realizability model, and the related computable versions of it, provide a very good environment for studying computability on topological spaces that goes much farther than computability of the real line.

In a somewhat related line of work Martin Escardó has used Cantor space to demonstrate how certain higher-order functionals can be implemented on compact spaces, see for example his Seemingly impossible functionals for a gentle introduction.

Andrej Bauer
  • 28,823
  • 1
  • 80
  • 133
  • I know the work on Type Two Effectivity and realizability, but -to be a Philistine for a moment- I'd not call these applications, not in the sense of exact reals and the Tucker applications. Escardó's work is different, but I think that doesn't count as well-established. – Charles Stewart Aug 30 '10 at 06:06
4

Cantor spaces also come up in the theory of cellular automata: the Curtis–Hedlund–Lyndon theorem characterizes cellular automaton rules as the functions on Cantor space (viewed as the space of states of a CA grid) that are both continuous and equivariant with respect to translations of the space.

David Eppstein
  • 50,990
  • 3
  • 170
  • 278
  • There seems to be a mismatch between your characterisation of the CHL theorem and WP's: where you talk of CA rules, WP talks of global mappings. Is this right? I don't count this as an application - see my comment on Andrej's answer. – Charles Stewart Aug 30 '10 at 06:07