As línguas reconhecíveis por Turing, também conhecidas como idiomas recursivamente enumeráveis, têm as seguintes propriedades de fechamento:
Propriedades positivas de fechamento (fechadas sob essas operações): *
União: Se L1 e L2 forem reconhecíveis por Turing, L1 ∪ L2 também é reconhecível por Turing. Você pode simular as duas máquinas de Turing para L1 e L2 em paralelo. Se aceita, a máquina combinada aceita.
*
Concatenação: Se L1 e L2 forem reconhecíveis por Turing, o L1L2 também é reconhecível por Turing. Isso é um pouco mais complicado. Você pode dividir a sequência de entrada não deterministicamente em duas partes e, em seguida, executar as máquinas Turing para L1 e L2 nessas partes. Se ambos aceitarem, a máquina combinada aceita.
*
estrela de Kleene: Se L for reconhecível com Turing, então L* também é reconhecível por Turing. Semelhante à concatenação, você pode dividir a string de entrada não deterministicamente em zero ou mais peças e testar se cada parte estiver em L.
*
reversão: Se L é reconhecível por Turing, então eu r
(A reversão de L) também é reconhecível por Turing. Uma máquina de Turing pode facilmente reverter a sequência de entrada e, em seguida, executar a máquina Turing para L na sequência invertida.
Propriedades de fechamento negativo (não fechadas sob essas operações): *
Interseção: Os idiomas reconhecíveis por Turing não estão * fechados sob interseção. Isso significa que, se L1 e L2 forem reconhecíveis por Turing, L1 ∩ L2 não é * necessariamente * reconhecível por Turing. No entanto, se*ambos*L1 e L2 forem turing-*decidíveis*, então L1 ∩ L2 é decidível (e, portanto, também reconhecível por Turing).
*
Complementação: Os idiomas reconhecíveis por Turing não estão * fechados sob complementação. Se L for reconhecível com Turing, ¬l (o complemento de L) não é necessariamente * reconhecível.
* Um idioma L é decidível (recursivo) se e somente se L e ¬l forem reconhecíveis com Turing (recursivamente enumeráveis). Esta é uma conexão crucial entre idiomas reconhecíveis e decidíveis.
em resumo: | Operação | Fechado? | Explicação |
| -----------
| Union | Sim | Simule as duas máquinas em paralelo, aceite se aceitar. |
| Concatenação | Sim | Dividir não dividir a entrada e testar cada parte. |
| Kleene Star | Sim | Dividir não dividir a entrada em várias partes e testar cada parte. |
| Reversão | Sim | Inverta a entrada e execute a TM. |
| Interseção | Não | Pode falhar. Requer que ambos os idiomas sejam decidíveis para o fechamento. |
| Complementação | Não | O complemento de uma linguagem reconhecível por Turing nem sempre é reconhecível por Turing. |
Por que a interseção e a complementação não estão fechadas? A questão decorre do fato de que as máquinas de Turing para idiomas reconhecíveis por Turing podem fazer um loop para sempre.
*
Interseção: Se uma das máquinas loop em uma entrada específica, a máquina combinada também poderá fazer um loop, mesmo que a outra máquina acabasse rejeitando (o que significa que a entrada * não * não * na interseção). Você precisa de uma maneira de saber * quando * parar de esperar por uma máquina que possa estar fazendo um loop para sempre.
*
Complementação: Uma máquina de Turing para L aceita, rejeita ou loops em uma entrada. Para reconhecer o complemento, você precisa * rejeitar * todas as cordas aceitas por l e * aceitar * todas as cordas rejeitadas * ou loopadas * por L. Você não pode distinguir de forma confiável entre uma máquina que * rejeitará eventualmente e que fará um loop para sempre. Você precisaria saber de alguma forma * quando * uma máquina vai fazer um loop, o que geralmente é impossível.
Exemplo demonstrando o não fechamento sob complementação: Considere o problema de interrupção, que é reconhecível por Turing (uma máquina de Turing pode simular outra máquina de Turing e aceitar se ele interromper). O complemento do problema de interrupção é * não * reconhecível. Se fosse, o problema de parada seria decidível (uma vez que o problema de parada e seu complemento seriam reconhecíveis por Turing), o que sabemos que é falso.
