Moja lekcja

 0    16 schede    szymonklempert
inizia ad imparare

Scarica mp3 Stampa Gioca Testa il tuo livello
 
Domanda Risposta
{<M>: M jest maszyna Turinga oraz istnieje taki ’input’, na ktorym M zatrzymuje sie w nie wiecej niz |M| krokach}
inizia ad imparare
R
{<M>: M jest maszyn¸a Turinga oraz |L(M)| ≤ 3}
inizia ad imparare
non-RE
{<M>: M jest maszyna Turinga oraz |L(M)| ≥ 3}
inizia ad imparare
RE | non-R
{<M>: M jest maszyna Turinga oraz L(M) jest skonczony}
inizia ad imparare
non-RE
{<M>: M jest maszyna Turinga oraz L(M) jest nieskonczony}
inizia ad imparare
non-RE
{<M>: M jest maszyna Turinga oraz L(M) jest przeliczalny}
inizia ad imparare
R
{<M>: M jest maszyna Turinga oraz L(M) jest nieprzeliczalny}.
inizia ad imparare
R
{<M>: M jest jedyna maszyna Turinga akceptujaca L(M)}
inizia ad imparare
R
{<M1>: M1 jest taka MT, dla ktorej istnieja takie maszyny M2 oraz M3, by L(M1) ⊂ L(M3) U L(M3)}
inizia ad imparare
R
{<M1, M2>: M1 oraz M2 sa MT, dla ktorych ε ∈ L(M1) ∩ L(M2)}.
inizia ad imparare
RE | non-R
{<M1, M2>: M1 oraz M2 sa MT, dla ktorych ε ∈ L(M1) U L(M2)}.
inizia ad imparare
RE | non-R
{<M1, M2>: M1 oraz M2 sa takimi MT, dla ktorych ε ∈ L(M1)/L(M2)}
inizia ad imparare
non-RE
= {<M>: ∃x: |x| ≡6 2 oraz x ∈ L(M)}
inizia ad imparare
RE | non-R - Rice
{<M>: M jest MT oraz M0 zatrzymujaca sie dla kazdego slowa ma te wlasnosc, ze M0 ∈ L(M)}
inizia ad imparare
RE | non-R - Rice
= {<M>: M jest MT oraz istnieje taki ’input’, na ktorym M zatrzymuje sie w nie wiecej niz 2020 krokow.}
inizia ad imparare
R
= {<M>: M jest MT oraz istnieje taka MT M', dla ktorej L(M) = L(M')}
inizia ad imparare
R
Crea delle schede
English

Devi essere accedere per pubblicare un commento.