Rekurzív készlet

A Kiszámolhatóság elméletben , egy rekurzív halmaz vagy eldönthető készlet egy sor a egész számok (vagy könnyen kódolható elemek egész szám), amelynek karakterisztikus függvénye egy rekurzív függvény abban az értelemben, a matematikai logika .

Más szavakkal, egy halmaz akkor és csak akkor rekurzív, ha létezik egy Turing-gép ( számítógépes program ), amely véges idő alatt meg tudja határozni, hogy van-e egész szám vagy sem. E{\ displaystyle E} T{\ displaystyle T}E{\ displaystyle E}

∀nem∈NEM{\ displaystyle \ forall n \ in \ mathbb {N}}
T(nem)=OUén ha nem∈E{\ displaystyle T (n) = IGEN \ {\ mbox {si}} \ n \ E-ben}
T(nem)=NEMONEM ha nem∉E{\ displaystyle T (n) = NEM \ {\ mbox {si}} \ n \ notin E}

Ez a halmaztípus megfelel John R. Myhill tényleges koncepciójának , ezek azok a fogalmak, amelyek széleskörűen és egyértelműen meghatározhatók. A rekurzív módon megszámlálható (nem rekurzív) halmaz fogalma inkább konstruktív fogalom , amelynek tartalma az idő múlásával egyre világosabbá válik, és egyre jobban érthető anélkül, hogy valaha is lehetne teljesen meghatározni.

Meghatározás egy formális rendszer szempontjából

A formális rendszerek terminológiájában a következő meghatározás egyenértékű:

E{\ displaystyle E}rekurzív akkor és csak akkor, ha van egy korrekt és teljes hivatalos rendszerrel nyilatkozatok formájában „  van  ” és a forma „  nem  ”.nem{\ displaystyle n}E{\ displaystyle E}nem{\ displaystyle n}E{\ displaystyle E}

Tulajdonságok

• Egy sor egy rekurzív akkor, ha A és komplement vannak rekurzívan felsorolható .
• Ha A és B rekurzív, akkor A ∩ B és A ∪ B rekurzív.

Példák

A következő halmazok rekurzívak:

• bármely véges halmaz (az set üres halmaz triviális példa);
• egy egész szám többszörösének halmaza (egész számok, páros számok stb.);k{\ displaystyle k}
• a prímszámok halmaza;
• adott Diophantine-egyenlet megoldási halmaza .

A következő halmazok rekurzívan felsorolhatók, de nem rekurzívak:

• a Diophantine egyenletek halmaza, amelyeknek egész megoldása van;
• az összes program, amely leáll (azok a programok, amelyek nem futnak a végtelenségig): lásd: „  A probléma leállítása  ”.

Ez jelenleg nem ismert, hogy a multihalmazt a feltételeket a Syracuse szekvenciája eredeti időtartam rekurzív számára bármilyen (vélelmezett: egész szám). A syracusei sejtés az ellenkezőjét állítja, de a mai napig nem mutat be. Másrészt definíció szerint rekurzív módon felsorolható. u0=k{\ displaystyle u_ {0} = k}k>0{\ displaystyle k> 0}k{\ displaystyle k}

Megjegyzések és hivatkozások

1. Jean-Paul Delahaye , Információ, összetettség és esély , Hermes Science Publishing,1999( ISBN  2-7462-0026-0 )o. 74.

Lásd is

Kapcsolódó cikkek

• Dönthető probléma
• Tizedik Hilbert-probléma

Külső hivatkozás

Rekurziós tanfolyam