16
$\begingroup$

I am a mathematician interested in set theory, ordinal theory, infinite combinatorics and general topology.

Are there any applications for these subjects in computer science? I have looked a bit, and found a lot of applications (of course) for finite graph theory, finite topology, low dimensional topology, geometric topology etc.

However, I am looking for applications of the infinite objects of these subjects, i.e. infinite trees (Aronszajn trees for example), infinite topology etc.

Any ideas?

Thank you!!

Improve this question
$\endgroup$
2

3 Answers 3

Reset to default
21
$\begingroup$

One major application of topology in semantics is the topological approach to computability.

The basic idea of the topology of computability comes from the observation that termination and nontermination are not symmetric. It is possible to observe whether a black-box program terminates (simply wait long enough), but it's not possible to observe whether it doesn't terminate (since you can never be certain you have not waited long enough to see it terminate). This corresponds to equipping the two point set {HALT, LOOP} with the Sierpinski topology, where $\emptyset, \{HALT\}, and \{HALT, LOOP\}$ are the open sets. So then we can basically get pretty far equating "open set" with "computable property". One surprise of this approach to traditional topologists is the central role that non-Hausdorff spaces play. This is because you can basically make the following identifications

$$ \begin{matrix} \mathbf{Computability} & \mathbf{Topology}\\ \mbox{Type} & \mbox{Space} \\ \mbox{Computable function} & \mbox{Continuous function} \\ \mbox{Decidable set} & \mbox{Clopen set} \\ \mbox{Semi-decidable set} & \mbox{Open set} \\ \mbox{Set with semidecidable complement} & \mbox{Closed set} \\ \mbox{Set with decidable equality} & \mbox{Discrete space} \\ \mbox{Set with semidecidable equality} & \mbox{Hausdorff space} \\ \mbox{Exhaustively searchable set} & \mbox{Compact space} \\ \end{matrix} $$

Two good surveys of these ideas are MB Smyth's Topology in the Handbook of Logic in Computer Science and Martin Escardo's Synthetic topology of data types and classical spaces.

Topological methods also play an important role in the semantics of concurrency, but I know much less about that.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Thank you for your enlightening answer! I will have a look. $\endgroup$
    – user135172
    Commented May 1, 2015 at 21:35
  • $\begingroup$ Is it possible to seek a finer topology for polynomial hierarchy alone? $\endgroup$
    – Turbo
    Commented May 24, 2015 at 3:03
  • 1
    $\begingroup$ A fascinating application of these ideas can be found in the series of posts "Seemingly impossible functional programs" - math.andrej.com/2007/09/28/… , math.andrej.com/2014/05/08/seemingly-impossible-proofs $\endgroup$
    – jkff
    Commented May 25, 2015 at 3:54
  • 1
    $\begingroup$ Can you give us a little more here? I find this answer very difficult to comprehend. For example, assume for a contradiction that the semi-decidable subsets of $\mathbb{N}$ form a topology, as you appear to be claiming. Then it follows that since for every natural number $k \in \mathbb{N}$, the singleton set $\{k\} \subseteq \mathbb{N}$ is semi-decidable, hence arbitrary unions of singleton subsets of $\mathbb{N}$ are semi-decidable. Ergo every subset of $\mathbb{N}$ is semi-decidable, a contradiction. $\endgroup$
    – goblin GONE
    Commented Jun 1, 2015 at 6:12
4
$\begingroup$

The 2004 Gödel Prize was shared between the papers:

  • The Topological Structure of Asynchronous Computation.
    By Maurice Herlihy and Nir Shavit, Journal of the ACM, Vol. 46 (1999), 858-923
  • Wait-Free k-Set Agreement Is Impossible: The Topology of Public Knowledge.
    By Michael Saks and Fotios Zaharoglou, SIAM J. on Computing, Vol. 29 (2000), 1449-1483.

Quotes from the 2004 Gödel Prize:

The two papers offer one of the most important breakthroughs in the theory of distributed computing.

The discovery of the topological nature of distributed computing provides a new perspective on the area and represents one of the most striking examples, possibly in all of applied mathematics, of the use of topological structures to quantify natural computational phenomena.

Related post: Applications of topology to computer science

Improve this answer
$\endgroup$
1
  • 3
    $\begingroup$ Although these are certainly great applications of topology in TCS, they are really applications of "combinatorial/algebraic topology" rather than what I think the OP meant by "general topology" (which is more in the point-theoretic / set-theoretic / logical arena). $\endgroup$
    – Joshua Grochow
    Commented May 24, 2015 at 18:38
4
$\begingroup$

Behavior of a reactive system is often modeled using infinite structures ( infinite traced and infinite computation trees) and their Temporal properties (safety and liveness properties) have also been characterized using topology.

Defining Liveness Alpern and Schneider

Safety and Liveness in Branching time Manolios et. al.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.