Turing-igenkännbara språk, även kända som rekursivt ansökliga språk, har följande stängningsegenskaper:
Positiva stängningsegenskaper (stängda under dessa operationer):
* Union: Om L1 och L2 är Turing-igenkännbara, är L1 ∪ L2 också turing-igenkännande. Du kan simulera båda Turing -maskinerna för L1 och L2 parallellt. Om antingen accepterar accepterar den kombinerade maskinen.
* Concatenation: Om L1 och L2 är Turing-igenkännbara, är L1L2 också turing-igenkännande. Det här är lite svårare. Du kan icke-deterministiskt dela in ingångssträngen i två delar och sedan köra Turing-maskinerna för L1 och L2 på dessa delar. Om båda accepterar, accepterar den kombinerade maskinen.
* Kleene Star: Om L är Turing-igenkännande, är L* också Turing-igenkännande. I likhet med sammankoppling kan du icke-deterministiskt dela in ingångssträngen i noll eller fler delar och testa om varje del är i L.
* reversering: Om L är turing-igenkännande, så l
r
(Vändningen av L) är också turing-igenkännande. En Turing -maskin kan enkelt vända ingångssträngen och sedan köra Turing -maskinen för L på den omvända strängen.
Negativa stängningsegenskaper (inte stängda under dessa operationer):
* korsning: Turing-igenkännbara språk är * inte * stängda under korsningen. Detta innebär att om L1 och L2 är turing-igenkännbara, är L1 ∩ L2 inte * nödvändigtvis * Turing-igenkännande. Men om*både*l1 och l2 är turing-*avgörande*, är l1 ∩ l2 turing-avtagbar (och därmed också turing-igenkännande).
* komplement: Turing-igenkännbara språk är * inte * stängda under komplementering. Om L är Turing-igenkännande är ¬l (komplementet för L) * inte nödvändigtvis * Turing-igenkännande.
* Ett språk L är turing-avtagbart (rekursivt) om och bara om både L och ¬l är turing-igenkännbara (rekursivt är faktiskt). Detta är en avgörande koppling mellan igenkännbara och avgörande språk.
Sammanfattningsvis:
| Operation | Stängd? | Förklaring |
| ----------------- | --------- | --------------------------------------------------------------------------------------------------- |
| Union | Ja | Simulera båda maskinerna parallellt, acceptera om antingen accepterar. |
| CONCATENATION | Ja | Icke-deterministiskt delade inmatning och testa varje del. |
| Kleene Star | Ja | Icke-deterministiskt delade inmatning i flera delar och testar varje del. |
| Reversering | Ja | Vänd ingången och kör TM. |
| Korsning | Nej | Kan misslyckas. Kräver att båda språken är avgörande för stängning. |
| Komplementering | Nej | Komplementet för ett Turing-igenkännligt språk är inte alltid Turing-igenkännande. |
Varför stängs inte skärningspunkten och kompletteringen?
Frågan härrör från det faktum att Turing-maskiner för Turing-igenkännbara språk kan slingra för alltid.
* korsning: Om en av maskinerna slingrar på en viss ingång, kan den kombinerade maskinen också slinga, även om den andra maskinen så småningom skulle avvisa (vilket betyder att ingången är * inte * i korsningen). Du behöver ett sätt att veta * när * för att sluta vänta på en maskin som kan slingra för alltid.
* komplement: En Turing -maskin för L antingen accepterar, avvisar eller slingor på en ingång. För att känna igen komplementet ¬l måste du * avvisa * alla strängar som accepteras av l och * acceptera * alla strängar avvisade * eller slingras på * av L. Du kan inte på ett tillförlitligt sätt skilja mellan en maskin som * kommer att * avvisa så småningom och en som kommer att slinga för evigt. Du skulle behöva kunna på något sätt veta * när * en maskin kommer att slinga, vilket i allmänhet är omöjligt.
Exempel Demonstrerar icke-stängning under komplementering:
Tänk på stoppproblemet, som är Turing-igenkännande (en Turing-maskin kan simulera en annan Turing-maskin och acceptera om den stoppar). Komplementet för stoppproblemet är * inte * Turing-igenkännande. Om det var, skulle stoppproblemet vara turing-avkoppbart (eftersom både stoppproblemet och dess komplement skulle vara Turing-igenkännande), som vi vet är falskt.
