Agora estou bastante confiante em como transformar algo em uma máquina de Turing. Agora, minha pergunta é como você converte a MT em um complemento de uma máquina de Turing. Pelo que me lembro no Autômato Finito, complementando-o, você transformaria um estado inicial em um estado final; também, se você tiver um estado final, o transformaria em um estado inicial ... Como você complementaria uma Máquina de Turing?
Por exemplo, aqui eu tenho uma TM simples de um Palíndromo e quero um Palíndromo '
Respostas:
Você não pode fazer isso em geral.
Isso tornaria o complemento do seu idioma semi-decidível, como o próprio idioma. Portanto, ambos seriam decididos executando as duas máquinas em paralelo.
Obviamente, isso diz respeito apenas ao caso de idiomas semidecidíveis para os quais a MT nem sempre pára por palavras que não estão no idioma.
Se você tiver um idioma decidível para o qual a MT sempre interrompa com um sim ou um não, basta trocar o sim e o não.
No entanto, existem algumas precauções a serem tomadas:
compatibilidade de configurações de aceitação e não aceitação
Dependendo da definição escolhida de Máquinas de Turing, aceitar e interromper configurações de não aceitação pode não ser compatível e, portanto, não ser intercambiável. Se for permitido que um estado de aceitação tenha transições que poderiam ser usadas, torná-lo um estado normal pode apenas fazer a computação continuar, em vez de parar sem aceitar. Portanto, algumas precauções bastante simples devem ser tomadas com relação a como a aceitação e a rejeição são identificadas e como trocá-las.
máquinas não determinísticas
Máquinas não determinísticas são anti-gerentes. Quando um gerente diz "não", significa não, e quando ele diz "sim", significa "talvez".
Máquinas não determinísticas fazem o oposto: quando dizem "sim" significa "sim" e quando parecem dizer "não" (interrompendo uma configuração que não aceita), significa "talvez". A razão pela qual isso significa talvez é que ela pode ter respondido sim com uma escolha não determinística diferente de algumas transições. Na verdade, deve-se supor com mais precisão que os autômatos não determinísticos nunca dêem uma resposta negativa. É conveniente para os autômatos determinísticos, mas não significa nada para os não determinísticos. Também é "talvez" quando eles não terminam, por dois motivos: (1) outra opção de transição pode ter produzido aceitação e (2) você não pode afirmar a não aceitação, pois a computação pode continuar.
Portanto, não é fácil complementar uma linguagem reconhecida por um dispositivo não determinístico ou sem interrupção. Você não pode simplesmente trocar "sim" e "não", pois só possui "sim" e "talvez". Você só obteria uma máquina gerencial respondendo apenas "não" ou "talvez", não reconhecida pela Automata Theory Union. Os autômatos devem aceitar terminando e respondendo "sim" sem ambiguidade se a palavra a ser reconhecida estiver no idioma. Ser capaz de responder não em alguns casos é apenas um bônus de máquinas determinísticas, quando gentis o suficiente para parar.
Portanto, você deve primeiro converter sua máquina em uma determinística. Em seguida, você pode trocar as configurações de aceitação e rejeição (com o devido respeito ao ponto anterior acima), assumindo ainda que a máquina sempre pare.
Para obter o complemento de um conjunto regular, é conveniente primeiro comprar um DFA que o reconheça.
Uma máquina de Turing sempre pode ser transformada em uma determinística, mas pode não parar, deixando espaço para "talvez". Portanto, nem sempre é possível complementar um idioma reconhecido por uma máquina de Turing, conforme declarado acima. Mas é possível para uma MT (determinada) que sempre pare com uma resposta sim / não.
fonte