Qual é a diferença entre uma MT que aceita e decide um idioma?

Francamente, estou muito desconfortável com o material no momento. Há algumas coisas que posso entender, mas muitas ainda não o compreendo.

Minha primeira tarefa é me fazer uma pergunta (que eu sei fazer) para fornecer uma descrição completa de uma MT que aceite um idioma $L = \{ x \in \{0,1\}^* \mid x \text{ is divisible by } 4 \}$. Eu sei que qualquer string binária que termina com$00$ é divisível por 4, então $\{00,100,1100,1000,11100,11000,10100,10000,\dots\}$ é o idioma que esta TM aceita.

Mas no tópico da (des) decidibilidade: eu sei que uma linguagem é decidível se existe uma TM que aceita todas as strings e somente strings dessa linguagem - e essa mesma TM rejeita todas as strings e somente strings que não estão nesse idioma.

O que leva à pergunta: qual é a diferença entre uma máquina de Turing aceitar e decidir um idioma?

Em situações como estas, nas quais você está pensando sobre a diferença entre duas frases, a coisa certa a fazer é procurar algumas definições e pensar nelas. Você descobrirá várias variações, talvez algo como isto:

1. Uma máquina "come" um idioma $L$ se na entrada $x$ para e produz $1$ E se $x \in L$e $0$ de outra forma.

2. Uma máquina "bebe" um idioma $L$ se na entrada $x$ele pára em um acceptestado quando$x \in L$e em um rejectestado se$x \not\in L$.

3. Uma máquina "fareja" um idioma $L$ se na entrada $x$ele pára em um acceptestado quando$x \in L$e nunca termina se $x \not\in L$.

4. Uma máquina "devora" um idioma $L$ se na entrada $x$atinge um OKestado em que$x \in L$e nunca entra no OKestado de outra maneira.

5. Uma máquina "mastiga" um idioma $L$ se na entrada $x$ele pára em estado 0quando$x \in L$e nunca termina ou pára no estado 1quando$x \not\in L$.

Todos parecem iguais, mas são todos ligeiramente diferentes. Você deve esperar que algumas definições sejam levemente quebradas (porque você a encontrou na Wikipedia ou nas anotações de seu colega de classe) ou redigidas de uma maneira estranha que atenda às necessidades de um determinado livro de texto etc.

A coisa mais importante a fazer é descobrir o que as definições realmente estão tentando transmitir. Se são definições básicas às quais todos se referem, é provável que lhe digam algo importante. (Em um trabalho de pesquisa, as pessoas às vezes fazem definições para entorpecer o cérebro dos leitores.) Quando os conceitos são claros, não importa como eles são chamados. Além disso, em caso de confusão terminológica, você sempre será capaz de resolver rapidamente possíveis mal-entendidos, porque já sabe quais conceitos esperar.

No presente caso, existem realmente duas noções possíveis. Um em que uma máquina sempre interrompe e sinaliza aceitação / não aceitação de alguma forma, por exemplo, interrompendo em certos estados ou emitindo certos símbolos. O outro conceito é quando uma máquina nem sempre pára e usa a interrupção para indicar aceitação e a não interrupção para indicar não aceitação.

Um bom exercício é descobrir qual das cinco definições dadas acima corresponde a qual dos dois conceitos (e qual definição é um pouco incerta, se houver). Mas mesmo antes do exercício, você precisa saber por que esses são dois conceitos diferentes! Você precisa estar ciente de um idioma que se enquadre em um, mas não no outro conceito.

O problema com o aprendizado de matemática é que você precisa aprender simultaneamente novas frases e seus meandros e descobrir por que as pessoas as inventaram.

Há uma grande diferença. Uma máquina de turing "aceita" um idioma, se entra em um estado de aceitação para qualquer entrada do idioma, enquanto "decide" o idioma se "aceita" e entra em um estado de rejeição para qualquer entrada que não esteja no idioma.

São diferentes, porque há uma terceira coisa que uma máquina de Turing pode fazer: nunca pare. Essa máquina de Turing aceita o idioma, mas não o decide.

Veja também esta outra questão e definição de linguagem decidível no WP .

Eles são geralmente usados ​​como sinônimos. No seu exemplo, a Máquina de Turing deve primeiro ir até o final da entrada e depois verificar se os dois dígitos mais à direita são 0, como você sugere.