Vereinigung: Es seien ´L_1´ und ´L_2´ zwei rekursive Sprachen. Dann gibt es Turing-Maschinen ´M_1´ und ´M_2´, die ´L_1´ bzw. ´L_2´ akzeptieren und auf jeder Eingabe stoppen. Wir betrachten nun die Turing-Maschine ´M´, die wie folgt arbeitet: Zuerst schreibt ´M´ eine Kopie des Eingabewortes ´w´ hinter einem Trennzeichen auf das Band. Dann arbeitet ´M´ wie ´M_1´ auf dem ersten ´w´. Kommt ´M_1´ in einen akzeptierenden Zustand, so akzeptiert auch ´M´. Kommt ´M_1´ dagegen in einen ablehnenden Zustand, so arbeitet ´M´ weiter und löscht alles auf dem Band bis auf das zweite ´w´. Auf diesem arbeitet sie nun wie ´M_2´ und akzeptiert genau dann, wenn ´M_2´ akzeptiert. Es ist klar, dass ´M´ zuerst (durch ´M_1´) die Wörter aus ´L_1´ und dann (mittels ´M_2´) die Wörter aus ´L_2´, die nicht in ´L_1´ liegen, akzeptiert. Somit akzeptiert ´M´ die Vereinigung ´L_1 uu L_2´. Die Menge der rekursiven Sprachen ist also unter Vereinigung abgeschlossen.

Durchschnitt: Wir konstruieren zu den rekursiven Sprachen ´L_1´ und ´L_2´ wie oben ´M´ nur mit dem Unterschied, dass ´M´ ablehnt, wenn ´M_1´ ablehnt, und bei Akzeptanz durch ´M_1´ alles löscht, auf dem zweiten ´w´ wie ´M_2´ arbeitet und genau dann akzeptiert, wenn ´M_2´ akzeptiert. Damit akzeptiert ´M´, wenn sowohl ´M_1´ als auch ´M_2´ akzeptieren. Die Menge der rekursiven Sprachen ist also unter Durchschnitt abgeschlossen.

Komplement: Wir haben bereits gezeigt, dass ´L´ rekursiv ist, wenn sowohl ´L´ als auch ´C(L)´ rekursiv aufzählbar sind. Dann sind aber auch ´C(L)´ und ´C(C(L)) = L´ rekursiv-aufzählbar, womit ´C(L)´ als rekursiv nachgewiesen ist. Die Menge der rekursiven Sprachen ist also unter Komplement abgeschlossen.

Produkt: Es sei ´L_1´ und ´L_2´ zwei rekursive Sprachen, die von den auf jeder Eingabe haltenden Turing- Maschinen ´M_1´ bzw. ´M_2´ akzeptiert werden. Wir konstruieren nun die Turing Maschine ´M´, die wie folgt auf der Eingabe ´w = a_1 a_2 … a_n´ arbeitet: ´M´ schreibt ein zusätzliches (Trenn-)Symbol ´$´ vor das Wort (´$w´ steht auf dem Band) und schreibt eine Kopie von ´$w´ hinter ein weiteres Trennsymbol auf das Band. Dann prüft ´M´, ob das Wort vor ´$´ (also ´lambda´) von ´M_1´ akzeptiert wird. Ist dies der Fall, prüft sie mittels ´M_2´, ob das Wort hinter ´$´ (also ´w´) von ´M_2´ akzeptiert wird. Ist dies auch der Fall, wird akzeptiert (denn ´w = lambda w in L_1 L_2´ wegen ´lambda in L_1´ und ´w in L_2´). Wird durch ´M_1´ oder ´M_2´ nicht akzeptiert, so wird alles bis auf die Kopie ´$w´ gelöscht und dann das Trennzeichen um eine Position nach rechts verschoben, was ´a_1 $ a_2 … a_n´ ergibt. Dies wird wieder kopiert und dann geprüft, ob ´a_1´ durch ´M_1´ und ´a_2 … a_n´ durch ´M_2´ akzeptiert wird. Ist beides der Fall, wird akzeptiert (wegen ´a_1 in L_1´ und ´a_2 … a_n in L_2´ ist ´a_1 a_2 … a_n in L_1 L_2´). Im anderen Fall wird das Trennsymbol erneut nach rechts verschoben usw. Man findet also eine Zerlegung ´w = w_1 w_2´ mit ´w_1 in L_1´ und ´w_2 in L_2´ und damit ´w in L_1 L_2´ und akzeptiert oder findet eine solche nicht und lehnt ab, nachdem die Zerlegiung ´w = w lambda´ getestet wurde. Da ´M´ offenbar auf jeder Eingabe stoppt und ´L_1 L_2´ akzeptiert, ist ´L_1 L_2´ rekursiv. Die Menge der rekursiven Sprachen ist also unter Produkt abgeschlossen.