I.3 Fonctions Récursives

Fonctions Récursives

(ou Turing calculables)

Soit M=\left(K,\Sigma,\delta,s \left\{h\right\}\right) une MT et \Sigma_0 \subseteq \Sigma un alphabet et \omega \in\Sigma_{0}^{*} .

Si M s'arrête avec l'entrée \omega ( \left( s,\triangleright \underbrace{\sqcup}\omega\right) ) de sorte que \left( s,\triangleright \underbrace{\sqcup}\omega\right) \vdash_{M}^* \left(h,\triangleright \underbrace{\sqcup}\omega\prime\right) avec \omega\prime\in\Sigma_0^* on dit que \omega\prime est le résultat de sortie de ce calcul, on note \omega\prime=M\left(\omega\right) .

Note: ce mot \omega\prime est unique car M est déterministe.

Soit f une fonction \Sigma_0^* \rightarrow \Sigma_0^* . On dit que M calcule f si et seulement si \forall \omega \in \Sigma_0^* M s'arrête avec \omega en entrée et f\left(\omega\right)=M\left(\omega\right) .

Une fonction est dite récursive (ou récursive au sens de Turing) si et seulement si il existe une MT qui la calcule.

Exemple 1 : retournement

f : \omega \rightarrow \omega^R

Exemple 2 : incrément unaire

Exercice : incrément binaire

Rajouter 1 en binaire dans le sens “habituel”.

Fonctions entières récursives

Soit M=\left(K,\Sigma,\delta, s, \left\{h\right\}\right) une MT telle que

  • \left\{0, 1, ; \right\} \subset \Sigma
  • une fonction f:\mathbb{N}^k \rightarrow \mathbb{N}

On dit que M calcule f si et seulement si \forall \omega_1,\omega_2,\ldots\omega_k \in 0\cup 1\left\{O,1\right\}^* \quad : \quad M\left( \underbrace{\omega_1;\omega_2;\ldots;\omega_k}_{\text{un mot}} \right) = f\left(\underbrace{\omega_1;\omega_2;\ldots;\omega_k}_{\text{base 2}} \right)

Exemples :

  1. + : \mathbb{N}^2 \rightarrow \mathbb{N}
  2. *2 : \mathbb{N} \rightarrow \mathbb{N}
· 2009/11/30 15:01 · Maurice Lanselle

Langages récursivement énumerables

Semi-décidabilité

Semi-décision

Soit

  • M=\left(K, \Sigma, \delta, s,\left\{ h\right\} \right) un MT,
  • \Sigma_0 \subseteq \Sigma\setminus \left\{\sqcup ,\triangleright\right\}
  • et L \subset \Sigma_0^*

On dit que M semi-décide L (ou accepte L) si et seulement si \forall \omega\in\Sigma_0^*, \quad \omega\in L \Leftrightarrow M s'arrête avec l'entrée \omega.

N.B. : \forall \omega\in\Sigma_0^*, \quad \omega\notin L \Leftrightarrow M boucle à l'infini avec l'entrée \omega.

· 2009/11/30 15:29 · Maurice Lanselle
 
m1ilc/c_et_c_3.txt · Dernière modification: 2009/11/30 14:49 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