Em comemoração ao aniversário de Alan Turing, o Google publicou um doodle mostrando uma máquina. Que tipo de máquina é o doodle? Ele pode expressar um idioma completo de Turing?
Existem diferenças óbvias na máquina de turing clássica: uma fita finita, restrições de como o estado pode ser conectado, ...
O doodle ainda está disponível aqui
(O visor no canto superior direito mostra a saída esperada.)
A fita no meio é dividida em quadrados que podem conter um espaço em branco, um zero ou um. A cabeça está posicionada acima de um dos quadrados e é usada para leitura e escrita.
Abaixo da fita, você pode ver uma seta verde na qual você pode clicar para iniciar a máquina. Existem duas linhas de círculos ao lado, algumas das quais estão conectadas. Vou chamá-los de "estados".
Depois que a máquina inicia, o primeiro estado à direita do botão verde acende, depois o próximo à direita e assim por diante ... Cada estado contém um dos seguintes comandos:
- em branco = não fazer nada (basta passar para o próximo estado)
- 1 = escreva um na fita na posição atual da cabeça
- 0 = escreve um zero na fita na posição atual da cabeça
- seta para a esquerda = mova a cabeça um passo para a esquerda
- seta para a direita = mova a cabeça um passo para a direita
- condição: se o valor abaixo da cabeça for igual ao valor mostrado no quadrado, desça para a segunda linha de estados. caso contrário, vá para o próximo estado à direita
- salto esquerdo: retorne ao estado anterior (fixo), mas apenas na linha superior [originalmente eu esqueci esse, obrigado @Marzio!]
Não há como "sobrepor" dois saltos (um sobre o outro). A máquina para quando sai de um estado e não existe um próximo estado à sua direita.
(Após a máquina parar, o conteúdo da fita é comparado ao conteúdo da tela, mas não considero que isso faça parte da funcionalidade pretendida da máquina.)
Respostas:
Assumindo que:
Tentei criar uma configuração de máquina Doodle de Alan Turing que emula a máquina descrita em " Máquinas pequenas de Turing e competição generalizada de castores ocupados " que tem um problema de parada que depende de um problema aberto (como eu sei) de Collatz. A imagem completa está disponível aqui .M4
... portanto, mesmo que o Doodle do AT talvez não seja Turing completo (devido ao operador de salto esquerdo não sobreposto disponível apenas na primeira linha), ele é poderoso o suficiente para percorrer a linha fina da (des) decidibilidade: - D
EDIT: TURING DOODLE ESTÁ COMPLETO
(Deixo a resposta anterior acima, porque não tenho certeza de que esta parte esteja correta :-)
Eu acho que mesmo com um único salto esquerdo sem sobreposição, o Turing Doodle é Turing completo! . A idéia (simples) é usar a própria fita para armazenar o estado atual e usar várias células para representar um alfabeto maior.
Por exemplo, 2 estados e 8 símbolos TM podem ser simulados usando a seguinte representação em fita:
O doodle de Turing pode:
A imagem completa está disponível aqui .
fonte
alen turing
. Gostei de ler issoEste é um trecho do artigo original de Turing "Sobre números computáveis, com uma aplicação ao problema Entscheidung".
Um bom companheiro moderno do artigo que recomendo é The Annotated Turing, de Charles Petzold.
Como você pode ver, o Google apenas tentou se parecer com uma máquina muito semelhante à descrição de Turing.
Edição: Assumindo que o alfabeto completo do Google TM é o mostrado no final do jogo, depois de clicar no ícone do coelho , e tirando o fato de que está produzindo uma sequência infinita , obtém mais linhas e colunas (então podemos assumir que podemos adicionar qualquer ), deixou saltos à esquerda (e também sobrepôs saltos à esquerda) em qualquer linha , tem salto condicional e incondicional entre linhas adjacentes, acho que é Turing completo .
fonte
Nos quebra-cabeças, saltos são permitidos nas duas linhas, mas não podem se sobrepor. No doodle final da sequência de coelhos no final do jogo, eles permitem saltos em todas as linhas e podem ser aninhados entre colchetes , e [()] é permitido, mas ([)] parece não ser permitido.
Usarei as seguintes suposições:
Com essas suposições, o Google Doodle Machine é Turing Complete .
O GDM simula a TM da seguinte maneira:
Escolha sua TM universal favorita e implemente-a no procedimento acima para obter um GDM universal.
fonte