section_heading: Gramatike neograničenih produkcija i Turingovi strojevi
paragraph_text: Lako se vidi da će ovaj Turingov stroj generirati sve i samo rečenične oblike gramatike <math>G</math> na drugoj traci nakon što je posljednji korak izvršen proizvoljan broj puta, i time jezik <math>L(G)</math> mora biti rekurzivno prebrojiv.