Rekursiivinen sarja

In laskettavuus teoria , joka on rekursiivinen sarja tai ratkeava joukko on joukko on kokonaislukuja (tai helposti Koodattavat elementtejä kokonaislukuja), jonka karakteristinen funktio on rekursiivinen toiminto siinä mielessä matemaattinen logiikka .

Toisin sanoen joukko on rekursiivinen vain ja vain, jos on olemassa Turingin kone ( tietokoneohjelma ), joka antaa mahdollisuuden määrittää rajallisessa ajassa, onko jokin kokonaisluku vai ei. E{\ displaystyle E} T{\ displaystyle T}E{\ displaystyle E}

∀ei∈EI{\ displaystyle \ forall n \ sisään \ mathbb {N}}
T(ei)=OUMinä jos ei∈E{\ displaystyle T (n) = KYLLÄ \ {\ mbox {si}} \ n \ sisään E}
T(ei)=EIOEI jos ei∉E{\ displaystyle T (n) = EI \ {\ mbox {si}} \ n \ notin E}

Tämän tyyppinen joukko vastaa perusajatus on John R. Myhill , jotka ovat käsitteitä, jotka voidaan määritellä laajasti ja yksiselitteisesti. Rekursiivisesti lueteltavan (ei-rekursiivisen) joukon käsite on pikemminkin rakentava käsite , jonka sisältö tulee ajan mittaan selkeämmäksi ja paremmin ymmärrettäväksi ilman, että sitä olisi koskaan mahdollista määritellä kokonaan.

Määritelmä muodollisen järjestelmän kannalta

Virallisten järjestelmien terminologiassa seuraava määritelmä vastaa:

E{\ displaystyle E}on rekursiivinen vain ja vain, jos on olemassa oikea ja täydellinen muodollinen järjestelmä lausekkeille, joiden muoto on "  on  " ja muoto "  ei ole  ".ei{\ displaystyle n}E{\ displaystyle E}ei{\ displaystyle n}E{\ displaystyle E}

Ominaisuudet

• Joukko A on rekursiivinen vain ja vain, jos A ja sen komplementti ovat rekursiivisesti laskettavissa .
• Jos A ja B ovat rekursiivisia, niin A ∩ B ja A ∪ B ovat rekursiivisia.

Esimerkkejä

Seuraavat sarjat ovat rekursiivisia:

• mikä tahansa äärellinen joukko (tyhjä joukko ∅ on triviaali esimerkki);
• kokonaisluvun kerrannaisjoukko (kokonaisluvut, parilliset luvut jne.);k{\ displaystyle k}
• alkulukujoukko;
• joukko liuoksia tietyn Diofantoksen yhtälö .

Seuraavat sarjat ovat rekursiivisesti lueteltavia, mutta eivät rekursiivisia:

• joukko Diophantine-yhtälöitä, joilla on kokonaislukuinen ratkaisu;
• kaikki pysähtyvät ohjelmat (ohjelmat, jotka eivät toimi loputtomiin): katso ”  Pysäytysongelma  ”.

Tällä hetkellä ei tiedetä, onko alkutermin Syracuse-sekvenssin termien monikerros rekursiivinen jollekin (implisiittinen: kokonaisluku). Syracuse arveluja väittää päinvastaista, mutta vielä tähän päivään undemonstrated. Toisaalta se on rekursiivisesti lueteltavissa määritelmän mukaan. u0=k{\ displaystyle u_ {0} = k}k>0{\ displaystyle k> 0}k{\ displaystyle k}

Huomautuksia ja viitteitä

1. Jean-Paul Delahaye , tiedotus, monimutkaisuus ja mahdollisuus , Hermes Science Publishing,1999( ISBN  2-7462-0026-0 )s. 74.

Katso myös

Aiheeseen liittyvät artikkelit

• Ratkaistavissa oleva ongelma
• Kymmenes Hilbert-ongelma

Ulkoinen linkki

Rekurssikurssi