Set recursiv

În teoria calculabilității un set recursiv (sau set decisiv ) este intuitiv un set de numere naturale , deci este posibil să se construiască un algoritm care într-un timp finit (dar a priori nedeterminat) este capabil, având în vedere orice număr natural, să stabiliți dacă aparține sau nu întregului.

Mai formal, se spune că un set este recursiv dacă funcția sa caracteristică este recursivă .

Definiție formală

Un set $S.$ ${\ displaystyle S}$ $S.$ , subset de natural ( $S\subseteq \mathbb {N}$ ${\ displaystyle S \ subseteq \ mathbb {N}}$ ${\ displaystyle S \ subseteq \ mathbb {N}}$ ), se spune că este recursiv dacă funcția sa de indicator

\mathbf {1} _{S}\colon \mathbb {N} \to \left\{0,1\right\}

{\ displaystyle \ mathbf {1} _ {S} \ colon \ mathbb {N} \ to \ left \ {0,1 \ right \}}

{\ displaystyle \ mathbf {1} _ {S} \ colon \ mathbb {N} \ to \ left \ {0,1 \ right \}}

cu

\mathbf {1} _{S}(x)=\left\{{\begin{matrix}1&{\mbox{se}}\ x\in S\\0&{\mbox{se}}\ x\notin S\end{matrix}}\right.

{\ displaystyle \ mathbf {1} _ {S} (x) = \ left \ {{\ begin {matrix} 1 & {\ mbox {se}} \ x \ în S \\ 0 & {\ mbox {se} } \ x \ notin S \ end {matrix}} \ right.}

{\ displaystyle \ mathbf {1} _ {S} (x) = \ left \ {{\ begin {matrix} 1 & {\ mbox {se}} \ x \ în S \\ 0 & {\ mbox {se} } \ x \ notin S \ end {matrix}} \ right.}

este recursiv și total (totalitatea este implicită în notația pe care am dat-o, care prevede că, indiferent de intrare, ieșirea este întotdeauna $0$ ${\ displaystyle 0}$ ${\ displaystyle 0}$ sau $1$ ${\ displaystyle 1}$ $1$ ).

Proprietate

Complement împreună

Dacă un set $S.$ ${\ displaystyle S}$ $S.$ este recursiv, deci și complementul său este ${\bar {S}}=\mathbb {N} -S$ ${\ displaystyle {\ bar {S}} = \ mathbb {N} -S}$ ${\ bar {S}} = {\ mathbb {N}} - S$ (ne gândim $\mathbb {N}$ ${\ displaystyle \ mathbb {N}}$ $\ mathbb {N}$ ca univers) este recursiv.

Unire și intersecție

De sine $LA$ ${\ displaystyle A}$ $LA$ Și $B.$ ${\ displaystyle B}$ $B.$ sunt seturi recursive, apoi și $A\cap B$ ${\ displaystyle A \ cap B}$ $A \ cap B$ Și $A\cup B$ ${\ displaystyle A \ cup B}$ $A \ cup B$ sunt recursive.

Recursiv enumerabil

Întregul $LA$ ${\ displaystyle A}$ $LA$ este recursiv dacă și numai dacă $LA$ ${\ displaystyle A}$ $LA$ și complementul său ${\bar {A}}$ ${\ displaystyle {\ bar {A}}}$ ${\ displaystyle {\ bar {A}}}$ ambele sunt recursiv enumerabile (Teorema lui Post).

Funcția de imagine recursivă totală

Dacă întregul $LA$ ${\ displaystyle A}$ $LA$ este un set recursiv și este, de asemenea, domeniul unei funcții $f:A\to B$ ${\ displaystyle f: A \ to B}$ ${\ displaystyle f: A \ to B}$ funcție recursivă și totală , apoi și $B.$ ${\ displaystyle B}$ $B.$ este recursiv.

Exemple de seturi recursive

setul gol $\varnothing$ ${\ displaystyle \ varnothing}$ $\ varnothing$
ansamblul numerelor naturale $\mathbb {N}$ ${\ displaystyle \ mathbb {N}}$ $\ mathbb {N}$
orice subset finit de $\mathbb {N}$ ${\ displaystyle \ mathbb {N}}$ $\ mathbb {N}$
mulțimea numerelor prime , mulțimea numerelor egale (și deci și numerele impare )
un limbaj recursiv este un set recursiv în setul tuturor cuvintelor posibile din alfabetul limbajului formal .

Limitări: seturi nerecursive

Vă reamintim că de fiecare dată când folosim funcția $\varphi$ ${\ displaystyle \ varphi}$ $\ varphi$ , ne referim la o enumerare a funcțiilor recursive în care funcția $\varphi _{i}$ ${\ displaystyle \ varphi _ {i}}$ $\ varphi _ {i}$ Corespunde la $i+1$ ${\ displaystyle i + 1}$ $i + 1$ -funcția recursivă. Adică, a spus $f$ ${\ displaystyle f}$ $f$ Acolo $i+1$ ${\ displaystyle i + 1}$ $i + 1$ -funcția recursivă, avem:

\varphi _{i}(y)=f(y)

{\ displaystyle \ varphi _ {i} (y) = f (y)}

\ varphi _ {i} (y) = f (y)

Problema opririi

Întregul

{\mathit {K}}=\lbrace \left\langle x,y\right\rangle |\varphi _{x}(y){\mbox{ è definita}}\rbrace

{\ displaystyle {\ mathit {K}} = \ lbrace \ left \ langle x, y \ right \ rangle | \ varphi _ {x} (y) {\ mbox {is defined}} \ rbrace}

{\ displaystyle {\ mathit {K}} = \ lbrace \ left \ langle x, y \ right \ rangle | \ varphi _ {x} (y) {\ mbox {is defined}} \ rbrace}

nu este recursiv ci recursiv enumerabil .

Set de seturi recursive

Setul care conține toate seturile recursive nu este recursiv (nici nu este recursiv enumerabil ).

Alte seturi nerecursive

Multe dintre următoarele pot fi urmărite înapoi la problema opririi, adică pentru a dovedi că nu sunt recursive, se poate folosi tehnica de reducere absurdă , pentru a arăta că dacă au fost recursive atunci și setul ${\mathit {K}}$ ${\ displaystyle {\ mathit {K}}}$ ${\ displaystyle {\ mathit {K}}}$ ceea ce reprezintă problema opririi ar fi.

$\lbrace x|\varphi _{x}(x){\mbox{ è definita}}\rbrace$ ${\ displaystyle \ lbrace x | \ varphi _ {x} (x) {\ mbox {este definit}} \ rbrace}$ ${\ displaystyle \ lbrace x | \ varphi _ {x} (x) {\ mbox {este definit}} \ rbrace}$
$\lbrace x|\varphi _{x}(c){\mbox{ è definita}}\rbrace$ ${\ displaystyle \ lbrace x | \ varphi _ {x} (c) {\ mbox {este definit}} \ rbrace}$ ${\ displaystyle \ lbrace x | \ varphi _ {x} (c) {\ mbox {este definit}} \ rbrace}$ , unde este $c$ ${\ displaystyle c}$ $c$ este orice constantă
$\lbrace x|\varphi _{x}{\mbox{ è costante}}\rbrace$ ${\ displaystyle \ lbrace x | \ varphi _ {x} {\ mbox {este constant}} \ rbrace}$ ${\ displaystyle \ lbrace x | \ varphi _ {x} {\ mbox {este constant}} \ rbrace}$ (indecidabilitatea constanței unei funcții)
$\lbrace \left\langle x,y,z\right\rangle |\varphi _{x}(y)=z\rbrace$ ${\ displaystyle \ lbrace \ left \ langle x, y, z \ right \ rangle | \ varphi _ {x} (y) = z \ rbrace}$ $\ lbrace \ left \ langle x, y, z \ right \ rangle | \ varphi _ {x} (y) = z \ rbrace$ (indecidabilitatea valorii unei funcții)
$\lbrace \left\langle x,y\right\rangle |\varphi _{x}=\varphi _{y}\rbrace$ ${\ displaystyle \ lbrace \ left \ langle x, y \ right \ rangle | \ varphi _ {x} = \ varphi _ {y} \ rbrace}$ ${\ displaystyle \ lbrace \ left \ langle x, y \ right \ rangle | \ varphi _ {x} = \ varphi _ {y} \ rbrace}$ (indecidibilitatea egalității a două funcții)
de sine $X$ ${\ displaystyle x}$ $X$ reprezintă o gramatică fără context $d_{x}$ ${\ displaystyle d_ {x}}$ ${\ displaystyle d_ {x}}$ , $\lbrace x|d_{x}{\mbox{ è ambigua}}\rbrace$ ${\ displaystyle \ lbrace x | d_ {x} {\ mbox {este ambiguă}} \ rbrace}$ ${\ displaystyle \ lbrace x | d_ {x} {\ mbox {este ambiguă}} \ rbrace}$ (problema de a decide dacă o gramatică fără context este ambiguă)
ansamblul ecuațiilor diofantine care admit rădăcini întregi

Elemente conexe

Portalul de matematică : accesați intrările Wikipedia care se ocupă de matematică