Qual é a diferença entre parar, aceitar e decidir no contexto das máquinas de Turing?

10

Aceitar significa que a TM lerá e reconhecerá um caractere da célula da qual está lendo atualmente? E é o caso de uma TM parar se a entrada for decidida?

sdfasdgasg
fonte
Parar é sinônimo de terminar (em um estado de aceitação / rejeição). Aceitar um idioma (decidir a participação em um idioma) significa interromper em um estado de aceitação todas as entradas que pertencem ao idioma.
saadtaame 15/09/12
Esta é uma questão de definições básicas. O que tem confundido você?
Raphael

Respostas:

10

Aceitar e rejeitar o estado em que uma máquina de Turing pode eventualmente entrar, baseia-se na sequência lida na fita, não apenas no símbolo de uma célula. Obviamente, a decisão sobre inserir uma fita de aceitação ou rejeição é finalmente tomada com base em um símbolo.

Uma máquina de Turing pode, eventualmente, entrar em um estado de aceitação, entrar em um estado de rejeição ou fazer um loop para sempre. Se entrar em um estado de aceitação ou rejeição, será interrompido.

Uma máquina de Turing é considerada total se parar em todas as entradas.

O idioma aceito por uma máquina de Turing é o conjunto de todas as palavras que, quando fornecidas como entrada para a máquina de Turing, fazem com que a máquina de Turing entre no estado de aceitação.

Diz-se que um idioma é decidível se, e somente se, existe uma máquina de Turing total que aceitará o idioma.

Dave Clarke
fonte
Na verdade, deveríamos estar falando sobre programas de máquinas de Turing. A própria máquina de Turing é um modelo. É um abuso da expressão.
saadtaame 15/09/12