Pourquoi le non-déterminisme est-il un concept utile?

23

Un automate est un modèle abstrait d'un ordinateur numérique. Les ordinateurs numériques sont complètement déterministes; leur état à tout moment est uniquement prévisible à partir de l'entrée et de l'état initial.

Lorsque nous essayons de modéliser des systèmes réels, pourquoi inclure le non-déterminisme dans la théorie des automates?

Tanmoy
la source
1
Il serait peut-être utile de demander qui a initialement décrit les MNT et quel était leur but / objectif à l'époque.
usul
2
Notez que le fait que la machine soit déterministe ne signifie pas toujours que notre code l'est. Quiconque a fait du multitâche / du multithreading peut attester du fait que les moments auxquels se produit le changement de tâche sont souvent imprévisibles en termes pratiques et nous devons concevoir des verrouillages explicites pour que leur comportement apparaisse déterministe. (Fondamentalement, il existe des variables cachées dans l'état.) Les communications posent le même problème. Honnêtement, je ne sais pas si les NDA aident à résoudre ces problèmes - je suis un ingénieur logiciel, pas un informaticien - mais dans le monde réel, votre prémisse est trop optimiste.
keshlam
Lorsque vous parlez de multithreading, vous avez sans doute un non-déterminisme, du moins si vous considérez le métal et le système d'exploitation pour former la machine. Ce qui est drôle, c'est que le code lui - même est déterministe.
Raphael
@ Raphael, @keshlam En d'autres termes, nous pouvons dire que "les modèles non déterministes sont également utiles pour simuler l'exécution parallèle de code"
Grijesh Chauhan
@keshlam J'ai ajouté votre point dans ma réponse, @ Tanmoy lu a mis à jour ma réponse.
Grijesh Chauhan

Réponses:

16

Oui, vous avez raison, les ordinateurs sont automatisés déterministes. Les modèles non déterministes sont plus utiles à des fins théoriques, parfois la solution déterministe n'est pas aussi évidente pour la définition (ou dire l'énoncé du problème) et si peu difficile à trouver. Ensuite, une approche consiste à concevoir d'abord un modèle non déterministe qui peut être relativement facile à concevoir, puis à essayer de le convertir en un modèle déterministe. Ci-dessous, j'ai essayé de démontrer ce que je veux dire avec un exemple. Considérez l'expression régulière:

(01)*01(0 + 1)*  

Supposons maintenant, si vous êtes invité à dessiner DFA pour la langue générée par RE ci-dessus.

Avec ma connaissance de la conception autorités fédérales, je sais que (1) lorsqu'un *présent dans l' expression régulière a indiqué que je besoin de boucle correspondante FA (2) opérations concaténer comme a.bmoyen quelque chose comme: .(q0)─a→(q1)─b→(q2)

Donc, à ma première tentative, je dessinerais un NFA comme:

figue

Pensé que ce n'est pas une solution déterministe mais semble très simple FA qui peut être facilement conçu en utilisant l'expression régulière donnée. Mon genre d'analogie pour montrer la similitude entre l'expression régulière ci-dessus et mon NFA est comme ci-dessous:

  1. La boucle à l'état q 0 doit être pour(01)*
  2. 01(après (01)*) donne(q0)─0→(q1)─1→(q2)
  3. (0 + 1)* donne une boucle automatique à l'état q 2 pour l'étiquette 0, 1

Selon mon analogie, je pense que la FA que j'ai dessinée ci-dessus est relativement simple à tirer d'une RE donnée. Et heureusement, dans la classe des automates finis, chaque modèle non déterministe peut être converti en un modèle déterministe équivalent. Nous avons une méthode algorithmique pour convertir un NFA en DFA . Je peux donc facilement convertir au-dessus de NFA en DFA:

fig-2

Une autre partie est malheureusement que ce n'est pas toujours possible de convertir un modèle non déterministe en un modèle déterministe, par exemple la classe pour l'automatisme push-down déterministe est un sous-ensemble de la classe de l'automate push-down déterministe "check venn diagram " et vous ne pouvez pas toujours convertir un NPDA dans un PDA.

Habituellement, lorsqu'il n'est pas possible de convertir une solution non déterministe en solution déterministe, à l'aide d'une solution non déterministe, nous définissons la solution déterministe dans un sous-domaine (ou, disons, un domaine partiel) au lieu d'un domaine complet. Ou nous définissons la solution d'une autre manière (par exemple une approche gourmande) qui bien sûr peut ne pas vous donner une solution optimale .

Parfois, le non-déterminisme est un mécanisme efficace pour décrire avec précision et efficacité certains problèmes / solutions complexes, par exemple, des machines non déterministes peuvent servir de modèle d'algorithme de recherche et de retour en arrière (lire: Comment le processus de chaîne dans un modèle non déterministe en utilisant le retour arrière) ). Des modèles déterministes opposés représentent mieux des solutions efficaces, minimisées et moins redondantes.

Ici, je voudrais également citer de Wikipedia Utilisation de l'algorithme non déterministe :

Dans la conception d'algorithmes, des algorithmes non déterministes sont souvent utilisés lorsque le problème résolu par l'algorithme autorise intrinsèquement plusieurs résultats (ou lorsqu'il existe un seul résultat avec plusieurs chemins par lesquels le résultat peut être découvert, chacun également préférable). Surtout, chaque résultat produit par l'algorithme non déterministe est valide, quels que soient les choix que l'algorithme fait lors de son exécution.

Un grand nombre de problèmes peuvent être conceptualisés grâce à des algorithmes non déterministes, y compris la question non résolue la plus célèbre de la théorie informatique, P vs NP.

Comme @keshlam l'a également mentionné dans son commentaire : «Le non-déterminisme» est en pratique utilisé pour désigner toute imprévisibilité dans l'issue d'un processus. Par exemple, les programmes simultanés présentent un comportement non déterministe - deux exécutions du même programme avec la même entrée peuvent produire des résultats différents (si le mécanisme de contrôle de concurrence n'est pas appliqué). En savoir plus à ce sujet dans "Utilité du non-déterminisme" .

Je vous suggère également de lire les liens suivants:
1. Quelle est la différence entre le non-déterminisme et le hasard?
2. 9.2.2 Modèles non déterministes et probabilistes: (a). Non déterministe: je n'ai aucune idée de ce que la nature fera. (b). Probabiliste: J'ai observé la nature et collecté des statistiques.
3. Programmation non déterministe

