Uma máquina que nunca pára sempre faz um loop?

22

Uma máquina de Turing que retorne ao estado encontrado anteriormente com sua cabeça de leitura / gravação na mesma célula da mesma fita será presa em um loop. Essa máquina não para.

Alguém pode dar um exemplo de uma máquina sem interrupção que não se repete?

computability turing-machines halting-problem hollow7
fonte

1

Apenas uma observação: a fita também pode ser diferente: uma condição suficiente (mas não necessária) para um loop sem fim quando a MT entra na mesma célula na etapa

e na etapa

no mesmo estado, é aquela em etapa

a parte da fita visitada pela cabeça entre a etapa

e a etapa

é igual à porção correspondente imediatamente antes de inserir

.

t_{1}

$t_1$

t_{2} > t_{1}

$t_2 > t_1$

t_{2}

$t_2$

t_{1}

$t_1$

t_{2}

$t_2$

t_{1}

$t_1$

Vor

4

Se uma TM tivesse que fazer um loop para não interromper, você seria capaz de resolver com facilidade o problema de interrupção das MTs: lembre-se de todas as configurações anteriores e, a cada etapa, verifique se você está em uma configuração que já viu antes, e se assim for, você sabe que a coisa não pára (caso contrário, como assumimos que ela deve fazer um loop para poder rodar para sempre, não será executada para sempre, ou seja, será interrompida; nesse caso, eventualmente saber sobre isso).

22812 Patrick87

Inspirado pela resposta de @Niel de Beaudrap: uma máquina de turing pode calcular a sequência oeis.org/A014445 e parar quando obtiver um número ímpar. Ele pode calcular oeis.org/A016742 como uma soma contínua e parar quando o número é ímpar. Poderia calcular x^2onde os xciclos entre -100e 100e o ciclo são feitos com um módulo e parar quando o resultado é negativo. Ele poderia calcular x%2onde x varia de zero ao infinito positivo e parar quando o resultado é igual a 2. Na linguagem assembly, os loops while / while / down vêm todos com um salto condicional, mas o salto cond significa pouco.

Leonid

A suposição da pergunta é verdadeira apenas para máquinas determinísticas.

Raphael

15

Considere a TM que sempre move a cabeça da fita para a direita e imprime um símbolo especial de fita não em branco a cada etapa. Isso significa que a TM nunca para, pois sempre se move para a direita e nunca repete um estado, pois depois que k pisa, a cabeça da fita fica sobre a quinta célula da máquina. Conseqüentemente, cada configuração da máquina é diferente de todas as outras, e a máquina sempre faz um loop.

Também poderíamos mostrar de maneira não construtiva a existência de tais máquinas. Suponha, por contradição, que toda MT que nunca pára, eventualmente faz um loop. Isso significa que, se você iniciar um TM em uma sequência , um dos seguintes ocorrerá eventualmente: $M$ $w$

pára, ou $M$
repete uma configuração. $M$

Nesse caso, o problema da parada seria decidível da seguinte maneira. Dada uma TM e a sequência , simule em , a cada ponto, anotando o conteúdo da fita, o estado atual e a posição atual da fita. Se essa configuração for duplicada, a saída "não será interrompida". Caso contrário, se parar em , a saída "pára". Como é garantido que um desses eventos acabe eventualmente, esse processo sempre termina, portanto, teríamos um algoritmo para o problema de parada, que sabemos que não existe. $M$ $w$ $M$ $w$ $M$ $w$

Espero que isto ajude!

templatetypedef
fonte

Hah, vencê-lo nessa edição. Veja meu comentário sobre a questão. Eu gosto dessa maneira de explicar por que nem todas as MTs sem interrupção devem fazer um loop ... isso cria intuição.

Patrick87

@ Patrick87- Desculpe, eu não percebi o comentário. Pensei no adendo no meu trajeto e me sentei para entrar assim que voltei.

templatetypedef

Não tem problema, cara ... Fico feliz que você tenha adicionado, pois acho que é uma boa maneira de explicar. Eu apenas o adicionei como comentário, e não como resposta, já que você me venceu. : D

Patrick87 13/07/12

Na verdade, em termos do problema de parada, que volta e troca a fita ad infinitum parece ser o "problema real". Aqueles caminhantes vazios que você pode detectar.

Raphael

12

Uma máquina de Turing que calcula todas as casas decimais de π (ou qualquer outra fração sem terminação, em qualquer base) nunca pára, e pode ser feita para escrever em cada célula apenas um número finito de vezes. Obviamente, o fato de não haver transição para um estado de parada seria uma oferta inoperante, mas é pelo menos um exemplo natural.

f (n) = {\begin{cases} 3 n + 1, & if n is odd; \\ n / 2, & if n is even, \end{cases}

$f(n) = \begin{cases} 3n+1 , & \text{if $n$ is odd}; \\ n/2, & \text{if $n$ is even}, \end{cases}$

f \circ f \circ \dots f (n) = n

$f \circ f \circ \cdots f(n) = n$ , ... que divergem assintoticamente para o infinito. Se existir alguma sequência deste último tipo, isso implicaria que a máquina de Turing que descrevi acima não seria repetida, pois a fita seria continuamente alterada para números cada vez maiores.

Niel de Beaudrap
fonte

Eu gosto de brincar com os dígitos de pi. A TM pode parar sempre que o quadrado de qualquer dígito piiguais exatamente 7.

Leonid

@ Leonid: Você certamente poderia considerar uma máquina de Turing que aceita alguma entrada e pára em uma condição determinada por essa entrada. Você pode até fazer a especificação das condições sob as quais ele pára parte da entrada. E você pode fornecer uma entrada, como você descreve, definindo uma restrição que nunca é satisfeita.

Niel de Beaudrap 17/07/12

10

Considere qualquer máquina de Turing sem interrupção que nunca mova a cabeça de leitura / gravação para a esquerda.

JeffE
fonte

Alguns deles ainda fazem loop. </nitpicking>

Raphael

5

Se isso fosse verdade, o problema da parada seria decidível. Você apenas gravaria cada par (fita, estado) visto ao executar a máquina de Turing, e a máquina parava (nesse caso, obviamente, para) ou você vê um par que você já viu antes, nesse caso a máquina não para.

Como o problema da parada é indecidível, isso não pode ser verdade. (Veja outros exemplos para exemplos contrários.)

RecursivelyIronic
fonte

O que essa resposta adiciona à resposta do templatetypedef ?

Raphael

I guess it doesn't. Sorry, I somehow missed that answer when I wrote mine.

RecursivelyIronic

Uma máquina que nunca pára sempre faz um loop?

Respostas: