Que tipo de autômato é o Turing Doodle do Google?

10

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 Captura de tela do doodle

(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.)

bjelli
fonte
9
Uma máquina de Turing, é claro! pt.wikipedia.org/wiki/Turing_machine Talvez você estivesse confuso porque o sistema de transição é descolado.
precisa
Há também um "operador de salto esquerdo" no mecanismo de controle que permite retornar à posição anterior, mas apenas na linha superior; além disso, não há como "sobrepor" dois saltos (um sobre o outro). Sem o operador de salto, a máquina é equivalente a um DFA (as ações no mecanismo de controle são "executadas" da esquerda para a direita), mas também com o operador de salto esquerdo limitado , a máquina parece não ser suficientemente poderosa para simular um LBA (mas eu não não pense muito nisso). Em todos os casos, não pode ser Turing completo porque a fita é finita.
Marzio De Biasi
11
@Marzio De Biasi: Você está certo que este quebra-cabeça contém instruções de salto e, sem elas, o modelo é obviamente muito fraco, porque uma máquina só pode funcionar por um tempo constante. (Não sei ao certo o que você quer dizer com “equivalente a um DFA”.) Que restrição você coloca nas instruções de salto pode alterar a resposta. "A fita é finita" é provavelmente uma suposição incorreta.
Tsuyoshi Ito
O Google mantém seus doodles disponíveis (embora aparentemente nem sempre as versões interativas).
Raphael
@TsuyoshiIto: Quero dizer (mas talvez eu esteja errado) que, dada uma máquina sem loops, você pode criar um DFA que simule. Se você permitir saltos arbitrários em ambas as direções e que possam se sobrepor, a máquina estará imediatamente "completa" (assumindo uma fita infinita), mesmo com apenas duas linhas (os estados podem ser "achatados" horizontalmente). Não sei o que acontece se você permitir saltos à esquerda que possam se sobrepor (mas apenas na primeira linha) e um número arbitrário de linhas (mas o controle nas linhas inferiores pode ser apenas para cima ou para baixo). Talvez seja uma boa pergunta para cs.stackexchange.com
Marzio De Biasi

Respostas:

10

Assumindo que:

  • podemos adicionar um número arbitrariamente grande de linhas ("linhas de status")
  • as linhas podem ser arbitrariamente longas
  • a fita é infinita

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

atdoodle

... 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:

    HEAD POSITION
    v
...[s][b2 b1 b0] [_][b2 b1 b0] [_][b2 b1 b0] ....
   ^^^^^^^^^^^^^
    "macro cell"

O doodle de Turing pode:

  1. s
  2. b2,b1 1,b0 0
  3. escreva o próximo símbolo, mova a cabeça para a "célula macro" à esquerda ou à direita e armazene nela o próximo estado; na figura abaixo, essas operações (que podem ser feitas em uma sequência de células usando as ações mover para a esquerda / direita e escrever) são chamadas de "MW";
  4. finalmente, transfira o controle para a linha superior que, com um único salto à esquerda, o controle retornará à etapa 1.

A imagem completa está disponível aqui .

TdoodleTC

TMDM

Marzio De Biasi
fonte
nooo! Você chegou antes de mim! Eu estava escrevendo como fazer uma TM arbitrária no espaço de estados, em vez de fita. No entanto, sua abordagem é melhor, pois usa apenas um salto. Bem feito! Aguarde, como sua máquina recebe entrada?
Artem Kaznatcheev
@ marzio-de-biasi Bom trabalho!
pepper_chico
11
@ArtemKaznatcheev: recebe entrada na fita; obviamente, você deve codificá-lo de acordo com os símbolos do alfabeto original da MT que você está emulando e deixar espaços em branco para a representação do estado.
Marzio De Biasi
A marca do júnior alen turing . Gostei de ler isso
iDroid
não totalmente convencido quanto à completude da TM. não pense que você lidou com o caso em que a TM grava em novos quadrados em branco não definidos anteriormente na fita de entrada. isso é necessário para a integridade da TM, caso contrário, é apenas um cálculo finito.
vzn
5