Grijesh Chauhan
la source
@Grijest: merci beaucoup pour une telle élaboration. Une seule confusion: "Les modèles déterministes opposés représentent mieux les solutions efficaces, minimisées et moins redondantes." - Mais je pense que les modèles déterministes sont moins efficaces que les modèles non déterministes. (C'est pourquoi les problèmes de NP sont plus complexes que P. n'est-ce pas?)
tanmoy
@tan En fait, utiliser le mot "efficace" est faux, et oui, vous avez raison de dire que les modèles non déterministes sont plus capables que les modèles déterministes. La classe de problèmes couverts par les modèles déterministes est un sous-ensemble du modèle non déterministe.
Grijesh Chauhan
dans quel contexte les modèles déterministes sont "efficaces" que les modèles non déterministes (comme vous l'avez mentionné)?
tanmoy
@tan Supposons que si vous souhaitez effectuer une opération supplémentaire (par exemple, vouloir convertir FA en RE, ou expliquer la preuve du pompage du lemme, ou un autre ..), le modèle déterministe vous donnera de meilleurs résultats (donc je l'ai dit efficace).
Grijesh Chauhan
@tan Comprenez-vous les grammaires ambiguës?
Grijesh Chauhan
9

C'est plutôt l'inverse: les automates sont apparus en premier, sous forme de modèles mathématiques. Et le non-déterminisme est tout à fait naturel, vous avez souvent plusieurs voies ouvertes devant vous. Au lieu d'une façon désordonnée de spécifier que tous les chemins doivent être suivis jusqu'à la fin dans un certain ordre, et peut-être s'enliser dans des branches infinies, et ... utilisez simplement le non-déterminisme.

Et bien que les langages de programmation non déterministes ne soient pas courants, ils ont une histoire illustre, commençant peut-être par le GCL de Dijkstra . Alors que les machines utilisent de plus en plus de cœurs (processeurs indépendants), une certaine forme de non-déterminisme s'infiltre dans toute la programmation.

vonbrand
la source
Je pense que la première partie de votre réponse est factuellement erronée. Pourquoi pensez-vous que les automates sont apparus en premier? Les DFA et les NFA ont été définis plus de 10 ans après les MT définies par Turing. Voir la discussion sur cstheory
Artem Kaznatcheev
@ArtemKaznatcheev, le modèle de machine de Turing est un automate, et il est certainement antérieur aux ordinateurs d'au moins une décennie.
vonbrand
oui, mais quand les gens disent automates, ils ne signifient pas TM mais ils signifient automates à états finis et leurs extensions directes (PDA, NPDA, etc.). Voir la question que j'ai liée pour une histoire là-bas et vous verrez que les MT et l'architecture de von Neumann ont été développées indépendamment de ce que nous appelons maintenant la théorie des automates.
Artem Kaznatcheev
4
@ArtemKaznatcheev, DFA / NFA, PDA, LBA, TM sont tous des automates. De même que les transducteurs (FA avec sortie, PDA avec sortie).
vonbrand
1
Le dernier paragraphe est faux. Prolog est antérieur à GCL et est même toujours présent et assez courant. Bien entendu, Prolog n'a pas été conçu dans le vide, en s'appuyant sur les langages de programmation non déterministes précédents tels que PLANNER. Le mérite revient probablement à Golomb et Baumert "Backtrack Programming" de 1965.
Pseudonyme du
7

Les NFA peuvent être utilisés dans la pratique, consultez cette réponse sur stackexchange. La raison en est que la construction du jeu de puissance peut être simulée à la volée, pour ainsi dire. Afin de simuler un NFA sur un ordinateur déterministe, nous gardons simplement une trace des états possibles dans lesquels le NFA pourrait être. Typiquement, ce nombre serait petit, et donc la simulation serait rapide. C'est beaucoup plus pratique que d'exécuter la construction réelle du jeu de puissance: l'automate résultant pourrait être très grand, même si en pratique la plupart des ensembles seraient rarement atteints.

Le non-déterminisme est également important pour la complexité du calcul, où il est utilisé pour définir la classe NP. (La classe NP a également d'autres définitions équivalentes, par exemple en utilisant des témoins.)

Yuval Filmus
la source
comprendre votre réponse mais ne pas la saisir correctement. Pourriez-vous s'il vous plaît expliquer le fait que la construction du jeu de puissance peut se faire facilement en utilisant le non-déterminisme?
tanmoy
"Le non-déterminisme est également important pour la complexité du calcul, où il est utilisé pour définir la classe NP." - cela ne soutient l'importance du non-déterminisme que si nous supposons que NP est un concept utile, ce qui n'est que si le non-déterminisme est utile.
Raphael
@Raphael NP-exhausteness est un concept important quelle que soit votre position sur le non-déterminisme.
Yuval Filmus
2
@Tanmoy Si vous avez un non-déterminisme, vous n'avez pas besoin de la construction du jeu de puissance, mais malheureusement, les vrais ordinateurs sont déterministes. Néanmoins, il pourrait être plus facile de simuler directement un NFA plutôt que de le convertir d'abord en DFA. Consultez la réponse à laquelle je renvoie pour plus de détails.
Yuval Filmus
4

Vous déclarez correctement que les automates sont des modèles, il y a donc deux parties d'utilisation que le non-déterminisme peut avoir:

  1. Utilisation dans la modélisation de problèmes réels.

    De plus, les automates non déterministes peuvent fournir des représentations plus compactes des langues. Par exemple, il est bien connu qu'il existe des NFA dont le DFA équivalent minimal est exponentiellement plus grand.

  2. Utilisation en théorie.

    L'utilisation du non-déterminisme peut simplifier les preuves, voir par exemple la conversion d'expressions régulières en automates finis.

Raphael
la source
4

(Il s'agit d'une reformulation de certaines des autres réponses, mais je les publierai quand même :)

Vous écrivez: Un automate est un modèle abstrait d'un ordinateur numérique.

Je ne suis pas d'accord! Les automates modélisent la façon dont nous, les humains, spécifions le calcul, pas seulement la façon dont les ordinateurs l'exécutent. Le non-déterminisme est exactement la différence. Nos spécifications sont souvent non déterministes.

Par exemple, prenez le tri par fusion . Le tri par fusion consiste à trier les éléments à trier en deux moitiés de taille à peu près égale, à trier chaque moitié à l'aide du tri par fusion et à fusionner les résultats triés. Cela spécifie complètement l'idée du tri par fusion, mais ce n'est pas déterministe: cela ne spécifie pas un ordre dans lequel trier les moitiés (pour tout ce qui nous intéresse, cela peut être fait simultanément), ni ne spécifie un moyen exact de déterminer la scission. Ces détails devront être remplis afin d'arriver à une version déterministe et séquentielle du tri par fusion qui peut être implémentée par un programme informatique à un seul thread, mais je dirais qu'ils font partie d'une façon particulière de faire un tri par fusion, non l'idée de fusion se trie.

La même chose est vraie pour les algorithmes en général - par exemple les recettes de livres de cuisine. Certaines personnes définissent les algorithmes comme étant déterministes, auquel cas cette notion plus générale et à mon avis plus naturelle d '«algorithme» a besoin d'un nom différent.

L'idée de travailler avec des spécifications non déterministes a été formalisée par la méthode de programmation de Dijkstra, qui commence par des spécifications qui ne donnent que des pré- et postconditions à respecter par le programme, et développe systématiquement un programme déterministe et impératif à partir de celles-ci. Dijkstra aurait probablement dit: le tri est le problème, la relation entre les pré- et post-conditions que nous essayons d'établir; tri par fusionest une approche pour le faire, quelque part à mi-chemin entre la spécification du problème et une solution déterministe; un algorithme de tri de fusion déterministe particulier est une solution déterministe concrète. Mais la même approche générale peut être utilisée pour développer des programmes simultanés, dans lesquels le programme éventuel n'est toujours pas déterministe. De tels programmes peuvent par exemple être exécutés dans des environnements informatiques distribués.

reinierpost
la source
2

Vous avez raison, nous ne pouvons PAS construire une machine non déterministe. Par conséquent, l'objectif n'est pas d'utiliser le concept pour construire de meilleures machines. Au contraire, le non-déterminisme est un concept utile lorsque l'on essaie de comprendre le calcul. Par exemple, nous savons maintenant que, du point de vue de la calculabilité, le non-déterminisme n'est pas quelque chose de plus puissant que le déterminisme, ce qui signifie que nous pouvons simuler une machine non déterministe en utilisant une machine déterministe. Cependant, du point de vue de la complexité, le non-déterminisme nous permet, par exemple, de raisonner et d'essayer de comprendre la relation entre la difficulté de trouver une solution efficace à un problème et la difficulté de vérifier une solution (qui est le fameux problème P versus NP) . Etc. Par conséquent, la principale raison d'étudier le non-déterminisme est théorique.

Massimo Cafaro
la source
Sans contexte ou sans contexte déterministe?
alto
@alto Qu'en est-il?
babou
@babou J'essayais de souligner que "le non-déterminisme n'est pas quelque chose de plus puissant que le déterminisme", est une fausse déclaration. Les NPDA sont plus puissants que les PDA.
alto
1
@alto: non, vous comprenez mal la déclaration. Du point de vue de la calculabilité, ils sont entièrement équivalents, car la classe de problèmes (ou de langues si vous préférez) que vous pouvez résoudre INDÉPENDAMMENT de la quantité de ressources de calcul requises est la même. Et en effet, vous POUVEZ simuler une machine non déterministe avec une machine déterministe. Encore une fois, le temps et l'espace requis NE SONT PAS IMPORTANTS dans le contexte de calculabilité.
Massimo Cafaro
1
@MassimoCafaro Je ne pourrais pas être plus d'accord, en théorie. En pratique, il semble que je préfère chicaner sur la sémantique.
alto
2

l'invention de la machine de Turing a été en 1936 par Turing. Des modèles de type FSM ont été introduits par McCulloch et Pitts , deux neurophysiologistes, comme modèle d'activité neurobiologique en 1943. à partir de la page d'histoire de Stanford CS :

L'histoire passionnante de la façon dont les automates finis sont devenus une branche de l'informatique illustre son large éventail d'applications. Les premières personnes à avoir envisagé le concept d'une machine à états finis étaient une équipe de biologistes, psychologues, mathématiciens, ingénieurs et certains des premiers informaticiens. Ils partageaient tous un intérêt commun: modéliser le processus de pensée humaine, que ce soit dans le cerveau ou dans un ordinateur. Warren McCulloch et Walter Pitts, deux neurophysiologistes, ont été les premiers à présenter une description des automates finis en 1943. Leur article, intitulé "A Logical Calculus Immanent in Nervous Activity", a apporté une contribution importante à l'étude de la théorie des réseaux de neurones, théorie de les automates, la théorie du calcul et la cybernétique. Plus tard, deux informaticiens, GH Mealy et EF Moore, généralisé la théorie à des machines beaucoup plus puissantes dans des articles séparés, publiés en 1955-56. Les machines à états finis, la machine Mealy et la machine Moore, sont nommées en reconnaissance de leur travail.

pas un historien CS, mais soupçonne que le modèle McCulloch-Pitts n'incluait pas le non-déterminisme et le modèle Mealy - Moore l' a fait, dans une généralisation / abstraction naturelle du concept formel / théorique. notons que les DFA et les NFA ont le même pouvoir de représentation, de sorte que si l'on souhaite modéliser des systèmes réels, il y a le choix entre les deux. une différence fondamentale est qu'un NFA peut être beaucoup plus petit qu'un DFA équivalent (il existe donc par exemple un élément naturel de compression des données / informations). il y a aussi des aspects / analogues naturels du parallélisme dans l'étude NFA.

vzn
la source
3
Hé, je vous ai vu profil et ressemble à quelqu'un intentionnellement down-vote de vos réponses (partout où vous avez seulement deux downvotes) ... Cette réponse ne se trompe pas , la réponse ajoute des informations utiles. +1
Grijesh Chauhan
0

Tout d'abord, je tiens à remercier toutes les personnes qui ont répondu à la question.Toutes les réponses sont importantes et ajoutent des informations utiles.Mais comme c'est une question délicate pour les débutants et qui a besoin de suffisamment de temps pour bien la comprendre, je essaierait de résumer ce que j'ai gagné de toutes les réponses et de certains livres:

En fait, j'avais une confusion qui concernait le mécanisme du modèle non déterministe. Je me suis toujours interrogé sur la machine non déterministe car c'est une machine non mécanique qui n'existe pas dans le monde réel. J'ai toujours comparé Automata avec nos ordinateurs actuels qui sont de nature complètement déterministe, et je ne comprenais pas bien le modèle non déterministe. Maintenant, je pense que je comprends assez bien le modèle non terminologique: une machine non déterministe est une machine qui suit toujours ce chemin d'exécution qui conduit à l'acceptation de la chaîne (sans retour arrière), mais comment cela peut-il être possible dans la vie réelle? : Il est absolument impossible pour un ordinateur actuel d'être aussi intelligent pour prédire l'avenir. Alors pourquoi le non-déterminisme du tout?. La réponse à cette question est assez délicate, ce que j'ai conclu à ce sujet, c'est que: La théorie des automates existait lorsque les ordinateurs n'existaient pas (première théorie puis pratique). Il s'agit d'un sujet purement théorique et le concept de non-déterminisme est venu intuitivement. Le motif du sujet «Théorie des automates» n'était pas de traiter des ordinateurs pratiques. Mais lorsque pratiquement l'ordinateur arrive, alors en utilisant la théorie des automates, nous sommes en mesure de définir précisément les ordinateurs pratiques: quelles sont les limites des ordinateurs actuels.qui le problème algorithmique est très complexe pour les ordinateurs et si peu pratique (ici, le rôle du non-terminisme est très crucial pour lequel nous peut distinguer deux classes de complexité P et NP) .Quelles sont les solutions à ces problèmes impraticables par lesquelles il peut être exécuté relativement plus rapidement.etc. C'est l'utilité du non-déterminisme. Il s'agit d'un sujet purement théorique et le concept de non-déterminisme est venu intuitivement. Le motif du sujet «Théorie des automates» n'était pas de traiter des ordinateurs pratiques. Mais lorsque pratiquement l'ordinateur arrive, alors en utilisant la théorie des automates, nous sommes en mesure de définir précisément les ordinateurs pratiques: quelles sont les limites des ordinateurs actuels.qui le problème algorithmique est très complexe pour les ordinateurs et si peu pratique (ici, le rôle du non-terminisme est très crucial pour lequel nous peut distinguer deux classes de complexité P et NP) .Quelles sont les solutions à ces problèmes impraticables par lesquelles il peut être exécuté relativement plus rapidement.etc. C'est l'utilité du non-déterminisme. Il s'agit d'un sujet purement théorique et le concept de non-déterminisme est venu intuitivement. Le motif du sujet «Théorie des automates» n'était pas de traiter des ordinateurs pratiques. Mais lorsque pratiquement l'ordinateur arrive, alors en utilisant la théorie des automates, nous sommes en mesure de définir précisément les ordinateurs pratiques: quelles sont les limites des ordinateurs actuels.qui le problème algorithmique est très complexe pour les ordinateurs et si peu pratique (ici, le rôle du non-terminisme est très crucial pour lequel nous peut distinguer deux classes de complexité P et NP) .Quelles sont les solutions à ces problèmes impraticables par lesquelles il peut être exécuté relativement plus rapidement.etc. C'est l'utilité du non-déterminisme. Mais lorsque pratiquement l'ordinateur arrive, alors en utilisant la théorie des automates, nous sommes en mesure de définir précisément les ordinateurs pratiques: quelles sont les limites des ordinateurs actuels.qui le problème algorithmique est très complexe pour les ordinateurs et si peu pratique (ici, le rôle du non-terminisme est très crucial pour lequel nous peut distinguer deux classes de complexité P et NP) .Quelles sont les solutions à ces problèmes impraticables par lesquelles il peut être exécuté relativement plus rapidement.etc. C'est l'utilité du non-déterminisme. Mais lorsque pratiquement l'ordinateur arrive, alors en utilisant la théorie des automates, nous sommes en mesure de définir précisément les ordinateurs pratiques: quelles sont les limites des ordinateurs actuels.qui le problème algorithmique est très complexe pour les ordinateurs et si peu pratique (ici, le rôle du non-terminisme est très crucial pour lequel nous peut distinguer deux classes de complexité P et NP) .Quelles sont les solutions à ces problèmes impraticables par lesquelles il peut être exécuté relativement plus rapidement.etc. C'est l'utilité du non-déterminisme. Quelles sont les solutions à ces problèmes impraticables par lesquelles il peut être exécuté relativement plus rapidement.etc. C'est l'utilité du non-déterminisme. Quelles sont les solutions à ces problèmes impraticables par lesquelles il peut être exécuté relativement plus rapidement.etc. C'est l'utilité du non-déterminisme.

Veuillez me corriger s'il y a un problème.

Tanmoy
la source
Il est faux de dire qu'une machine non déterministe est une machine qui suit toujours le chemin d'exécution qui conduit à l'acceptation de la chaîne . Ça ne fait pas ça! Une machine non déterministe est une machine dont le fonctionnement permet d'effectuer certains choix non prémédités (= non déterministes) lors de l'exécution. Ces machines n'ont rien d'irréaliste, par exemple, elles peuvent demander à l'environnement de faire ces choix. Ces machines sont ensuite appliquées à des tâches pour lesquelles il considère que certains choix produiront un état d'acceptation.
reinierpost
@reinierpost: Vous dites donc que les machines non déterministes existent dans la vie réelle.
tanmoy
Oui. Voici un exemple: supposons que vous conduisez une voiture et que vous ne prenez aucune décision sur l'itinéraire à suivre. Par exemple, vous conduisez sans but ou vous suivez les instructions d'un navigateur humain ou d'un appareil de navigation. La voiture et vous êtes un système non déterministe pour conduire des lieux. Vous vous déplacez dans le trafic et continuez à rencontrer des choix dans quelle direction prendre. Pour vous et la voiture, ces choix ne sont pas déterministes: vous ne décidez pas dans quelle direction aller, mais étant donné cette décision, vous la suivrez.
reinierpost
@reinierpost: Existe-t-il un ordinateur non déterministe? Ma réponse est non. car s'il existe, les problèmes NP auront une complexité temporelle polynomiale. n'est-ce pas?
tanmoy
Que les ordinateurs soient déterministes ou non déterministes dépend de la façon dont vous les regardez. Lorsqu'un ordinateur s'arrête et attend que l'utilisateur fasse quelque chose et que ses prochaines actions dépendent de ce que fait l'utilisateur, vous pouvez dire que c'est un choix non déterministe. Non, cela n'implique pas que P = NP.
reinierpost
0

le non-déterminisme est utile car il vous aide à comprendre le déterminisme, mais pas l'inverse. On pourrait dire que le non-déterminisme est l'idée la plus importante. Une machine de Turing déterministe est un cas particulier d'une machine non déterministe. - Le non-déterminisme peut nous aider à comprendre pourquoi, sur les plateformes d'aujourd'hui, certains problèmes sont difficiles à cerner. Il existe un certain nombre de problèmes de calcul qui n'ont pas de solution efficace sur une plate-forme informatique déterministe, mais nous comprenons qu'il peut y avoir des solutions efficaces sur des plates-formes non déterministes. ... état, encodage, non-déterminisme, ils sont tous liés http://people.cs.umass.edu/~rsnbrg/teach-eatcs.pdf

Dans une machine de Turing déterministe, l'ensemble de règles prescrit au plus une action à effectuer pour une situation donnée. Une machine de Turing non déterministe (NTM), en revanche, peut avoir un ensemble de règles qui prescrivent plus d'une action pour une situation donnée. http://en.wikipedia.org/wiki/Non-deterministic_Turing_machine Si vous pouvez créer une boîte logicielle qui gère si bien les transitions d'état qu'elle peut gérer plus d'une action, vous pouvez obtenir des performances au-delà des machines déterministes.

À M
la source
Je ne suis pas sûr que les liens présumés avec la réalité soient utiles. Il est clair que nous ne pouvons pas construire une machine non déterministe (au moins aujourd'hui), c'est donc une construction entièrement théorique.
Raphael
Nous pouvons construire une machine non déterministe en laissant les décisions non déterministes être prises par quelque chose d'extérieur à la machine.
reinierpost
@ reinierpost, plus important encore, nous pouvons construire des machines non déterministes comme des machines déterministes, sans encourir de frais généraux exponentiels. voir le théorème de Savitch. en.wikipedia.org/wiki/Savitch's_theorem
Tom
@ Raphael, certaines références au monde réel sont importantes. Pourquoi la mise en cache fonctionne-t-elle? Parce que les événements dans le monde réel, qui est finalement la source de toutes les données, suivent une distribution normale. voir Localité temporelle: durablescope.blogspot.co.at/2009/11/…
Tom
@ reinierpost, et que quelque chose d'extérieur est ce que Turing a appelé une machine oracle. Je pense que vous pouvez penser que ce soit comme des données sortant du cache ou quelque chose comme une machine multi-bandes ou même puiser dans la mémoire à accès aléatoire.
Tom
0

Pourquoi le concept de non-déterminisme est-il utile?

Le déterminisme a une forte tendance à briser les symétries. Cette tendance est encore plus forte pour le déterminisme séquentiel, mais la notion de graphe orienté acyclique et un ordre topologique d'un tel graphe permet d'ignorer la différence entre déterminisme et déterminisme séquentiel. Le non-déterminisme est un sur-ensemble du déterminisme, qui permet de conserver plus de symétries. Lors de la conception de la solution d'un problème, commencer par la solution non déterministe permet de conserver des symétries utiles, et qui maintient la description de la solution petite et compacte. La rupture des symétries peut ensuite être déléguée à un stade ultérieur lors de la mise en œuvre, tout en convertissant la solution non déterministe en solution déterministe.

Souvent, le non-déterminisme signifie que la notion de fonction partielle est remplacée par la notion de relation. Dans ce cas, une machine non déterministe peut fonctionner à la fois en avant et en arrière dans le temps, ce qui n'est généralement pas possible pour une machine déterministe. Si nous travaillons avec des fonctions totales pour le déterminisme et des fonctions totales à valeurs multiples pour le non-déterminisme à la place, la symétrie n'est plus aussi agréable, mais elle peut toujours fonctionner.

Thomas Klimpel
la source
Pouvez-vous donner un exemple précis? J'ai du mal à voir ce que vous entendez par "symétrie" ici.
Raphael
@Raphael Que diriez-vous d'inverser (01) * 01 (0 + 1) * à (0 + 1) * 10 (10) * de sorte qu'il reconnaisse la chaîne d'entrée inversée, et appliquez cette symétrie à la machine non déterministe en inversant tout flèche et permutation des états de début et de fin? Je ne sais pas s'il existe des exemples beaucoup plus intéressants pour les machines à états finis, mais je pourrais essayer de trouver un exemple intéressant pour un PDA à la place.
Thomas Klimpel
J'ai écrit sur ma réponse à une question similaire dans un article de blog sur la réversibilité des relations binaires, des matrices substochastiques et des fonctions partielles .
Thomas Klimpel