Applications pour la théorie des ensembles, la théorie ordinale, la combinatoire infinie et la topologie générale en informatique?

15

Je suis un mathématicien intéressé par la théorie des ensembles, la théorie ordinale, la combinatoire infinie et la topologie générale.

Existe-t-il des applications pour ces sujets en informatique? J'ai regardé un peu et j'ai trouvé beaucoup d'applications (bien sûr) pour la théorie des graphes finis, la topologie finie, la topologie basse dimension, la topologie géométrique, etc.

Cependant, je recherche des applications des objets infinis de ces sujets, à savoir les arbres infinis ( Aronszajn par exemple), la topologie infinie etc.

Des idées?

Je vous remercie!!

set-theory topology topological-graph-theory user135172
la source

1

voir aussi Application de sujets de théorie des ensembles comme ordinaux, forçage, filtres génériques en génie logiciel cs.se

vzn

2

En plus de l'excellente réponse de Neel, vous pourriez également être intéressé par les ordinaux calculables, qui jouent un rôle intéressant dans la théorie de la calculabilité: en.wikipedia.org/wiki/Recursive_ordinal

Joshua Grochow

21

Une application majeure de la topologie en sémantique est l'approche topologique de la calculabilité.

L'idée de base de la topologie de la calculabilité vient de l'observation que la terminaison et la non-terminaison ne sont pas symétriques. Il est possible d'observer si un programme de boîte noire se termine (attendez simplement assez longtemps), mais il n'est pas possible d'observer s'il ne se termine pas (car vous ne pouvez jamais être certain que vous n'avez pas attendu assez longtemps pour le voir se terminer). Cela correspond à l'équipement de l'ensemble à deux points {HALT, LOOP} avec la topologie Sierpinski, où sont les ensembles ouverts. Ainsi, nous pouvons essentiellement obtenir l'équivalent d'un "ensemble ouvert" avec une "propriété calculable". Une surprise de cette approche des topologues traditionnels est le rôle central que jouent les espaces non-Hausdorff. En effet, vous pouvez essentiellement effectuer les identifications suivantes $\emptyset, \{HALT\}, and \{HALT, LOOP\}$

\begin{matrix} C o m p u t une b je l je t y & T o p o l o g y \\ Type & Espace \\ Fonction calculable & Fonction continue \\ Ensemble décidable & Ensemble Clopen \\ Ensemble semi-décidable & Ensemble ouvert \\ Ensemble avec complément semi-décidable & Ensemble fermé \\ Sertie d'une égalité décidable & Espace discret \\ Sertie d'une égalité semi-décidable & Espace Hausdorff \\ Ensemble consultable de manière exhaustive & Espace compact \end{matrix}

$\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}$

Deux bonnes enquêtes sur ces idées sont la topologie de MB Smyth dans le Handbook of Logic in Computer Science et la topologie synthétique de Martin Escardo sur les types de données et les espaces classiques .

Les méthodes topologiques jouent également un rôle important dans la sémantique de la concurrence, mais j'en sais beaucoup moins à ce sujet.

Neel Krishnaswami
la source

Merci pour votre réponse éclairante! J'irais regarder.

user135172

Est-il possible de rechercher une topologie plus fine pour la hiérarchie polynomiale seule?

T ....

1

Une application fascinante de ces idées peut être trouvée dans la série de messages "Programmes fonctionnels apparemment impossibles" - math.andrej.com/2007/09/28/… , math.andrej.com/2014/05/08/seemingly-impossible -proofs

jkff

1

N

$\mathbb{N}$

k \in N

$k \in \mathbb{N}$

{k} \subseteq N

$\{k\} \subseteq \mathbb{N}$

N

$\mathbb{N}$

N

$\mathbb{N}$

4

Le prix Gödel 2004 a été partagé entre les journaux:

La structure topologique du calcul asynchrone .
Par Maurice Herlihy et Nir Shavit, Journal de l'ACM, Vol. 46 (1999), 858-923
Un accord k-set sans attente est impossible: la topologie de la connaissance publique .
Par Michael Saks et Fotios Zaharoglou, SIAM J. sur Computing, Vol. 29 (2000), 1449-1483.

Citations du prix Gödel 2004:

Les deux articles offrent l'une des percées les plus importantes dans la théorie de l'informatique distribuée.

La découverte de la nature topologique de l'informatique distribuée offre une nouvelle perspective sur le domaine et représente l'un des exemples les plus frappants, peut-être dans toutes les mathématiques appliquées, de l'utilisation de structures topologiques pour quantifier les phénomènes informatiques naturels.

Article connexe: Applications de la topologie à l'informatique

hengxin
la source

3

Bien que ce soient certainement de grandes applications de la topologie dans TCS, ce sont vraiment des applications de la "topologie combinatoire / algébrique" plutôt que ce que je pense que l'OP signifiait par "topologie générale" (qui est plus dans la théorie des points / la théorie des ensembles / la logique arène).

Joshua Grochow

4

Le comportement d'un système réactif est souvent modélisé en utilisant des structures infinies (arbres de calcul infinis tracés et infinis) et leurs propriétés temporelles (propriétés de sécurité et de vivacité) ont également été caractérisées en utilisant la topologie.

Définition de Liveness Alpern et Schneider

Sécurité et vivacité dans le temps de ramification Manolios et. Al.

Mitesh J
la source

Applications pour la théorie des ensembles, la théorie ordinale, la combinatoire infinie et la topologie générale en informatique?

Réponses: