Uma máquina de Turing pode decidir o idioma

11

Seja Existe uma máquina de Turing R que decide (não quero dizer, reconhece) o idioma ?L

L={MM is a Turing Machine and L(M)=}.

L

Parece que a mesma técnica usada para mostrar que deve funcionar aqui também.{AA is a DFA and L(A)=}

msn
fonte
1
O que você tentou? Por exemplo, você pode pensar em um DFA para o idioma vazio? Lembre-se de que os DFAs podem ser considerados TMs muito limitados.
Shaull 29/03/2013
1
Certo. No estado inicial, mova para o estado "parar de rejeitar", independentemente do que está na fita de entrada. Isso aceita explicitamente todas as seqüências de caracteres no idioma e rejeita todas as seqüências de caracteres que não estão no idioma.
Patrick87
8
@mahdisaeedi: Esta última é uma pergunta totalmente diferente! Você está perguntando se é decidível para decidir se um determinado TM reconhece a linguagem vazia - e a resposta é não, ver Teorema de Rice
Shaull

Respostas:

9

Marcando, você provavelmente quer dizer análise de acessibilidade - procurando um caminho do estado inicial para o estado de aceitação. De fato, o idioma de um DFA está vazio se não houver esse caminho.

Vamos começar com um exemplo de por que isso falha nas TMs. Considere uma TM que, em , ignore sua entrada, mas grave na fita, mova a cabeça para a direita e vá para o estado ; depois, em , novamente ignore a entrada, escreve , move a cabeça para a esquerda e passa para q 2 . No q 2 , se lê a , então escreve a , move a cabeça para a direita e volta para q 1 . a q 1 q 1 aq0aq1q1aq2q2aaq1

Ou seja, a máquina apenas escreve e suplentes entre dois estados ( q 1 e q 2 ) e tem sempre duas adjacentes um é na fita.aq1q2a

Agora adicionamos uma transição de que, ao ler b, passa para um estado de aceitação e pára.q2b

O idioma desta máquina está vazio. De fato, a execução sempre fica presa no loop e nunca chega ao estado de aceitação. No entanto, existe um caminho de estado para um estado de aceitação. Então, o que deu errado?q1q2

Bem, intuitivamente, o `` estado '' de uma TM não é informativo o suficiente para descrever a continuação da execução. Para ter todas as informações, você precisa da configuração da TM, que inclui o estado, a posição da cabeça e o conteúdo da fita. Se você encontrar um caminho de configuração (que é chamado de execução ) para uma configuração de aceitação, na verdade o idioma não está vazio e é uma condição iff.

O problema com o uso da análise de acessibilidade no gráfico de configuração é que ele pode ser infinito. É por isso que decidir o vazio da linguagem é indecidível.

É também por isso que o não vazio da linguagem é reconhecível - você pode executar um BFS no gráfico de configuração infinita. Se houver um caminho para um estado de aceitação, você o encontrará eventualmente. Se não houver, no entanto, você poderá ficar preso em uma pesquisa infinita.

Shaull
fonte
A função de transição de uma TM é assim: F (Q T) -> (Q T * {L, R}). Você poderia escrever a função para ignorar a entrada?
314 msn
Sim. Nesse caso, , F ( q 1 , a ) = F ( q 1 , b ) = ( q 2 , a , L ) , F ( q 2 , a ) = (F(q0,a)=F(q0,b)=(q1,a,R)F(q1,a)=F(q1,b)=(q2,a,L) e F ( q 2 , b ) = ( q a c c , a , L ) (mas o último nunca é alcançado). F(q2,a)=(q1,a,R)F(q2,b)=(qacc,a,L)
Shaull
9

é indecidível por causado TeoremadeRice, que afirma que propriedades não triviais de funções parciais não são decidíveis.A

  1. Existe uma TM que não aceita nenhuma string. (Que vai diretamente para o estado de rejeição).
  2. Existe uma TM que aceita todas as strings. (Que vai diretamente para o estado de aceitação).

Isso significa que as funções calculadas pelos elementos de têm uma propriedade não trivial. Portanto, A não é decidível.AA

é decidível apenas sob a suposição de que os DFAs são codificados de maneira especial, como tabela de transição de estado ou etc. (não podemos decidir se uma TM aceita apenas idiomas regulares, por causa do Teorema de Rice!). Neste caso Teorema de Rice não é aplicável porque a codificação específica de um elemento é necessário para decidir sobre E . Portanto, não decidimos apenas funções parciais.EE

(Ou seja, se o problema fosse, decidir se uma MT específica é um DFA - ou DFA computável - e o idioma aceito por ela estiver vazio, seria indecidível pelo Teorema de Rice. Observe que, neste caso, A = E .)EA=E

Eu.
fonte
6

Outra dica: tente reduzir o problema de parada para .L

(A dica original é usar o teorema de Rice, mas, neste caso, uma prova direta também é bastante simples.)

Yuval Filmus
fonte
@Yuval_Filmus É correto dizer que esse idioma nem é Turing reconhecível?
Sashas # 28/15
1
O que você acha? Você pode provar sua reivindicação? Nesse caso, não há necessidade de fazer a pergunta.
Yuval Filmus
1

Lema 1 : Se L é indecidível, então o complemento de L.

Sabemos que o problema da parada, HTM é indecidível. Portanto, de acordo com o Lema um complemento do problema da paragem, HTMc também é indecidible.

HTM ={M,x M is a TM and M halts on input x }

HTMc ={M,x M is a TM and M loops on input x }

ETM ={M M is a TM and L(M) = }

Assume-se que ETM é determinável. Vamos reduzir HTMc para ETM - em outras palavras, vamos mostrar como construir uma máquina de Turing MHTMc que decide HTMc usando o TM, METM que decide ETM . Isso nos dá uma contradição, porque sabemos que HTMc é indecidível e, portanto, MHTMcnão pode existir. A palavra "reduzir" significa simplesmente resolver um determinado problema, convertendo-o em outro problema que já sabemos resolver. Assim, a máquina de Turing para HTMc pode ser construído como se segue:

MHTMc = “na entradaM,x

1. Construa o código para uma TM, M1 que faça o seguinte:

M1 = "na entradaw

1. Simule M em x .

2. Aceite se M parar ".

2. Execute METM em M1

3. Aceite se METM aceita, rejeite de outra forma. "

É crucial entender que o TM M1 nunca é realmente simulado - essa simulação pode entrar em um loop infinito. Tudo o que estamos fazendo é construir o código para M1 .

M1 é construído de tal maneira que em qualquer entradaw dada a ele, ele simularáM com a entradax . M pode parar ou fazer um loop emx e, portanto, pode haver dois casos:

1. M1 aceita todas as entradas w se M parar em x . METM rejeitará M1 como L(M1) .

2. Se M fizer um loop em x , M1 também fará um loop para todas as entradas w lhe forem dadas. De qualquer forma, como METM é umSe decidir que rejeitará e interromperá na entrada M1 como L(M1)= .

Correctness : DesdeMETM sempre paradas (por nossa suposição),MHTMc também sempre paradas. MHTMc aceita seMETM aceita, isto é, seL(M1)= que acontece seM fizer umloop emx .
MHTMc rejeita seMETM rejeita queL(M1) que acontece seM parar emx . Assim,MHTMc decideHTMc que é uma contradição, poisHTMc é indecidível.


Nb:

Deixe R ser a redução a partir de HTMc para ETM .

A redução fornece:

i) M,xHTMcR(M,x)ETM

