→ Moja Lekcja → Start Learning / Download MP3 Flashcards

start learning

Question		Answer
{<M>: M jest maszyna Turinga oraz istnieje taki ’input’, na ktorym M zatrzymuje sie w nie wiecej niz \|M\| krokach} start learning		R
{<M>: M jest maszyn¸a Turinga oraz \|L(M)\| ≤ 3} start learning		non-RE
{<M>: M jest maszyna Turinga oraz \|L(M)\| ≥ 3} start learning		RE \| non-R
{<M>: M jest maszyna Turinga oraz L(M) jest skonczony} start learning		non-RE
{<M>: M jest maszyna Turinga oraz L(M) jest nieskonczony} start learning		non-RE
{<M>: M jest maszyna Turinga oraz L(M) jest przeliczalny} start learning		R
{<M>: M jest maszyna Turinga oraz L(M) jest nieprzeliczalny}. start learning		R
{<M>: M jest jedyna maszyna Turinga akceptujaca L(M)} start learning		R
{<M1>: M1 jest taka MT, dla ktorej istnieja takie maszyny M2 oraz M3, by L(M1) ⊂ L(M3) U L(M3)} start learning		R
{<M1, M2>: M1 oraz M2 sa MT, dla ktorych ε ∈ L(M1) ∩ L(M2)}. start learning		RE \| non-R
{<M1, M2>: M1 oraz M2 sa MT, dla ktorych ε ∈ L(M1) U L(M2)}. start learning		RE \| non-R
{<M1, M2>: M1 oraz M2 sa takimi MT, dla ktorych ε ∈ L(M1)/L(M2)} start learning		non-RE
= {<M>: ∃x: \|x\| ≡6 2 oraz x ∈ L(M)} start learning		RE \| non-R - Rice
{<M>: M jest MT oraz M0 zatrzymujaca sie dla kazdego slowa ma te wlasnosc, ze M0 ∈ L(M)} start learning		RE \| non-R - Rice
= {<M>: M jest MT oraz istnieje taki ’input’, na ktorym M zatrzymuje sie w nie wiecej niz 2020 krokow.} start learning		R
= {<M>: M jest MT oraz istnieje taka MT M', dla ktorej L(M) = L(M')} start learning		R

Moja lekcja