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

<p>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).</p>

CC BY-SA 2.5
2010-08-23T16:52:28.847Z
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
CC BY-SA 2.5
2010-08-23T20:00:46.317Z
To define Martin-Löf randomness you should define some computable measure on Cantor space. Topology is not heavily used, though.
ilyaraz
CC BY-SA 2.5
2010-08-26T11:33:25.463Z
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
CC BY-SA 2.5
2010-08-26T16:25:42.363Z
@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
CC BY-SA 2.5
2010-08-23T16:41:47.070Z
2010-08-24T01:36:44.643Z
2010-08-24T01:36:44.643Z
ilyaraz
<p>Cantor space is used quite widely in the theory of representations of topological spaces in general, and not just the real numbers.</p>

<p>An important realizability model, namely <a href="http://books.google.si/books?id=3AFKAAAAMAAJ&amp;dq=editions%3aUOM39015068271272&amp;hl=en" rel="nofollow">Kleene's function realizability</a> (also known as <a href="http://books.google.si/books?id=OPolVWVFDJYC&amp;lpg=PP1&amp;ots=_QnXaeZoWy&amp;dq=book%20computable%20analysis&amp;hl=en&amp;pg=PP1#v=onepage&amp;q=book%20computable%20analysis&amp;f=false" rel="nofollow">Type Two Effectivity</a>) uses Cantor space (or equivalently the Baire space <code>nat -&gt; nat</code>) 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.</p>

<p>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 <a href="http://math.andrej.com/2007/09/28/seemingly-impossible-functional-programs/" rel="nofollow">Seemingly impossible functionals</a> for a gentle introduction.</p>

CC BY-SA 2.5
2010-08-30T06:06:34.617Z
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
CC BY-SA 2.5
2010-08-28T23:23:12.690Z
2010-08-28T23:23:12.690Z
Andrej Bauer
<p>Cantor spaces also come up in the theory of cellular automata: the <a href="http://en.wikipedia.org/wiki/Curtis%E2%80%93Hedlund%E2%80%93Lyndon_theorem" rel="nofollow">Curtis–Hedlund–Lyndon theorem</a> 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.</p>

CC BY-SA 2.5
2010-08-30T06:07:48.170Z
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
CC BY-SA 2.5
2010-08-29T00:27:32.333Z
2010-08-29T00:27:32.333Z
David Eppstein
<p>Are there well-established applications of the <a href="http://en.wikipedia.org/wiki/Cantor_space" rel="nofollow">Cantor space</a> ($2^\omega$) in computer science, other than those connected with computable real arithmetic?</p>

<p>John Tucker's page <a href="http://www-compsci.swan.ac.uk/~csjvt/JVTResearch/ComputationTopologicalData.html" rel="nofollow">Computation on Topological Data Types</a> mentions applications of the general area in signal processing, 3d graphics, and semantics of process algebras: have these applications been fruitful?</p>

<reference-request><semantics><topology><computable-analysis>
What applications of Cantor space are there?
Charles Stewart
# What applications of Cantor space are there?

(Asked by: username_0 on 2010-08-23)

Are there well-established applications of the [Cantor space](http://en.wikipedia.org/wiki/Cantor_space) ($2^\omega$) in computer science, other than those connected with computable real arithmetic?

John Tucker's page [Computation on Topological Data Types](http://www-compsci.swan.ac.uk/~csjvt/JVTResearch/ComputationTopologicalData.html) mentions applications of the general area in signal processing, 3d graphics, and semantics of process algebras: have these applications been fruitful?

**Tags:** reference-request, semantics, topology, computable-analysis


---

## 3 answers

### Answer by username_1 on 2010-08-23. Score: 5 | Accepted answer

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

> **Comments:**
> **username_0**: 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?  
> **username_1**: To define Martin-Löf randomness you should define some computable measure on Cantor space. Topology is not heavily used, though.  
> **username_0**: 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).  
> **username_1**: @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...  

---

### Answer by username_2 on 2010-08-28. Score: 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](http://books.google.si/books?id=3AFKAAAAMAAJ&dq=editions%3aUOM39015068271272&hl=en) (also known as [Type Two Effectivity](http://books.google.si/books?id=OPolVWVFDJYC&lpg=PP1&ots=_QnXaeZoWy&dq=book%20computable%20analysis&hl=en&pg=PP1#v=onepage&q=book%20computable%20analysis&f=false)) 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](http://math.andrej.com/2007/09/28/seemingly-impossible-functional-programs/) for a gentle introduction.

> **Comments:**
> **username_0**: 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.  

---

### Answer by username_3 on 2010-08-29. Score: 4

Cantor spaces also come up in the theory of cellular automata: the [Curtis–Hedlund–Lyndon theorem](http://en.wikipedia.org/wiki/Curtis%E2%80%93Hedlund%E2%80%93Lyndon_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.

> **Comments:**
> **username_0**: 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.  

---