H laçadas na entrada x sse o idioma reconhecido por R(M,x) aceita nada

ii) M,xHTMcR(M,x)ETM

M paradas na entrada x sse a linguagem reconhecida por R(M,x) aceita algo

Nabhan Abdulla
fonte
0

Prova por contradizendo , (que sabemos que é indecidível).ATM={M,wM is a Turing Machine which accepts w}

Pressupõem a existência de , um TM que decide G RTML

Uso pode então usar na construção de uma TM S T M , que é um decisor para A t MRTMSTMATM

"Na entradaH , W , onde H é a codificação de uma TM e W é uma cadeia de caracteres:STM=definitionM,wMw

  1. Modifique , levando em consideração a entrada w , de modo que o novo M (chame de M 1 ) rejeite todas as entradas que não sejam iguais a w , onde w está embutido em sua descrição. Se a entrada for igual a w , então M 1 executará M em we produzirá quaisquer que sejam M saídas.MwMM1wwwM1MwM

  2. Executar com a entrada M 1 , w RTMM1,w

  3. Saída o oposto de saída s ".RTM

O pressuposto de que existe um descongelante Turing Máquina para , permite-nos construir um decisor para um T M , que é uma contradição.LATM

Pétur Ingi Egilsson
fonte
Não é a entrada de uma MT (sem extras w )? Como você executar R T M em M 1 , w ? RTMwRTMM1,w
Xkxzr # 22/18
-2

E = {| M é uma TM e L (M) = Φ}. O E Turing é reconhecível?

E é uma linguagem, para aceitar a linguagem E construímos uma Máquina de Turing. Suponha que criamos um EM de Turing para o idioma E.

O EM será fornecido como entrada, a codificação de outras máquinas de Turing. Se essa máquina inserida M aceitar um idioma vazio, será membro do idioma E, caso contrário, não será membro do idioma.

Suponha que tenhamos uma Máquina de Turing M, precisamos verificar se ela aceita um idioma vazio. O EM da máquina de Turing possui M e as seqüências eps, a, b, aa, bb, ..... O EM verificará se M pode atingir um estado final de pelo menos uma única entrada e se aceita pelo menos uma única entrada. será descartado e não incluído no idioma E. Agora, veja uma possibilidade do TM M entrar em um loop para que o M continue funcionando e não pudemos decidir se ele pode aceitar ou não nada. Portanto, esse idioma E não é RE.

PS: Eu acho que o complemento dessa linguagem E será RE.

Manu Thakur
fonte
Infelizmente, esse argumento intuitivo não constitui uma prova. Pode haver uma maneira diferente de decidir E, e isso não é descartado pelo seu argumento.
Yuval Filmus
sim correto, mas da maneira que expliquei alguém pode entender em linguagem leiga.
precisa saber é o seguinte
Este site não é para leigos. É para ciência da computação teórica em nível acadêmico.
Yuval Filmus
2
Tudo o que você fez é apresentar um argumento intuitivo sobre por que uma técnica computacional específica parece falhar na solução desse problema. Mas a questão está pedindo uma prova de que nenhuma técnica possível funciona.
David Richerby