Muul juhul ei peatu. DEF: Hulka (keelt), millel leidub karakteristlik Turingi masin, nimetatakse lahenduvaks ehk rekursiivseks. DEF: Hulka (keelt), millel leidub genereeriv Turingi masin, nimetatakse rekursiivselt loenduvaks ehk genereeritavaks. Lemma: Iga lahenduv hulk on rekursiivselt loenduv. T: Igal lahenduva hulga karakteristlikku masinat saab tesendada nii, et ta jääks olekusse qr jõudmise asemel tsüklisse ehk muutuks genereerivaks masinaks. Registermasin sisaldab registreid R1… (sisuks naturaalarv) ja märgendeid N1… Operaatorid on INC (+1), DEC (-1), CLR (nullimine), R → R (omastad ühe väärtuse teisele), JMP Na (go to N), JMP Nb (go to N+1), R JMP Na (kui R=0…), R JMP Nb, CONTINUE (ei tee midagi). Registermälu kasutab suvapöördusmälu RAM ehk on võimeline iga oma registrini pöörduma võrdse ajaga. Mälu ja registri suurus on piiramatud.
d). Leidnud sobivad rajatingimused, avaldamegi rekurrentsi kujul .
[15]. Rekurrentsete võrrandite lahendamine genereerivate funktsioonide meetodil.
(Ainus küsimus, millest ei saa mitte sittagi aru).
Olgu arvujada esitatud rekurrentse seose abil.
a). Esmalt täiendan jada elementidega g-1 = g-2 = ... = 0
b). Korrutan rekurrentse võrrandi mõlemaid pooli suurusega zn ning summeerin üle
kõigi n'i väärtuste. Võrduse vasakul poolel olevat summat nimetatakse jada
annaabi.ee 