A máquina é fornecida com uma “fita” (o análogo do papel) passando por ela e dividida em seções (chamadas “quadrados”), cada uma capaz de exibir um “símbolo”. A qualquer momento, existe apenas um quadrado, digamos o r-ésimo, com o símbolo S (r) que está “na máquina”. Podemos chamar esse quadrado de “quadrado digitalizado”. O símbolo no quadrado digitalizado pode ser chamado de "símbolo digitalizado". O “símbolo digitalizado” é o único dos quais a máquina está, por assim dizer, “diretamente consciente”. No entanto, alterando sua configuração m, a máquina pode efetivamente lembrar alguns dos símbolos que “viu” (digitalizados) anteriormente. O possível comportamento da máquina a qualquer momento é determinado pela configuração m qn e pelo símbolo digitalizado S (r). Este par qn, S (r) será chamado de "configuração": assim, a configuração determina o possível comportamento da máquina. Em algumas das configurações nas quais o quadrado digitalizado está em branco (ou seja, não possui símbolo), a máquina anota um novo símbolo no quadrado digitalizado: em outras configurações, ele apaga o símbolo digitalizado. A máquina também pode alterar o quadrado que está sendo digitalizado, mas apenas deslocando-o um lugar para a direita ou esquerda. Além de qualquer uma dessas operações, a configuração m pode ser alterada. Alguns dos símbolos escritos {232} formarão a sequência de números que é o decimal do número real que está sendo calculado. Os outros são apenas notas brutas para "ajudar a memória". Somente essas notas ásperas poderão ser apagadas. não possui símbolo) a máquina anota um novo símbolo no quadrado digitalizado: em outras configurações, apaga o símbolo digitalizado. A máquina também pode alterar o quadrado que está sendo digitalizado, mas apenas deslocando-o um lugar para a direita ou esquerda. Além de qualquer uma dessas operações, a configuração m pode ser alterada. Alguns dos símbolos escritos {232} formarão a sequência de números que é o decimal do número real que está sendo calculado. Os outros são apenas notas brutas para "ajudar a memória". Somente essas notas ásperas poderão ser apagadas. não possui símbolo) a máquina anota um novo símbolo no quadrado digitalizado: em outras configurações, apaga o símbolo digitalizado. A máquina também pode alterar o quadrado que está sendo digitalizado, mas apenas deslocando-o um lugar para a direita ou esquerda. Além de qualquer uma dessas operações, a configuração m pode ser alterada. Alguns dos símbolos escritos {232} formarão a sequência de números que é o decimal do número real que está sendo calculado. Os outros são apenas notas brutas para "ajudar a memória". Somente essas notas ásperas poderão ser apagadas. Alguns dos símbolos escritos {232} formarão a sequência de números que é o decimal do número real que está sendo calculado. Os outros são apenas notas brutas para "ajudar a memória". Somente essas notas ásperas poderão ser apagadas. Alguns dos símbolos escritos {232} formarão a sequência de números que é o decimal do número real que está sendo calculado. Os outros são apenas notas brutas para "ajudar a memória". Somente essas notas ásperas poderão ser apagadas.

É minha opinião que essas operações incluem todas as que são usadas no cálculo de um número. A defesa dessa afirmação será mais fácil quando a teoria das máquinas for familiar para o leitor. Na próxima seção, portanto, prossigo com o desenvolvimento da teoria e assumo que seja entendido o que se entende por "máquina", "fita", "digitalizado" etc.

Este é 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 .

pepper_chico
fonte
mas eles implementaram de maneira aguda uma máquina de turing? este tem uma fita finita, então essa é uma diferença facilmente discernível. é uma diferença que faz a diferença? eles de fato implementaram uma máquina mais fraca?
bjelli
2
@bjelli Bem, não posso garantir isso porque, como ainda não o projetei, não conheço todas as regras sobre sua máquina. Mas, se você chegar à final do jogo, poderá clicar no ícone Bunny, que leva a uma fita mais longa, verifique a análise aqui: sbf5.com/~cduan/technical/turing . Portanto, pode não haver restrições quanto ao número de linhas que a máquina pode obter, o que levaria a uma fita de qualquer tamanho.
pepper_chico
plz esboçar uma prova de que a sua Turing completa
vzn
4

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:

  1. 0 01 1ϵ
  2. A máquina pode usar qualquer número fixo de linhas
  3. Saltos à esquerda são permitidos em qualquer linha (usarei um salto à esquerda por linha)
  4. ϵ0 01 1

Com essas suposições, o Google Doodle Machine é Turing Complete .

0 01 1ϵ0 01 1n

3(n-1 1)+1 15n+1 1

Google Doodle Machine

ϵ0 01 1ϵ0 01 10 01 1

O GDM simula a TM da seguinte maneira:

  1. 1 1
  2. j
  3. ϵ0 01 1
  4. ϵ
  5. 0 01 1
  6. 0 01 1

Escolha sua TM universal favorita e implemente-a no procedimento acima para obter um GDM universal.

Artem Kaznatcheev
fonte