Définitions Utilisées en Calculabilité et Complexité

En-tête 2

Machine de Turing

Une machine de Turing (MT) est un quintuplet M=\left(K,\Sigma,\delta,s,H\right)

  • K est un ensemble fini d'états
  • \Sigma est un alphabet (fini) contenant les symboles \sqcup (blanc) et \triangleright (début de mot)
  • s\in K : état initial
  • H\in K : ensemble des état d'arrêt
  • \delta : fonction de transition
    • \delta: \left(K \setminus H\right) \times \Sigma \mapsto K\times \left(\Sigma \cup \left\{ \leftarrow, \rightarrow\right\}\setminus \left\{ \triangleright \right\}\right)
    • \left[\delta\left(p,\triangleright\right)=\left(q,\sigma\right)\right]\Rightarrow\left[\sigma=\rightarrow\right]
· 2009/10/11 16:26 · Maurice Lanselle

Configuration (d'une MT)

Soit M=\left(K, \Sigma, \delta, s, H\right) une machine de Turing. Une configuration de M est un élément de

K \times \triangleright\Sigma^* \times\left(\Sigma^* \left(\Sigma\setminus \left\{ \sqcup \right\}\right) \cup\left\{ e \right\} \right)


Pas de Calcul

Soientt M=\left(K, \Sigma, \delta, s, H\right) une machine de Turing et \left(q_1,w_1 a_1 u_1\right) et \left(q_2,w_2 a_2 u_2\right) deux configuration de M. On dis qu'on passe de la première à la deuxième en un pas de calcul si et seulement si \exists \beta | \beta\in\left(\Sigma \cup \left\{\leftarrow,\rightarrow\right\}\right) tel que

  • \delta\left(q_1,a_1\right) = \left(q_2,b\right)
  • la situation est l'une de ces trois:
    1. b\in\Sigma, \&\quad a_2=b, w_2=w_1, u_2=u_1
    2. b \; =\; \rightarrow, \text{ et } w_2=w_1 a_1 et
      • soit u_1\ne e \; \Rightarrow \; u_1=a_2 u_2
      • soit u_1 = e \; \Rightarrow \; a_2=\sqcup,u_2=e
    3. b\;=\;\leftarrow, \text{ et } w_1=w_2 a_2 et
      • soit a_1 u_1 = \sqcup\quad \& \quad u_2=e
      • soit u_2 = a_1 u_1

On note alors \displaystyle \left(q_1, w_1 a_1 u_1\right) \vdash_{M} \left(q_2, w_2 a_2 u_2\right)

Cas w1 a1 u1
2.1 w2 a2 u2
Cas w1 a1 u2=e
2.2 w2 a_2=\sqcup u2=e
Cas w1 a1 u1
3.1 w2 a2 u2
· 2009/10/11 21:40 · Maurice Lanselle

Langage décidé

Soit M=\left(K,\Sigma,\delta,s,\left\{y,n\right\}\right).

  • On appelle configuration acceptée ou réussie de M une configuration de la forme \left(y,\omega\right).
  • On appelle configuration rejettée ou échouée de M une configuration de la forme \left(n,\omega\right).
  • On dit que M accepte le mot \displaystyle \omega \quad \Leftrightarrow \; \left(s,\triangleright \sqcup \omega\right) \vdash_M^* \;\left(y,\omega\prime\right)
  • On dit que M rejette le mot \displaystyle \omega \quad \Leftrightarrow \; \left(s,\triangleright \sqcup \omega\right) \vdash_M^* \;\left(n,\omega\prime\right)
  • On dit que M décide un langage L\subset\Sigma_0^* \subset\Sigma\setminus\left\{\triangleright, \sqcup\right\} si et seulement si \forall \omega\in\Sigma_0^*
    • \omega\in L \Rightarrow M\text{ accepte }\omega
    • \omega\notin L \Rightarrow M\text{ rejette }\omega

Langage récursif

Un langage L est dit récursif si et seulement si il existe une machine Turing qui le décide.

· 2009/10/11 21:34 · Maurice Lanselle
 
m1ilc/c_et_c_defs.txt · Dernière modification: 2009/10/09 19:01 par suitable
 
Sauf mention contraire, le contenu de ce wiki est placé sous la licence suivante :CC Attribution-Noncommercial-Share Alike 3.0 Unported
Recent changes RSS feed Donate Powered by PHP Valid XHTML 1.0 Valid CSS Driven by DokuWiki