\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ý.

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í.