Veuillez expliquer cette définition formelle du calcul

J'essaie d'attaquer TAOCP une fois de plus, étant donné la lourdeur littérale des volumes que j'ai du mal à m'y engager sérieusement. Dans TAOCP 1, Knuth écrit, page 8, les concepts de base:

Soit un ensemble fini de lettres. Soit l'ensemble de toutes les chaînes de (l'ensemble de toutes les séquences ordonnées ... où et est dans pour ). L'idée est de coder les états du calcul pour qu'ils soient représentés par des chaînes de . Soit maintenant un entier non négatif et Q (l'état) l'ensemble de tous , où est dans et j est un entier ; laisse$A$$A^*$$A$$x_1$ $x_2$$x_n$$n \ge 0$$x_j$$A$$1 \le j \le n$$A^*$$N$$(\sigma, j)$$\sigma$$A^*$$0 \le j \le N$$I$(l'entrée) le sous - ensemble de Q avec et soit (la sortie) le sous - ensemble avec . Si et sont des chaînes dans , nous disons que se produit dans si a la forme pour les chaînes et . Pour compléter notre définition, soit une fonction du type suivant, définie par les chaînes , et les entiers , pour$j=0$$\Omega$$j = N$$\theta$$\sigma$$A^*$$\theta$$\sigma$$\sigma$$\alpha \theta \omega$$\alpha$$\omega$$f$$\theta_j$$\phi_j$$a_j$$b_j$$0 \le j \le N$ :

• $f((\sigma, j)) = (\sigma, a_j)$ si ne se produit pas dans$\theta_j$$\sigma$
• $f((\sigma, j)) = (\alpha \psi_j \omega, b_j)$ si est la chaîne la plus courte possible pour laquelle$\alpha$$\sigma = \alpha \theta_j \omega$
• $f((\sigma,N)) = (\sigma, N)$

N'étant pas informaticien, j'ai du mal à saisir tout le passage. J'ai en quelque sorte l'idée qui se cache derrière un système d'opcodes, mais je n'ai pas progressé efficacement dans la compréhension. Je pense que le principal problème est que je ne sais pas comment le lire efficacement.

Serait-il possible d'expliquer le passage ci-dessus pour que je puisse le comprendre, et me donner une stratégie pour entrer dans la logique d'interprétation de ces affirmations?

Nous manquons de contexte, donc je n'ai aucune idée de ce que Knuth essaie de faire, mais voici comment interpréter une machine de Turing de cette façon. Cela vous aidera peut-être à comprendre ce qui se passe. En général, un bon moyen de maîtriser un concept est de jouer avec lui. Dans le cas des paradigmes de programmation, cela signifie écrire un programme. Dans ce cas, je vais montrer comment écrire n'importe quel programme.

Supposons que la bande de la machine de Turing ait des symboles $\{0,1,\epsilon\}$ (où $\epsilon$ signifie "vide"), et ajoutez un autre symbole qui représente l'emplacement de la tête $H$. Vos états vont être des paires du formulaire$(q,\alpha)$, où $q$ est un état de la machine de Turing, et $\alpha \in \{0,\ldots,14\}$. Nous identifions également$(F,0)$ avec $N$ pour tout état final.

Entrée (non vide) $x$, votre point de départ sera $(Hx,(s,0))$, où $s$est l'état de départ. La partie difficile est de coder les états. Supposons qu'à l'état$q$, lors de la lecture de l'entrée $x$, vous le remplacez par $a(q,x)$, se déplacer dans la direction $D(q,x) \in \{L,R\}$et passer à l'état $\sigma(q,x)$. Pour le$\theta$s, nous avons

$$\begin{align*} \theta_{q,0} &= 0H0, & \theta_{q,1} &= 0H1, & \theta_{q,2} &= 0H\epsilon, \\ \theta_{q,3} &= 1H0, & \theta_{q,4} &= 1H1, & \theta_{q,5} &= 1H\epsilon, \\ \theta_{q,6} &= \epsilon H0 & \theta_{q,7} &= \epsilon H1, & \theta_{q,8} &= \epsilon H\epsilon, \\ \theta_{q,9} &= H0, & \theta_{q,10} &= H1, & \theta_{q,11} &= H\epsilon, \\ \theta_{q,12} &= 0H, & \theta_{q,13} &= 1H, & \theta_{q,14} &= \epsilon H. \end{align*}$$ Pour le $a$s, nous avons $a_{q,i} = (q,i+1)$ pour $i < 14$, et $a_{q,14} = (q,14)$, bien que nous ne devrions jamais vraiment aller aussi loin. Pour le$b$s, nous avons $$\begin{align*} &b_{q,0} = b_{q,3} = b_{q,6} = b_{q,9} = (\sigma(q,0),0), \\ &b_{q,1} = b_{q,4} = b_{q,7} = b_{q,10} = (\sigma(q,1),0), \\ &b_{q,2} = b_{q,5} = b_{q,8} = b_{q,11} = b_{q,12} = b_{q,13} = b_{q,14} = (\sigma(q,\epsilon),0). \end{align*}$$ Reste maintenant à déterminer $\psi$s. Laisser$a_0 = a(q,0)$. Si$D(q,0) = L$ puis $$\begin{align*} \psi_{q,0} &= H0a_0, & \psi_{q,3} &= H1a_0, & \psi_{q,6} &= \psi_{q,9} = H\epsilon a_0. \end{align*}$$ Si $D(q,0) = R$ puis $$\begin{align*} \psi_{q,0} &= 0a_0H, & \psi_{q,3} &= 1a_0H, & \psi_{q,6} &= \epsilon a_0 H, & \psi_{q,9} &= a_0H\epsilon. \end{align*}$$ Ensuite, laissez $a_1 = a(q,1)$. Si$D(q,1) = L$ puis $$\begin{align*} \psi_{q,1} &= H0a_1, & \psi_{q,4} &= H1a_1, & \psi_{q,7} &= \psi_{q,10} = H\epsilon a_1. \end{align*}$$ Si $D(q,1) = R$ puis $$\begin{align*} \psi_{q,1} &= 0a_1H, & \psi_{q,4} &= 1a_1H, & \psi_{q,7} &= \epsilon a_1 H, & \psi_{q,10} &= a_1 H\epsilon. \end{align*}$$ Enfin, laissez $a_\epsilon = a(q,\epsilon)$. Si$D(q,\epsilon) = L$ puis $$\begin{align*} \psi_{q,2} &= H0a_\epsilon, & \psi_{q,5} &= H1a_\epsilon, & \psi_{q,8} &= \psi_{q,11} = H\epsilon a_\epsilon, \\ \psi_{q,12} &= H0a_\epsilon, & \psi_{q,13} &= H1a_\epsilon, &\psi_{q,14} &= H\epsilon a_\epsilon. \end{align*}$$ Si $D(q,\epsilon) = R$ puis $$\begin{align*} \psi_{q,2} &= 0a_\epsilon H, & \psi_{q,5} &= 1a_\epsilon H, & \psi_{q,8} &= \epsilon a_\epsilon H, & \psi_{q,11} &= a_\epsilon H\epsilon, \\ \psi_{q,12} &= 0a_\epsilon H, & \psi_{q,13} &= 1a_\epsilon H, & \psi_{q,14} &= \epsilon a_\epsilon H. \end{align*}$$

Maintenant, appliquez $f$à plusieurs reprises jusqu'à ce que vous soyez coincé. Si vous suivez la construction, vous verrez que nous avons simulé le fonctionnement de la machine de Turing.

Décomposons-le petit à petit. Tout d'abord, rappelez-vous ce que Knuth a écrit à la page 7:

Définissons formellement une méthode de calcul comme étant un quadruple$(Q,I,\Omega,f)$, dans lequel $Q$ est un ensemble contenant des sous-ensembles $I$ et $\Omega$, et $f$ est une fonction de $Q$en lui-même. [...] Les quatre quantités$Q$, $I$, $\Omega$, $f$ sont destinés à représenter respectivement l'état du calcul, l'entrée, la sortie et la règle de calcul.

Ceci est le contour. Vous devez lire "représenter" comme "contenir";$Q$ va contenir des états (dont certains sont en $I$, certains sont en $\Omega$) et $f$va être une fonction de transition entre les états; pensez-y comme un programme.

Laisser $A$être un ensemble fini de lettres. Laisser$A^*$ être l'ensemble de toutes les chaînes $A$ (l'ensemble de toutes les séquences ordonnées $x_1$ $x_2$ ... $x_n$ où $n \ge 0$ et $x_j$ est dans $A$ pour $1 \le j \le n$).

Ceci est juste une réitération de ce $A^*$est. Voir aussi ici .

L'idée est de coder les états du calcul afin qu'ils soient représentés par des chaînes de $A^*$.

C'est probablement la phrase clé. Nous parlons de calculs , c'est-à-dire des séquences d'exécution de certaines instructions (langage de programmation) qui manipulent certains états , qui peuvent être considérées comme des valeurs dans les cellules de mémoire ou des évaluations de variables. Knuth dit ici qu'il veut encoder ces états de manière abstraite, à savoir sous forme de mots sur un alphabet.

Exemple: considérons un programme qui utilise (tout au plus)$k$variables, chacune d'entre elles stockant un entier. Autrement dit, un état est donné par le tuple de valeurs$(x_1, \dots, x_k)$ où $x_k$ est la valeur (actuelle) du $k$-th variable. Afin de coder les états de cette forme dans un langage formel, nous pouvons choisir$A = \{0,1,\#\}$ avec $\#$un séparateur. Maintenant, modélisez un tel état en$\#\overline{x_1}\#\cdots\#\overline{x_k}\#$ où $\overline{x_i}$ est le codage binaire de $x_i$.

Plus précisément, $(3,5,0)$ serait $\#11\#101\#0\#$.

Maintenant, laisse $N$ être un entier non négatif et Q être l'ensemble de tous $(\sigma, j)$, où $\sigma$ est dans $A^*$ et j est un entier $0 \le j \le N$; laisser$I$ être le sous-ensemble de Q avec $j=0$ et laisse $\Omega$ être le sous-ensemble avec $j = N$.

Vous y avez mal cité (mauvais Stefano!); les parenthèses ne sont pas dans le texte original et elles étaient trompeuses (voir ci-dessus). Knuth définit$Q$ici comme l'ensemble de tous les états possibles ($\sigma \in A^*$) à tous les endroits possibles du calcul ($j$peut être compris comme compteur de programme). Donc,$Q$ contient tous les états indexés par les instructions tout calcul de l'algorithme donné par $f$peut assumer. Par définition, nous commençons par le compteur de programme$0$ et se terminent par $N$, donc les états indexés $0$ sont des états d'entrée et ceux indexés $N$ sont des états de sortie.

Si $\theta$ et $\sigma$ sont des chaînes $A^*$, nous disons que $\theta$ se produit dans $\sigma$ si $\sigma$ a la forme $\alpha \theta \omega$ pour cordes $\alpha$ et $\omega$.

J'espère que cela est clair; ce n'est qu'une (re) définition des sous-chaînes.

Pour compléter notre définition, laissez $f$ être une fonction du type suivant, définie par les chaînes $\theta_j$, $\phi_j$ et les entiers $a_j$, $b_j$ pour $0 \le j \le N$:

• $f((\sigma, j)) = (\sigma, a_j)$ si $\theta_j$ ne se produit pas dans $\sigma$
• $f((\sigma, j)) = (\alpha \psi_j \omega, b_j)$ si $\alpha$ est la chaîne la plus courte possible pour laquelle $\sigma = \alpha \theta_j \omega$
• $f((\sigma,N)) = (\sigma, N)$

Il s'agit d'un petit langage de programmation; si vous corrigez$\theta_j, \psi_j, a_j, b_j$, vous avez un programme. Sur le compteur de programme$j$, $f$ remplace l'occurrence la plus à gauche $\theta_j$ dans l'état avec $\psi_j$ et va à la déclaration $b_j$. Si il n'y a pas$\theta_j$ dans l'état actuel, il va à la déclaration $a_j$. Le programme boucle si l'instruction$N$ est atteint, modélisation de la terminaison.

Dans la moitié supérieure de la page 8, il y a un exemple plus concret de "programme" $f$. Gardez à l'esprit que Knuth va utiliser le langage d'assemblage plus tard; cela informe comment il regarde les programmes (déclarations atomiques reliées par des sauts).

Ce texte décrit le pseudocode (Python) suivant:

subs = a list of string pairs  
As = a list of integers  
Bs = a list of integers

def f(state, pc):  
  if pc == N: return (state, pc)  
  if state.find(subs[pc][0]) != -1:  
    return (state.replace(subs[pc][0],subs[pc][1],1), Bs[pc])  
  else:  
    return (state,As[pc])  

La fonction f va vraisemblablement être appliquée à plusieurs reprises.

Les trois derniers points sont tout ce dont vous avez vraiment besoin une fois que vous avez compris les notations. Tout ce qui précède est un peu similaire à l'explication du fonctionnement de Python avant de donner le code Python.