«La» catégorie des machines de Turing?

Avertissement: je connais très peu la théorie de la complexité.

Je suis désolé mais il n'y a vraiment aucun moyen de poser cette question sans être (terriblement) concis:

Quels devraient être les morphismes dans "la" catégorie des machines de Turing?

Ceci est évidemment subjectif et dépend de l'interprétation que l'on a de la théorie, donc une réponse à cette question devrait idéalement fournir des preuves et un raisonnement à l'appui de la réponse.

Je voudrais souligner le fait que je recherche une catégorie de machines de Turing et non de langages formels par exemple. En particulier, je pense que mes morphismes devraient contenir des informations plus fines, puis des réductions ou quelque chose comme ça (je ne suis pas sûr cependant).

Bien sûr, s'il existe déjà une catégorie bien connue et utilisée dans la littérature, j'aimerais savoir de quoi il s'agit.

cc.complexity-theory turing-machines ct.category-theory Saal Hardali
la source

Vous l'avez dit vous-même - fonctions calculables.

Yuval Filmus

@Raphael, le fait est que vous ne définissez jamais vraiment une structure avant de la mettre dans une catégorie. C'est alors que les caractéristiques essentielles de la définition spécifique sont supprimées.

Saal Hardali

@SaalHardali Gardez à l'esprit que tout le monde ne souscrit pas à la promesse de salut faite par les théoriciens des catégories. En fait, beaucoup roulent des yeux.

Raphael

@JoshuaGrochow Il y a un morphisme étiqueté

réduit

f

$f$

T_{1}

$T_1$

T_{2}

$T_2$

f

$f$

T_{2}

$T_2$

T_{1}

$T_1$ (ou peut-être l'inverse), c'est-à-dire

. C'est, par exemple, pour les machines qui, à chaque entrée, s'arrêtent ou non, mais n'ont pas d'autre sortie.

T_{1} (x) = T_{2} (f (x))

$T_1(x) = T_2(f(x))$

Yuval Filmus

À part: pourquoi les MT devraient-elles être des objets? Il pourrait également s'agir de morphismes.

Martin Berger

Réponses:

Saal Hardali a mentionné qu'il voulait une catégorie de machines de Turing pour faire de la géométrie (ou du moins de la théorie de l'homotopie). Cependant, il existe de nombreuses façons différentes d'atteindre des objectifs similaires.

Il existe une très forte analogie entre la calculabilité et la topologie. L'intuition est que la terminaison / non-terminaison est comme l'espace Sierpinski, puisque la terminaison est finement observable (c'est-à-dire ouverte) et la non-terminaison ne l'est pas (pas ouverte). Voir les notes de cours de Martin Escardo Topologie synthétique des types de données et des espaces classiques pour une introduction modérée mais complète à ces idées.
Dans le calcul simultané et distribué, il est souvent utile de considérer les exécutions possibles d'un programme comme un espace, puis diverses contraintes de synchronisation peuvent être exprimées comme des propriétés homotopiques de l'espace. (Le fait que l'exécution ait un ordre temporel semble appeler une théorie de l'homotopie dirigée, plutôt qu'une théorie de l'homotopie ordinaire.)

Voir l'article d'Eric Goubault Quelques perspectives géométriques sur la théorie de la concurrence pour plus de détails. Voir également l'article de lauréat du prix Goedel de Maurice Herlihy et Nir Shavit, La structure topologique de la calculabilité asynchrone , qui a résolu certains problèmes ouverts de longue date dans la théorie de la programmation distribuée.
Une troisième idée vient de la théorie du type homotopique, via la découverte que la théorie du type Martin-Löf est (probablement?) Une présentation syntaxique (au sens de générateurs et de relations) de la théorie des oméga-groupoïdes - c'est-à-dire les modèles d'abstrait théorie de l'homotopie. La meilleure introduction à ces idées est le livre de théorie du type homotopie .

Notez que toutes ces idées sont très différentes les unes des autres, mais toutes utilisent toujours des intuitions géométriques! Et il y en a d'autres, que je ne connais pas, comme les utilisations qui se posent dans la théorie de la complexité géométrique, et la façon dont les théories des circuits peuvent être décrites en termes de théorie (co) homologique des graphes .

Fondamentalement, lorsque vous faites du CS, la géométrie est un outil - vous l'utilisez pour formaliser vos intuitions, de sorte que vous pouvez tirer parti de l'énorme corpus de travail qui a été fait dessus. Mais c'est un amplificateur d'idées, pas un substitut pour avoir des idées!

Neel Krishnaswami
la source

Si vos objets sont des machines de Turing, il existe plusieurs possibilités raisonnables de morphismes. Par exemple:

1) Considérez les machines de Turing comme les automates qu'elles sont et considérez les morphismes habituels des automates (cartes entre les alphabets et les états qui sont cohérents les uns avec les autres) qui préservent également les mouvements des têtes de bande, ou inversent exactement (par exemple chaque fois que la MT source va à gauche, la TM cible va à droite et vice versa).

2a) Envisagez des simulations ou des bisimulations .

2b) Dans le même ordre d'idées, vous pouvez déterminer quand une MT peut être transformée (par une fonction calculable) pour simuler l'autre. Cela peut être fait au niveau du comportement par étapes, ou comme Yuval l'a suggéré dans les commentaires, au niveau de l'entrée-sortie, c'est-à-dire qu'un morphisme de à (ou peut-être l'inverse) est un calculable tel que $T_1$ $T_2$ $f$ $T_1(x) = T_2(f(x))$ $x$ .

3) Considérons le graphe de transition de la machine de Turing (chaque sommet est une description complète de l'état de la machine et des bandes, avec des bords dirigés correspondant aux transitions que la MT effectuerait) et considérons les morphismes des graphiques. Pour les MT, c'est une relation très grossière, car elle ignore essentiellement la nature locale du calcul (elle ignore, par exemple, le contenu des bandes).

Je pense que la vraie question est: que voulez-vous savoir sur les MT ou en faire ? En l'absence de cela, il est difficile de donner des arguments pour une définition par rapport à une autre, au-delà de la naturalité (au sens habituel du mot, pas au sens catégorique).

Joshua Grochow
la source

Je suis très nouveau dans ce genre de mathématiques. J'ai lu dans le passé sur la théorie de la complexité, mais ce n'est que récemment que je l'ai repris après avoir vu quelqu'un sur Internet affirmer que les techniques cohomologiques entreraient en quelque sorte dans la théorie de la complexité au siècle prochain et cela m'a intéressé. Après quelques lectures, j'ai réalisé qu'au-delà d'une compréhension superficielle de la définition d'une machine de turing, je n'ai pratiquement aucune idée de ce qu'elle code exactement. Voilà comment je suis arrivé à la question. On pourrait donc dire qu'à un niveau très rudimentaire, j'essaie d'imaginer comment la cohomologie peut entrer dans la théorie de la complexité.

Saal Hardali

Je me rends compte que c'est extrêmement prématuré pour quelqu'un comme moi qui comprend très peu de choses sur ce sujet, mais je voulais jouer un peu avec cette idée dans ma tête de "faire la théorie de l'homotopie sur la catégorie des machines de Turing". Votre réponse est agréable et je vise certainement à en lire plus sur certains aspects. Je vous remercie.

Saal Hardali

@SaalHardali: Je suis curieux de savoir où vous lisez que la cohomologie entrera dans la théorie de la complexité? Je peux penser à deux façons, mais je ne vois pas encore de route via la théorie des types d'homotopie (peut-être parce que je ne comprends pas encore assez bien HoTT). Les deux façons dont je peux voir: (1) dans l'informatique distribuée, cela s'est déjà produit, à savoir. Herlihy et Rajsbaum, et (2) via la théorie de la complexité géométrique.

Joshua Grochow

Par la théorie de l'homotopie, je me référais à l'idée générale d'étudier des catégories avec de faibles équivalences et pas tellement HoTT. Je l'ai lu dans un sondage sur P =? NP, il n'est pas difficile à trouver, je pense qu'il était lié à l'une des questions sur ce site. Je suppose que ma première supposition (en tant qu'étranger) était qu'il y avait peut-être une sorte d'équivalence faible intéressante sur une catégorie d'un modèle de calcul qui correspond d'une manière ou d'une autre à des classes de complexité, puis étudier les foncteurs invariants sous ces équivalences faibles constituerait ce que j'appelle un " la théorie de l'homotopie "c'est probablement très naïf et totalement raté.

Saal Hardali

Dans le cas où votre intérêt est la théorie de la complexité plutôt que la théorie de la calculabilité, peut-être que cette réponse vous sera utile: cstheory.stackexchange.com/a/3422/4896

Sasho Nikolov

Vous pourriez être intéressé par les catégories Turing de Robin Cockett et Pieter Hofstra. Du point de vue de la théorie des catégories, la question "quelle est la catégorie des machines de Turing" est moins intéressante que "quelle est la structure catégorielle qui sous-tend le calcul". Ainsi, Robin et Pieter identifient un type général de catégorie qui convient pour développer la théorie de la calculabilité. Ensuite, il existe plusieurs possibilités pour définir une telle catégorie à partir des machines de Turing. Pourquoi avoir une catégorie alors que vous pouvez en avoir une catégorie entière?

Andrej Bauer
la source