Slovník pojmů (ve vývoji)


příklad

palindrom

\pojem{Palindrom} je řetězec $w$ stejný při čtení zepředu i zedadu, tj. $w=w^R$.

 

Jazyk palindromů není regulární, je bezkontextový.


Příklad nerekurzivního, rekurzivně spočetného jazyka

Problém zastavení TM (halting problem) je algoritmicky nerozhodnutelný.

Neexistuje algoritmus, který by pro daný kód TM a daný vstup rozhodl, zda se TM zastaví.