Toda linguagem recursiva é reconhecida por uma máquina mortal de Turing?

Dizemos que uma Máquina de Turing é mortal se parar para cada configuração inicial (em particular, o conteúdo da fita e o estado inicial podem ser arbitrários). Toda linguagem recursiva é reconhecida por uma máquina de Turing mortal? (ou seja, se existe uma MT que aceita , também existe uma MT mortal que aceita ) $M$ $M$ $L$ $L$

computability Marcin Kotowski
fonte

Você pode dar referência às Máquinas de Turing Mortal? Obrigado :)

Tayfun Pay

Como é que o estado inicial pode ser arbitrário? Uma máquina de Turing mortal não é apenas uma TM que pára em cada entrada?

Philip White

@ Marcin: você está interessado em máquinas que param em todas as configurações, incluindo infinitas, ou apenas naquelas que param em todas as configurações finitas ?

Joshua Grochow

Eu acho que ele quer dizer configurações iniciais finitas. Certo?

Philip White

@ Philips: Imagine a máquina em estado e configuração arbitrários e execute o cálculo a partir desse ponto, seguindo as regras usuais.

21414 Joshua Grochow

Respostas:

Aqui estão dois resultados citados em Charles E. Hughes "Indecidibilidade da convergência finita para operadores de concatenação, inserção e shuffle limitado" :

Teorema 3 : A classe das máquinas de Turing mortais é exatamente a classe das máquinas de Turing com tempo de execução constante.

r para todas as configurações iniciais $ConstT = \{ M \mid \exists s$ , paradas em não mais do que as etapas $C$ $M$ $s$ $\}$

Então, acho que podemos derivar o seguinte: dada uma máquina de Turing mortal , seja o tempo constante correspondente TM e seu tempo de execução. A língua reconhecida por $M$ $M', s$ $M$ sobre o alfabeto é exatamente: $\Sigma = \{0,1\}$

{x y ∣ | x | \leq s \land M^{'} accepts x in no more than s steps, y \in {0, 1}^{*}}

$\{ xy \mid |x| \leq s \land M' \text{ accepts } x \text{ in no more than s steps}, y \in \{0,1\}^* \}$

Portanto, a classe de idiomas reconhecida pelas máquinas de Turing mortais é um subconjunto apropriado da classe de idiomas regulares. Por exemplo, você pode usar para enganar toda vez TM constante. $L = \{(0|1)^*1^*\}$

As coisas ficam interessantes quando tentamos decidir se uma máquina de Turing é mortal porque temos que enfrentar fita e estado inicial arbitrário (finito).

Teorema 4 : o conjunto de máquinas de Turing mortais é recursivamente enumerável.

Marzio De Biasi
fonte

Eu acho que existe. Temos que fazer para cada L que M o aceite de tal maneira que todos os seus movimentos sejam gravados em uma fita e após cada "passo principal", verifique se todos os seus passos até aquele momento eram realmente válidos. Abaixo, descrevo como essa máquina deve ser fabricada (que pode conter alguns erros menores, mas a idéia principal deve ser boa).

Indique uma máquina que aceita L por T. Agora, descrevemos M. Primeiro, copiamos x para uma fita de memória separada. Então, sempre que T faz uma jogada, anotamos nessa fita de memória, depois de x. Depois disso, copiamos todo o conteúdo das fitas de T em algumas fitas de trabalho extras e verificamos se, a partir da configuração inicial, T realmente chegaria ao seu estado atual após as etapas gravadas na fita de memória. Caso contrário, paramos. Se sim, continuamos.

domotorp
fonte

enquanto escrevia minha resposta, li a sua ... que diz o contrário :-) ... talvez eu esteja interpretando erroneamente o que é uma string aceita por uma máquina de Turing mortal?

Marzio De Biasi

@MarzioDeBiasi: A noção de mortal considerada nesse artigo exige uma parada da máquina em um número finito de etapas, mesmo se for iniciada com uma quantidade infinita de dados arbitrários em sua fita. Mas acho que a construção da domotorp funciona no máximo para configurações finitas. Por exemplo, em uma configuração com uma entrada infinita de comprimento, M de domotorp é pego em uma sequência infinita de copiar a entrada infinita de comprimento para a fita de memória separado ...

Joshua Grochow

Sim, a diferença é que eu supunha que todo o conteúdo da fita é finito e sabemos onde estão os limites. Caso contrário, as TM mortais são apenas constantes, como você escreve.

Domotorp