Quelle est la différence entre le non-déterminisme et le caractère aléatoire?

38

J'ai récemment entendu ceci:
"Une machine non déterministe n'est pas la même chose qu'une machine probabiliste. En gros, une machine non déterministe est une machine probabiliste dans laquelle les probabilités de transitions ne sont pas connues".

Je me sens comme si je comprends le point mais je n'ai vraiment pas. Est-ce que quelqu'un pourrait m'expliquer cela (dans le contexte des machines ou en général)?

Edit 1:
Juste pour clarifier, la citation était dans le contexte d'automate fini, mais la question est significative pour les machines de Turing aussi comme d'autres ont répondu.

De plus, j'entends des gens dire - "... alors je choisis l'objet x de l'ensemble de manière non déterministe". J'avais l'habitude de penser qu'ils veulent dire - "au hasard". D'où la confusion.


la source
5
En informatique, on utilise parfois le terme "déterministe" pour souligner qu'un algorithme n'est pas aléatoire. D'où la confusion: déterministe signifie non randomisé, mais non déterministe ne signifie pas randomisé.
Jukka Suomela
Cette question m'amène à ce coin de SE ...
Troy Woo

Réponses:

27

Il est important de comprendre que les informaticiens utilisent le terme "non déterministe" différemment de la façon dont il est généralement utilisé dans d'autres sciences. Une MT non déterministe est en réalité déterministe au sens physique du terme - c’est-à-dire qu’une MNT produit toujours la même réponse sur une entrée donnée: elle accepte toujours ou rejette toujours. Une MT probabiliste acceptera ou rejettera une entrée avec une certaine probabilité. Ainsi, lors d'une exécution, elle pourrait l'accepter et une autre, elle pourrait la rejeter.

Plus en détail: à chaque étape du calcul effectué par un MNT, au lieu d’avoir une seule règle de transition, plusieurs règles peuvent être invoquées. Pour déterminer si la MNT accepte ou rejette, vous examinez toutes les branches possibles du calcul. (Ainsi, s'il existe, disons, exactement 2 transitions parmi lesquelles choisir à chaque étape et que chaque branche de calcul comporte un total de N étapes, il y aura brances au total à prendre en compte.) Pour une MNT standard, une entrée est: accepté si l' une des branches de calcul accepte.2N

Cette dernière partie de la définition peut être modifiée pour obtenir d'autres types de machines de Turing connexes. Si vous êtes intéressé par des problèmes ayant une solution unique, vous pouvez faire accepter la MT si une seule branche accepte. Si le comportement de la majorité vous intéresse, vous pouvez définir la MT à accepter si plus de la moitié des branches l’acceptent. Et si vous choisissez au hasard (selon une distribution de probabilité) l'une des branches possibles et acceptez ou refusez en fonction de ce que cette branche fait, alors vous avez une MT probabiliste.

Kurt
la source
Kurt, pouvez-vous s'il vous plaît expliquer comment le chiffre de 2 ^ N a été atteint. Si pour chaque branche, il y a 2 possibilités et s'il y a N étapes de ce type pour trouver la solution, cela ne ferait pas 2 ^ (N + 1) -1. J'essaie de voir cela comme un graphique et je peux me tromper. Pourriez-vous expliquer comment vous êtes arrivé au numéro 2 ^ N? Merci.
Gangadhar
Eh bien, si vous représentez le calcul sous forme d'arborescence, avec la racine représentant la configuration initiale en tant qu'étape 0, après N étapes, vous avez 2 ^ N feuilles et ce que j'appelle une branche est un chemin d'accès de la racine à une feuille. Il est vrai que vous aurez 2 ^ (N + 1) -1 nœuds au total, représentant toutes les configurations possibles à un moment donné du calcul. J'espère que ma terminologie va bien!
Kurt
Toutes les sciences utilisent la même définition du non-déterminisme unifié sur le concept d'entropie sans limite. Les résultats imprévisibles dans toutes les sciences sont dus à l’incapacité à énumérer a priori tous les résultats possibles d’un algorithme (ou d’un système), car celui-ci accepte des états non bornés, c’est-à-dire une classe de complexité NP. Spécifier une entrée particulière pour observer si elle s'arrête et noter que le résultat est idempotent revient, dans d'autres sciences, à maintenir constante le reste de l'entropie de l'univers tout en répétant le même changement d'état. L'informatique permet cette isolation d'entropie, contrairement aux sciences naturelles.
Shelby Moore III
1
@ShelbyMooreIII Non. Vous avez mal compris le concept de non-déterminisme qui apparaît en informatique.
David Richerby
@ David Richerby désolé David. Allez sur l' autre fil et voyez que je vous ai réfuté de manière éclatante. Vous pouvez essayer de réfuter la logique que j'ai présentée ici. Le simple fait d'affirmer sans preuves ni explications ne permet de gagner la vérité.
Shelby Moore III
18

Dans le contexte de Turing Machines, "non déterministe" signifie vraiment "parallèle". Un algorithme randomisé peut explorer de manière aléatoire les branches de l'arbre de calcul d'une machine de Turing non déterministe, mais une machine de Turing non déterministe peut les explorer - en même temps - en même temps, ce qui lui donne toute sa puissance.

Dans d'autres contextes (je ne peux pas dire de votre citation si vous parlez de Turing Machines), un algorithme aléatoire pourrait utiliser intentionnellement le hasard, alors qu'un algorithme que vous vouliez être déterministe pourrait finir par présenter un non-déterminisme à cause d'un bogue ...

En réponse à votre modification, lorsque les gens disent "choisissez un élément d'un ensemble de manière non déterministe", il est possible qu'ils signifient simplement "de manière aléatoire". Cependant, il est également possible qu'ils signifient "choisissez comme par magie l'élément -right- de l'ensemble". Une manière courante de visualiser les machines à calcul non déterministes est qu’elles «découvrent» comme par magie une solution, puis vérifient son exactitude. Bien sûr, vous pouvez voir cette supposition magique comme étant simplement le résultat de la vérification de toutes les possibilités en parallèle.

Aaron Roth
la source
Relatif à "choisir par magie le bon élément": lorsque le mot "non-déterminisme" est utilisé, les gens le qualifient parfois de "angélique". Il y a aussi le non-déterminisme «démoniaque». (Pourtant, comme vous le dites, l'essentiel est que tout se passe en parallèle.)
Radu GRIGore
13

Il existe plusieurs contextes différents où «déterministe», «aléatoire» et «non déterministe» signifient trois choses différentes. Dans les contextes où il y a plusieurs participants, tels que la sécurité et la concurrence, l'intuition est souvent quelque chose comme:

  • déterministe signifie «je peux choisir»

  • non déterministe signifie «quelqu'un d'autre peut choisir»

  • aléatoire signifie «personne ne peut choisir»

Quelques exemples:

  1. [simultanéité, aléatoire] Considérez un protocole de réseau tel que Ethernet , où plusieurs nœuds peuvent envoyer un message à tout moment. Si deux nœuds envoient un message à des intervalles très rapprochés, il se produit une collision: les messages se chevauchent et sont illisibles. Si une collision se produit, les deux nœuds doivent essayer d'envoyer les messages ultérieurement. Imaginez que vous écrivez la spécification d'Ethernet. Comment spécifiez-vous le délai entre les tentatives? (Les retards auraient dû être différents ou il y aurait encore une collision!)

    • déterministe: définit un algorithme que les deux nœuds doivent utiliser. Cela n'est pas fait pour Ethernet car, pour donner des résultats différents, l'algorithme devrait privilégier un nœud par rapport à l'autre (pour tout contenu de message donné), et Ethernet évite de le faire.

    • non déterministe: laissez chaque implémenteur décider. Ce n'est pas bon car les implémenteurs des deux nœuds peuvent choisir le même algorithme.

    • random: chaque nœud doit sélectionner une valeur de délai de manière aléatoire (avec une distribution spécifiée). Ça fonctionne comme ça. Il existe une faible probabilité que les deux nœuds choisissent le même délai et qu'il y ait une autre collision, mais la probabilité de succès augmente asymptotiquement vers 1 à mesure que le nombre de tentatives augmente.

  2. [simultanéité, non déterministe] Vous écrivez un algorithme simultané. Dans une situation spécifique, il peut y avoir une impasse. Comment pouvez-vous empêcher l'impasse de se produire? Cela dépend du type de planification de votre environnement de concurrence.

    • déterministe: le planificateur bascule toujours entre les threads à certains points bien définis, par exemple uniquement lorsque le code donne explicitement. Ensuite, il vous suffit simplement de vous assurer que les fils ne cèdent pas aux mauvais moments.

    • random: le programmateur est assuré de changer de thread de manière aléatoire. Ensuite, une stratégie viable peut être de détecter le blocage si cela se produit et de relancer l’algorithme depuis le début.

    • non déterministe (la plupart des planificateurs sont comme cela): vous ne savez pas quand le planificateur basculera entre les threads. Donc, vous devez vraiment éviter l'impasse. Si vous avez essayé de détecter et de redémarrer de manière aléatoire, vous courez le risque que le planificateur planifie vos threads exactement de la même manière, encore et encore.

  3. [sécurité, aléatoire] Vous écrivez une application avec une invite de mot de passe. Comment modélisez-vous un attaquant?

    • déterministe: l'attaquant essaye toujours les mêmes mots de passe. Ce n’est pas un modèle utile d’attaquant - les attaquants ne sont pas prévisibles par définition.

    • non déterministe: l'attaquant connaît votre mot de passe d'une manière ou d'une autre et y entre. Cela montre la limitation des mots de passe: ils doivent être gardés secrets. Si votre mot de passe est secret, cet attaquant est irréaliste.

    • random: l'attaquant tente des mots de passe de manière aléatoire. Dans ce cas, il s’agit d’un modèle réaliste d’attaquant. Vous pouvez étudier le temps qu'il faudrait pour que l'attaquant devine votre mot de passe en fonction de la distribution aléatoire qu'il utilise. Un bon mot de passe est long pour toute distribution réaliste.

  4. [sécurité, non déterministe] Vous écrivez une application et vous craignez qu'elle puisse avoir une faille de sécurité. Comment modélisez-vous un attaquant?

    • déterministe: l'attaquant sait tout ce que vous savez. Encore une fois, ce n'est pas un modèle utile d'attaquant.

    • random: l'attaquant jette des ordures aléatoires et espère faire planter votre programme. Cela peut être utile parfois ( fuzzing ), mais l'attaquant pourrait être plus intelligent que cela.

    • non déterministe: s'il y a un trou, l'attaquant le trouvera éventuellement. Donc, vous feriez mieux de durcir votre application (augmentez les besoins en informations de l’attaquant; notez que s’il s’agit d’une exigence de renseignements plutôt que d’une exigence de calcul, cela compte comme non déterministe jusqu’à ce que l’intelligence artificielle apparaisse), ou mieux, de prouver qu’il n’existe pas. trou de sécurité et donc un tel attaquant n'existe pas.

Gilles, arrête de faire le mal
la source
Tourne Correction autour du mot manquant prouvent dans vos déclarations: déterministes est « Je peux prouver que je choisis (c. -à spécifier entièrement le résultat qui se termine sur mon entrée dans la classe de complexité P) », non déterministes est « Je ne peux pas prouver que je choisis (c’est-à-dire que la preuve de la résiliation est indécidable dans la classe de complexité NP) »et aléatoirement est« Je peux prouver que je peux choisir la moitié du temps (c.-à-d. la classe de complexité ZPP) ».
Shelby Moore III
@ShelbyMooreIII Je ne comprends pas où vous voulez en venir. Le déterminisme ne consiste pas, en général, à prouver que quelque chose est effectivement déterministe, ni à ce que certains problèmes appartiennent à une classe de complexité donnée. De plus, les classes de complexité ne permettent pas au système lui-même de prouver quelque chose sur son déterminisme (la plupart des problèmes n’ont même pas la notion de prouver à l’intérieur du système!).
Gilles, arrête de faire le mal '11
Le non-déterminisme est toujours le résultat d'entropie illimitée, donc une autre façon de le dire est que je ne peux pas prouver que je choisis le résultat (car je ne peux pas prouver que mon choix va se terminer). Tout ce que je peux faire est d'essayer, ce qui signifie que je dois énumérer tous les choix que je veux faire avant de savoir s'il se terminera. Alors qu'avec le déterminisme, je peux prouver que je choisis le résultat car il doit être terminé. La randomisation est l'endroit où je peux prouver que je ne peux choisir qu'une quantité aléatoire de temps, car une partie de l'entropie n'est pas sous mon contrôle. Si je connais le montant qui ne dépend pas de moi, je peux prouver avec précision les statistiques de.
Shelby Moore III
Convenu que ce n'est pas la classe de complexité NP qui donne lieu au non déterminisme, mais que NP est une dépendance. Turing-complete est un exemple de non-déterminisme. Plz voir mon commentaire sous la réponse de Kurt, ainsi que ma réponse sur le fil connexe . Ce que je veux dire avec vous concerne ce qui est précisément prouvé et imprévisible pour les termes déterministe, non déterministe et aléatoire. Tout est question d'entropie (et non de basse )
Shelby Moore III
9

Un exemple pour rendre les choses plus claires:

Supposons que vous deviez choisir une porte à ouvrir parmi 10000 portes (disons qu'il y a un prix derrière l'une des portes). Choisir au hasard signifie que vous choisiriez l'une des 10000 portes et y entreriez. S'il y a un prix derrière une seule porte, vous ne le trouverez probablement pas. Une machine non déterministe entrerait simultanément dans toutes les 10 000 portes. S'il y a un prix n'importe où, la machine non déterministe le trouvera.

Robin Kothari
la source
8
Alternativement, une machine non déterministe n'ouvrirait qu'une porte, mais ce serait toujours la bonne.
Jeffε
3
Oui, exactement. Ce serait la caractérisation la plus chanceuse possible des machines non déterministes.
Robin Kothari
@RobinKothari: "Alternativement, une machine non déterministe n'ouvrirait qu'une porte, mais ce serait toujours la bonne" .Et "Une machine non déterministe entrerait simultanément dans toutes les 10000 portes"?
tanmoy
3
@tan: Les deux interprétations sont correctes. Contrairement aux machines déterministes et aléatoires, qui sont physiquement réalisables, une machine non déterministe est un objet imaginaire. Vous pouvez donc l’imaginer comme bon vous semble, le fait est qu’il trouve toujours la bonne porte. Peut-être que c'est le meilleur choix, peut-être quelqu'un a-t-il secrètement dit à la machine où se trouvait le prix, peut-être qu'il vérifie toutes les portes comme par magie, etc.
Robin Kothari
5

Définition de machine de Turing non déterministe : machine de Turing qui possède plusieurs états suivants pour certaines combinaisons de contenu de la cellule et de l'état actuels. Une entrée est acceptée si une séquence de mouvements mène à l'acceptation.

Définition de la machine de Turing probabiliste : Machine de Turing non déterministe qui choisit de manière aléatoire les transitions disponibles à chaque point, selon une distribution de probabilité.

La machine de Turing probabiliste est une machine de Turing non déterministe pouvant faire des erreurs.

PPT j'ai trouvé utile.

Pratik Deoghare
la source
5

Je préfère la définition suivante:

Il n’existe pas de machine probabiliste de Turing! Il n'y a que des machines déterministes (à chaque étape un seul état de suivi possible) et des machines non déterministes (à chaque étape un nombre constant d'états de suivi possibles).

Le non-déterminisme fonctionne comme suit: considérons une machine non déterministe qui s'arrête sur chaque entrée (possible si le problème est décidable), où chaque calcul possible utilise le même nombre d'étapes et où chaque étape a exactement 2 états de suivi possibles ( les deux pas vraiment une restriction). Comme dans la définition de NP, une machine non déterministe accepte une entrée s'il existe au moins un calcul acceptant possible et la rejette si tous les calculs sont rejetés.

Le hasard entre en jeu de la manière suivante: Vous pouvez choisir de manière uniforme et aléatoire un chemin unique de calcul à partir d'une machine non déterministe, comme indiqué ci-dessus. Vous acceptez si et seulement si ce chemin de calcul choisi au hasard accepte. Cette approche randomisée "résout" votre problème si, avec une probabilité écrasante, cette réponse est correcte.

La différence entre le non-déterminisme et le caractère aléatoire réside donc dans le fait de savoir si vous recherchez la simple existence d'une réponse correcte Oui (et de réponses Non fiables), ou si vous souhaitez résoudre votre problème "la plupart du temps" .

ARM
la source
-1 Erreurs dans votre premier paragraphe. Des machines de Turing probabilistes existent et échantillonnent un tirage au sort d'entropie externe, voir la classe de complexité ZPP. Le non-déterminisme a un nombre illimité non borné, cf. la classe de complexité NP. Le déterminisme est la classe de complexité P et vous l'avez bien compris.
Shelby Moore III
Je pense que vous avez mal interprété ma réponse. Je soutiens que vous n'avez pas besoin d'une machine différente (avec une fonctionnalité de lancement de pièce ou autre) d'une machine à faire non déterministe "ordinaire" pour définir des classes de complexité probabilistes. Vous pouvez aussi bien utiliser un MNT et simplement utiliser une définition différente de l'acceptation, à savoir une définition dans laquelle "la plupart des chemins de calcul acceptent l'entrée", par opposition à "il existe au moins un seul chemin d'acceptation pour l'entrée".
MRA
3

Pour rester simple: une machine non déterministe peut choisir de manière optimale le résultat de chaque tirage (si vous aimez l'analogie avec une machine probabiliste). Vous pouvez également imaginer qu'il exécute le calcul pour chaque résultat du lancer de pièce en parallèle.

Serge Gaspers
la source
1

Reculer pendant le débogage pour motiver le non-déterminisme

La notion de machine non déterministe se suggère lorsque vous souhaitez revenir en arrière (dans le temps) dans un programme lors du débogage. Dans un ordinateur typique, chaque étape ne modifie qu'une quantité finie de mémoire. Si vous enregistrez toujours ces informations pour les 10000 étapes précédentes, vous pouvez alors avancer et revenir en arrière dans le programme. Cette possibilité ne se limite pas aux programmes de jouets. Si vous essayez de supprimer l'asymétrie entre les pas en avant et les pas en arrière, vous vous retrouvez avec la notion de machine non déterministe.

Similarités et différences entre le non déterminisme et le caractère aléatoire

Bien que les machines probabilistes partagent certaines caractéristiques avec les machines non déterministes, cette symétrie entre les pas en avant et les pas en arrière n'est pas partagée. Pour le voir, modélisons les étapes ou les transitions d'une machine déterministe par des fonctions (totales ou partielles), les transitions d'une machine non déterministe par des relations (finies) et les transitions d'une machine probabiliste par des matrices (sub) stochastiques . Par exemple, voici les définitions correspondantes pour les automates finis

  • Q
  • Σ
  • δ:Q×ΣQ
  • Δ:Q×ΣP(Q)
  • ΔQ×Σ×Q
  • Δ:ΣP(Q×Q)
  • δ:ΣssM(Q)

P(Q)QssM(Q)Q

Il existe de nombreuses conditions d'acceptation raisonnables

Les transitions ne sont qu'une partie d'une machine, les états initial et final, les conditions possibles de sortie et d'acceptation sont également importants. Toutefois, il existe très peu de conditions d'acceptation non équivalentes pour les machines déterministes, un certain nombre de conditions d'acceptation raisonnables pour les machines non déterministes (NP, coNP, #P, ...) et de nombreuses conditions d'acceptation possibles pour les machines probabilistes. Par conséquent, cette réponse se concentre principalement sur les transitions.

La réversibilité n'est pas triviale pour les machines probabilistes

PPTPPPBAkABk

La réversibilité est délicate même pour les machines non déterministes

PPTPPRRopRRRRRRopR=RRopRRop=RopPQPQ

Ces considérations ont également un sens pour les automates à pile

Cet article suggère que l'une des motivations du non-déterminisme consiste à supprimer cette asymétrie entre les pas en avant et les pas en arrière. Cette symétrie du non-déterminisme est-elle limitée aux automates finis? Voici les définitions symétriques correspondantes pour les automates à pile

  • Q
  • Σ
  • Γ
  • δ:Q×Γ×(Σ{ϵ})Q×Γ{0,2}δ(q,γ,ϵ)ϵδ(q,γ,σ)=ϵσΣ
  • Δ:Q×Γ{0,1}×(Σ{ϵ})P(Q×Γ{0,1})
  • ΔQ×Γ{0,1}×(Σ{ϵ})×Q×Γ{0,1}
  • Δ:Σ{ϵ}P(Q×Γ{0,1} × Q×Γ{0,1})
  • δ:Σ{ϵ}ssM(Q×Γ{0,1})δ(ϵ)+δ(σ)ssM(Q×Γ{0,1})σΣ

ϵΓ{0,2}={ϵ}Γ(Γ×Γ)Γ{0,1}={ϵ}ΓΓ

Vérification schématique de l'inversion pour des opérations d'entrée et de pile en progression

bΣΣ{ϵ}

a|bca|bcab|c
a|bcab|cab|c
c|bac|bacb|a

ϵΣ{ϵ}

a|bca|bca|bc
a|bca|bca|bc
cb|acb|acb|a

Voici un schéma d’une opération d’entrée en progression dont l’inversion serait très mauvaise

a|bca|bcab|ca|bcab|cab|cc|bac|bacb|a

(s,t)Γ{0,1}×Γ{0,1}, there are the three cases (s,t)=(a,ϵ), (s,t)=(ϵ,a), and (s,t)=(a,b). The stack operation (a,ϵ) gets reversed to (ϵ,a) as follows

abab|b
ab|bb
b|bab

The stack operation (a,b) gets reversed to (b,a) as follows

acacbc
acbcbc
bcbcac

A generalized stack operation (ab,cde)Γ×Γ would be reversed to (cde,ab)

abfabfcdef
abfcdefcdef
cdefcdefabf

Reversibility for Turing machines

A machine with more than one stack is equivalent to a Turing machine, and stack operations can easily be reversed. The motivation at the beginning also suggests that reversal (of a Turing machine) should not be difficult. A Turing machine with a typical instruction set is not so great for reversal, because the symbol under the head can influence whether the tape will move left or right. But if the instruction set is modified appropriately (without reducing the computational power of the machine), then reversal is nearly trivial again.

A reversal can also be constructed without modifying the instruction set, but it is not canonical and a bit ugly. It might seem that the existence of a reversal is just as difficult to decide as many other question pertaining to Turing machines, but a reversal is a local construction and the difficult questions often have a global flavor, so pessimism would probably be unjustified here.

The urge to switch to equivalent instruction sets (easier to reverse) shows that these questions are less obvious than they first appear. A more subtle switch happened in this post before, when total functions and stochastic matrices were replaced by partial functions and substochastic matrices. This switch is not strictly necessary, but the reversal is ugly otherwise. The switch to the substochastic matrices was actually the point where it became obvious that reversibility is not so trivial after all, and that one should write down details (as done above) instead of taking just a high level perspective (as presented in the motivation at the beginning). The questions raised by Niel de Beaudrap also contributed to the realization that the high level perspective is slightly shaky.

Conclusion

Non-deterministic machines allow a finite number of deterministic transitions at each step. For probabilistic machines, these transitions additionally have a probability. This post conveys a different perspective on non-determinism and randomness. Ignoring global acceptance conditions, it focuses on local reversibility (as a local symmetry) instead. Because randomness preserves some local symmetries which are not preserved by determinism, this perspective reveals non-trivial differences between non-deterministic and probabilistic machines.

Thomas Klimpel
la source
Are you assuming that non-deterministic transitions are one-to-many relations? What if two different configurations can transition to a common configuration, among others? — It seems to me that the difference between randomness and nondeterminism is not reversibility (neither are, without further constraint), but rather how one attributes significance to branches according to the result: perfectly democratic for randomness, or preferentially sensitive to "yes" or "no" answers for nondeterminism.
Niel de Beaudrap
@NieldeBeaudrap I assume that non-deterministic transitions are "arbitrary" relations (one for each symbol from the input alphabet). I can reverse them, swap start and end state, and get again a non-deterministic finite state machine, which accepts the reversed input string. This is what I call "run the machine backwards in time". (The machine accepts if there is at least one path from start to end state in the non-deterministic case, and this condition doesn't change when reversing time.) Please try to convince yourself that this works at least for a finite state machine.
Thomas Klimpel
So, you refer to the dual of the machine. For NFAs this seems a meaningful notion of reversibility. It's also clear that the dual of an NTM (with a single accept state) is another NTM, but I would hesitate to say that it is the same machine being run in reverse. Does your answer amount just to "Nondeterminism allows you to obtain closure under duals, random (and deterministic) machines aren't"?
Niel de Beaudrap
@NieldeBeaudrap My idea is certainly to run backwards in time, but I know that this isn't satisfied perfectly (because the conditions for a generalized inverse of an inverse semigroup are not satisfied). But what I tried to convey is that random (and deterministic) machines don't always allow this sort of reversal.
Thomas Klimpel
I wrote this answer in a blog post about Reversibility of binary relations, substochastic matrices, and partial functions.
Thomas Klimpel
0

In the context of Turing Machines (TMs) and automata theory, a non-deterministic machine is one in which any instantiation of the machine which accepts is fine. In this sense, it is like running multiple deterministic machines in parallel and take the output of any instances that accept the input. In fact there is a (deterministic) algorithm to transform any non-deterministic automaton (with n states) into an equivalent deterministic one (with 2n states, exponential) by considering equivalence classes of states, no matter if the algorithm implemented in the machine involves randomisation or probabilities (see below).

But if the algorithm implemented in the machine, involves randomisation or probabilities (intrinsic in the algorithm), then it is a randomised (or probabilistic) machine.

In general, it is always possible to remove non-determinism from a machine and construct a deterministic equivalent (see algorithm above), but the same cannot be done (in general) to remove randomisation (in the context of the above) because it is intrinsic to the algorithm implemented.

Note that in the light of the above, both a deterministic machine and a non-deterministic machine can be probabilistic if the algorithm (involved) uses randomisation (or probabilities) in this way.

To sum up, non-determinism in automata (in this context) refers to classes of similar automata, while randomisation or probabilistic machines refer to the (intrinsic application of randomisation in the) actual algorithms implemented by these automata.

Nikos M.
la source