Os azulejos Wang (dominós) foram inventados por Hao Wang em 1961 para problemas matemáticos, mas foram amplamente utilizados em jogos para criar gráficos de azulejos. Graças a eles, os resultados não parecem repetitivos, tanto em texturas 2D quanto em modelos 3D com ladrilhos.
Parece que as peças de Van também são capazes de executar máquinas de Turing e, portanto, são completas de Turing, o que significa que podem executar qualquer programa.
Esta é uma afirmação incrível e incompreensível, portanto, neste post, investigarei um pouco esse problema.
Brevemente sobre Van Tiles
Os ladrilhos da van são ladrilhos retangulares nos quais cada uma das faces pode corresponder apenas a outras faces específicas, mas para qualquer face em particular existem vários ladrilhos possíveis que podem corresponder a essa face. Ao combinar faces, quero dizer que elas se conectam perfeitamente sem criar artefatos visuais ou sinais de costura entre os ladrilhos.
Essa propriedade é útil para gráficos, pois permite criar gráficos de bloco sem costura, mas a configuração do local dos blocos pode ser completamente aleatória, desde que todas as faces sejam compatíveis entre si. O resultado são gráficos de ladrilhos, que não são nada parecidos com os de repetição, porque os padrões visuais se tornam muito menos visíveis que os gráficos de ladrilhos tradicionais.
Exemplos gráficos, informações mais detalhadas e links para Shadertoy podem ser encontrados aqui:
Wang Tiling .
Aqui está um exemplo que eu criei. Meus gráficos são "programadores de arte", mas espero que a idéia seja clara. O desenho é composto de 16 peças e, para cada face, existem dois tipos diferentes de faces.
Brevemente sobre máquinas de Turing
As máquinas de Turing foram inventadas em 1936 por Alan Turing como um computador generalizado, para o qual foi provado que ele pode executar qualquer algoritmo.
A máquina de Turing é composta por vários componentes principais: fitas de memória, cabeças de leitura / gravação e máquinas de estado.
A fita de memória possui um comprimento infinito, ou seja, possui uma capacidade de armazenamento infinita e, no início, é inicializada apenas com zeros.
O cabeçote de leitura / gravação começa a partir de uma determinada posição da fita e pode ler / gravar valores, além de se mover para a esquerda e direita ao longo da fita.
A máquina de estado controla a cabeça de leitura / gravação.
A máquina de estado sabe em que estado está e possui regras sobre o que fazer em cada estado quando lê um valor da fita.
Por exemplo, no estado A, se 0 for lido da fita, a regra pode ser escrever 1 na posição atual da fita, mover a cabeça de leitura / gravação para a direita ou ir para o estado B. O estado B pode ter uma lógica completamente diferente e pode executar a transição volte ao estado A ou permaneça no estado B ou mude para um estado completamente diferente.
Usando uma lógica tão simples de transição entre estados, qualquer algoritmo de computador pode ser executado.
A máquina de Turing também pode ter um "Estado de parada", significando que o programa concluiu a execução e a resposta foi calculada.
Procurando alguns programas. pode ser facilmente visto. que com o tempo, eles terminarão ou estarão em um loop infinito e nunca pararão. Alguns programas estão localizados entre eles, são complexos e não é tão fácil determinar se eles irão parar. Turing provou que não há solução geral para determinar se a máquina de Turing irá parar (é um programa de computador), e isso é chamado de
problema de parada . Em geral, a única maneira de descobrir se um programa é interrompido é aguardar. Ou seja, de fato, no caso geral, as respostas a essa pergunta são "sim" ou "ainda não", no entanto, no caso de muitos programas específicos, você pode ver que após o lançamento, eles terminam com o tempo.
Cálculos de Wang Tile
Acontece que os blocos Wang podem simular uma máquina de Turing, ou seja, são completos para Turing, o que significa que podem executar qualquer algoritmo de computador.
Para perceber isso, precisamos de uma coluna de ladrilhos Van que indique o estado da máquina de Turing em um ponto específico no tempo, começando no tempo 0 na coluna mais à esquerda. Colocaremos blocos na coluna à direita com todas as regras das faces e, em seguida, criaremos uma coluna à direita, e assim por diante, até o programa terminar (ou faremos isso para sempre se não terminar). Se você selecionar o conjunto correto de peças, verificar a conformidade com as regras das faces no processo de organização das peças será suficiente para concluir a máquina de Turing.
Vejamos um exemplo simples que possui as seguintes regras de lógica da máquina de estado:
- Quando a máquina está no estado A, no caso da leitura 0, escrevemos 1, movemos a cabeça de leitura / gravação para baixo e vamos para o estado B.
- Quando a máquina está no estado A, no caso da leitura 1, o programa para (muda para o estado final).
- Quando a máquina está no estado B, no caso da leitura 0, escrevemos 1, movemos a cabeça de leitura e gravação para cima e vamos para o estado A.
- Quando a máquina está no estado B, no caso da leitura 1, o programa para (entra no estado final)
Unidade de fita
Primeiro de tudo, precisamos de um armazenamento permanente para a fita. Para fazer isso, precisamos dos dois blocos a seguir:
Para testar seu trabalho, podemos preparar um segmento da fita com alguns valores (criar uma coluna de ladrilhos Van) e garantir que os únicos ladrilhos Van adequados localizados ao lado da coluna inicial sejam ladrilhos que transferem os valores 0 e 1 para frente no tempo sem alterar eles.
No diagrama abaixo, inicializamos a fita com o valor 0101 na coluna mais à esquerda (hora 0). Tendo apenas blocos com faces compatíveis, vemos que os valores na memória são armazenados para sempre. Implementamos uma unidade de memória!
Começaremos a demonstrar nosso exemplo com a memória inicializada em 0, e a figura acima simplesmente mostra a persistência da memória.
Máquina de estado principal de leitura e gravação
A cabeça de leitura / gravação de uma máquina de Turing é apresentada como parte das informações da face. Assim, além da face que armazena 0 ou 1, se a cabeça de leitura / gravação estiver nela, ela também armazena o estado da máquina de estado.
No nosso exemplo, dois estados são usados (não incluindo o estado final): A e B. Se 1 for lido, em qualquer um dos estados (A ou B) o programa será encerrado.
Para lidar com isso, precisamos dos seguintes blocos:
Agora que temos as regras para fazer a transição para o estado final (regras 2 e 4), precisamos entender como implementar as regras que controlam a mudança de um estado para outro (regras 1 e 3).
Movendo a cabeça de leitura / gravação
A regra 1 afirma que se estamos no estado A e lemos 0, devemos escrever 1, mover a cabeça de leitura / gravação para baixo e ir para o estado B.
Precisamos que esse bloco leia 0 no estado A, escreva 1 como saída e ordene que o bloco abaixo entre no estado B.
O bloco abaixo do atual pode ter um valor de 0 ou 1; sem conhecer um valor específico, devemos salvá-lo, mas aceitar a cabeça de leitura / gravação e estar no estado B. Para isso, precisamos de dois blocos - um para 0 na fita nessa posição e o outro para 1 na fita.
A regra 3 afirma que, se estamos no estado B e lemos 0, devemos escrever 1, mover a cabeça de leitura e gravação para cima e ir para o estado A.
Para fazer isso, precisamos de uma construção semelhante à construção da regra 1, mas não movemos para baixo, mas para cima. Os três blocos a seguir fornecerão o resultado desejado:
Mosaicos iniciais da coluna
Vamos perceber os limites da área de simulação como se eles tivessem uma face "x".
Isso significa que, para criar a coluna inicial (máquina de Turing no tempo 0), precisamos de duas peças especiais. Um bloco é necessário para armazenar o valor 0 na fita com a qual a fita é inicializada e outro bloco é necessário para armazenar a posição da cabeça de leitura / gravação no estado A, que é o nosso estado inicial.
Esses dois blocos são:
Conjunto pronto de telhas
Aqui está o conjunto completo de 12 peças que usaremos:
Simulação completa
Aqui está o design original de nossa máquina de Turing no momento 0. Observe que este é um dos possíveis estados iniciais, mas esse é o estado que escolhemos. Não deixamos a chance de escolher onde começa o cabeçote de leitura / gravação e sua presença também. Se seguirmos apenas as regras das faces, podemos obter 4 ou 0 cabeças de leitura / gravação ou qualquer número entre elas.
A partir daqui, para criar a segunda coluna, começamos do topo e descemos, escolhendo um bloco que corresponde às restrições da face em que ele toca. Nesta primeira etapa, a cabeça lê 0, escreve 1, desce e vai para o estado B.
Aqui está o segundo passo, onde a cabeça lê 0, escreve 1, move-se para cima e entra no estado A.
Aqui está o último passo no qual o cabeçalho lê 1 e entra no estado final, indicando que o programa está completo.
O programa foi encerrado e forneceu um valor de saída 0110 ou 6. Esses valores de saída não são particularmente significativos, mas outros programas podem produzir uma saída significativa. Por exemplo, podemos forçar uma máquina de Turing a adicionar dois números, e a saída será a soma desses dois números.
Detalhe importante
Aqui, devemos mencionar um detalhe importante que não consideramos acima e que não é mencionado na maioria das explicações das máquinas de Turing nos ladrilhos Van.
Ao colocar o segundo bloco para o tempo 2, a única restrição nas faces é que o bloco deve ter x na parte superior e 1 à esquerda. De fato, por isso, a situação se torna ambígua, porque não está claro qual dos dois blocos mostrados abaixo deve ser selecionado.
Então, como escolhemos o caminho certo?
A resposta é que apenas fazemos uma suposição e escolhemos uma delas. Se o bloco errado for selecionado nesse caso, quando passarmos para o próximo bloco, procuraremos um bloco com x na parte superior e B0 na esquerda. Esse bloco não existe, então não podemos colocá-lo. Quando isso acontece, precisamos voltar ao último bloco e tentar uma das outras opções.
Infelizmente, ao simular máquinas de Turing usando blocos Wang, existe literalmente um processo de tentativa e erro, mas pelo menos é bastante gerenciável. Realmente complica um pouco os cálculos no pixel shader (ou em outros dispositivos com alto paralelismo), mas os custos não são muito maiores.
Conclusão e links
Alguns dos links abaixo discutem as peças Wang e as máquinas de Turing, mas as discussões não parecem aderir estritamente às máquinas de Turing. Por exemplo, você pode perceber que, em alguns exemplos, os dados podem retornar “no tempo” - quando o programa termina, a resposta está gravada no tempo 0 da máquina de Turing, apesar de esses dados não estarem no tempo 0. Isso mostra que os ladrilhos Wang podem fazer os cálculos por conta própria, não apenas simulando as máquinas de Turing, mas não sei exatamente como essa técnica será chamada.
Além disso, se você estiver interessado em saber o que é útil na computação usando blocos de Wang, pessoalmente não consigo imaginar casos de sua aplicação prática. No entanto, os cientistas parecem ter descoberto que o DNA pode agir da mesma maneira que os azulejos de Van, no sentido de que as conexões são feitas apenas entre faces compatíveis. Graças a isso, agora os cálculos baseados em DNA estão sendo pesquisados com base no processo de computação usando blocos de Wang. Tópico bastante interessante!
Aqui está a implementação do cálculo de números primos usando blocos Wang em Shadertoy no sombreador de pixel WebGL:
Shadertoy: WangTiles: PrimeGeneratorAqui estão mais alguns ótimos vídeos sobre carros de Turing e o problema de parar:
Máquinas de Turing explicadas - ComputerphileTuring e o Problema da Parada - ComputerphileE aqui estão mais alguns links:
Computando com LadrilhosWikipedia: Van tilesTelhas Wang e máquinas de TuringWang Tiles - 1Aqui estão alguns artigos científicos:
Computando com LadrilhosComputabilidade de inclinações