10

Minha pergunta vem da seguinte implementação da Regra 110 em CSS (Isso! Em CSS!).

A dúvida vem da definição da completude de Turing, que diz que uma sistema é Turing-completo se for capaz de resolver qualquer problema computacional. No entanto a Regra 110 é usada para testar essa hipótese e o CSS, aparentemente, passou.

Mas, eu não consigo fazer tanta coisa com CSS (talvez porque meu conhecimento seja limitado... nesse caso, seria extremamente limitado).

2 Respostas 2

1

Não, há também o Jogo da Vida que pode ser utilizado para saber se o sistema é turing-completo.

Pode ser uma boa forma de identificar uma linguagem como turing-completa utilizando a Regra 110, devido a sua universalidade.

Por exemplo se temos uma função computacional S que para programa P recebe uma entrada X S(P,X) então P irá parar quando chegar no X, e se S(P,X) parar então o seu resultado sempre será similar ao de P sobre X. Regra 110 - Inglês

Já as regras 30 e 90 não sabemos se elas são universal ou não.

1
  • 1
    Obrigado pelo comentário, mas eu refiz minha pergunta, pois não é bem a resposta que eu espero. Eu gostaria de saber mais sobre a Regra de um ponto de vista prático. 3/12/2015 às 10:12
1

Eu gostaria de saber mais sobre a Regra de um ponto de vista prático.

Bem, o Autômato 110 é, resumidamente, um autômato celular com regras bastante simples, e mesmo assim ele é bastante versátil - afinal, ele é Turing-completo. Com isso, a Turing-completude de um dado sistema pode ser demonstrada simplesmente emulando um autômato 110 nele. Neste sentido, não existe nada profundamente especial neste autômato.

É como perguntar "será que eu consigo construir um Assembler para a arquitetura x86 usando essa linguagem de programação?". Só que o manual do x86 é enorme - mais de duas mil páginas! Então é (teoricamente) mais fácil usar uma linguagem mais simples.

Uma forte candidata é a linguagem Brainfuck. Tentemos então reformular hipoteticamente sua pergunta em Brainfuck:

Minha pergunta vem da seguinte implementação da Regra 110 em Brainfuck (Sim, em brainfuck!).

A dúvida vem da definição da completude de Turing, que diz que uma sistema é Turing-completo se for capaz de resolver qualquer problema computacional. No entanto a Regra 110 é usada para testar essa hipótese e o Brainfuck, aparentemente, passou.

Mas, eu não consigo fazer tanta coisa com Brainfuck (talvez porque meu conhecimento seja limitado... nesse caso, seria extremamente limitado).

Olhando assim, não me parece um profundo demérito não saber programar em Brainfuck. Pelo contrário, é mais fácil construir um programa que transpile C para Brainfuck. Eu até hoje não entendo completamente esse Quicksort feito em Brainfuck!.

O meu ponto de vista prático sobre isso é: "Bela curiosidade, mas nunca na vida vou usar isso". CSS vai continuar no seu nicho de configuração de páginas Web, e seguramente não veremos um sistema operacional feito em CSS tão cedo.

Indo direto à sua pergunta, a ideia é que a Regra 110 descreve uma máquina com poucas regras e de fácil entendimento, portanto a regra pode ser usada como um teste das capacidades de uma linguagem.

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .