Positieve sluitingseigenschappen (gesloten onder deze bewerkingen):

* Unie: Als L1 en L2 Turing-herkenbaar zijn, dan is L1 ∪ L2 ook Turing-herkenbaar. U kunt beide Turing-machines voor L1 en L2 parallel simuleren. Als een van beide accepteert, accepteert de gecombineerde machine.

* Aaneenschakeling: Als L1 en L2 Turing-herkenbaar zijn, dan is L1L2 ook Turing-herkenbaar. Dit is een beetje lastiger. U kunt de invoerreeks op niet-deterministische wijze in twee delen splitsen en vervolgens de Turing-machines voor L1 en L2 op die delen laten draaien. Als beide accepteren, accepteert de gecombineerde machine.

* Kleene Star: Als L Turing-herkenbaar is, dan is L* ook Turing-herkenbaar. Net als bij aaneenschakeling kunt u de invoertekenreeks op niet-deterministische wijze in nul of meer delen splitsen en testen of elk deel in L staat.

* Omkering: Als L Turing-herkenbaar is, dan is L ^R (de omkering van L) is ook Turing-herkenbaar. Een Turingmachine kan de invoerreeks eenvoudig omkeren en vervolgens de Turingmachine voor L op de omgekeerde reeks uitvoeren.

Negatieve sluitingseigenschappen (niet gesloten onder deze bewerkingen):

* Kruispunt: Turing-herkenbare talen zijn *niet* gesloten onder intersectie. Dit betekent dat als L1 en L2 Turing-herkenbaar zijn, L1 ∩ L2 niet *noodzakelijkerwijs* Turing-herkenbaar is. Als echter *zowel* L1 als L2 Turing-*beslisbaar* zijn, dan is L1 ∩ L2 Turing-beslisbaar (en dus ook Turing-herkenbaar).

* Aanvulling: Turing-herkenbare talen zijn *niet* gesloten onder complementatie. Als L Turing-herkenbaar is, is ¬L (het complement van L) *niet noodzakelijk* Turing-herkenbaar.

* Een taal L is Turing-beslisbaar (recursief) dan en slechts dan als zowel L als ¬L Turing-herkenbaar zijn (recursief opsombaar). Dit is een cruciale verbinding tussen herkenbare en beslisbare talen.

Samengevat:

| Operatie | Gesloten? | Uitleg |

|---------------|---------|------------------------------ -------------------------------------------------------|

| Unie | Ja | Simuleer beide machines parallel, accepteer als een van beide accepteert. |

| Aaneenschakeling | Ja | Splits de invoer niet-deterministisch en test elk onderdeel. |

| Kleene Ster | Ja | Splits invoer op niet-deterministische wijze op in meerdere delen en test elk deel. |

| Omkering | Ja | Keer de invoer om en voer het TM uit. |

| Kruispunt | Nee | Kan mislukken. Vereist dat beide talen beslisbaar zijn voor afsluiting. |

| Aanvulling | Nee | Het complement van een Turing-herkenbare taal is niet altijd Turing-herkenbaar. |

Waarom zijn intersecties en complementaties niet gesloten?

Het probleem komt voort uit het feit dat Turing-machines voor Turing-herkenbare talen voor altijd in een lus kunnen blijven staan.

* Kruispunt: Als een van de machines een bepaalde invoer doorloopt, kan de gecombineerde machine ook een lus maken, zelfs als de andere machine uiteindelijk zou afwijzen (wat betekent dat de invoer *niet* op het kruispunt ligt). Je hebt een manier nodig om te weten *wanneer* je moet stoppen met wachten op een machine die mogelijk voor altijd in een lus blijft staan.

* Aanvulling: Een Turing-machine voor L accepteert een invoer, wijst deze af of herhaalt deze. Om het complement ¬L te herkennen, moet je alle strings *verwerpen* die door L zijn geaccepteerd en *accepteren* alle strings die door L zijn afgewezen *of doorgelust*. Je kunt niet op betrouwbare wijze onderscheid maken tussen een machine die *uiteindelijk* zal afwijzen en een machine die voor altijd in een lus blijft. Je zou op de een of andere manier moeten weten *wanneer* een machine een lus gaat maken, wat over het algemeen onmogelijk is.

Voorbeeld van niet-afsluiting onder complementatie:

Denk eens aan het Halting-probleem, dat Turing-herkenbaar is (een Turing-machine kan een andere Turing-machine simuleren en accepteren als deze stopt). Het complement van het Halting-probleem is *niet* Turing-herkenbaar. Als dat zo zou zijn, zou het Halting-probleem Turing-beslisbaar zijn (aangezien zowel het Halting-probleem als het complement ervan Turing-herkenbaar zouden zijn), waarvan we weten dat het onjuist is.