Tentei procurar no google por explicações, mas a maioria dos links diz apenas coisas como "O FRACTRAN está completo. Como exemplo, vejamos a multiplicação".
Lembro-me de ver uma postagem no fórum do xkcd dizer que o FRACTRAN ajudou o pôster a entender a Turing Completeness. Estou procurando uma explicação intuitiva sobre por que esse esolang é Turing completo, pois não é muito óbvio olhar para a mecânica da linguagem.
turing-completeness
mosquito
fonte
fonte
Respostas:
Para que uma linguagem imperativa seja Turing completa, ela deve ter:
FRACTRAN é uma linguagem composta de uma série de frações que armazena seus dados nos expoentes dos números primos.
Digamos que você queira adicionar dois números: 2 a 3 b torna-se 5 ab
Esse é um programa FRACTRAN para fazer isso acima da mudança.
Você começa com um número como 72 (2 3 3 2 ). O programa avança até encontrar um número que, quando multiplicado pela instrução, é outro número inteiro (nenhum resto é permitido).
72
seguirá em frente até chegar11/2
. Em seguida, dividirá o número por2
e multiplicará por11
(o poder em 11 é uma variável). Isso dá396
.396
é divisível por 33 (reduzindo a potência 3 e a 11) e multiplicado por 455 (incrementando as variáveis 5, 7 e 13). E assim por diante. A descrição completa deste programa e sua tabela de estados podem ser lidas na página da FRACTRAN , incluindo um gif animado muito bom do programa acima.Outros materiais FRACTRAN no Stack Exchange que abordam a integridade de Turing podem ser encontrados em: Converter Fractran em Brainfuck (ok, esse é um uso realmente produtivo do tempo)
Parte do truque aqui (e isso começa desviando em teoria) é que por trás das cenas, esta é uma máquina de registo Minsky para o qual foi provado que certas fitas (programas) são Turing máquinas IF a fita é representado como um número de Gödel que é exatamente qual é o número FRACTRAN (na página da wikipedia vinculada):
Então, temos loops condicionais, variáveis arbitrárias armazenadas como números de Gödel, temos uma máquina de Turing.
Alguma outra leitura divertida que toca a natureza Collatz, como a natureza do FRACTRAN, pode ser lida em Can't Decide? Indeciso! que relacionam a conjectura de Collatz ao FRACTRAN e o problema da parada.
FRACTRAN é um pouco difícil de entender.
Considere o programa algo como:
Neste, cada bloco tem o formato:
A primeira instrução do programa de multiplicação acima:
Seria escrito desta forma como:
E assim você pode ver claramente o armazenamento de dados e as construções de loop necessárias para a integridade de Turing. É muito rudimentar, mas existe e funciona como uma simples máquina de registro - mas é tudo o que você realmente precisa para fazer.
Ainda não está convencido?
Isso se baseia amplamente em uma palestra de Dimitri Hendricks sobre Modelos de Computação
Isso requer o programa muito simples
(2/3)
que é um somador (2 a 3 b -> 3 a + b ). Mas é destrutivo - o valor em 2 é limpo como parte do processo.Vamos escrever um FRACTRAN de nível superior que facilita a não destruição.
O programa original pode ser considerado como:
Em F 2 , pode-se especificar 'funções' de um tipo.
Para converter um programa F 2 (P) em um programa FRACTRAN padrão, é necessário:
torna-se:
O que isso fez é usar os primos p, q, re es para armazenar o estado do programa.
E então temos a máquina de registro ... ela tem um número finito de registros que armazenam números grandes arbitrários e duas instruções:
Esta máquina registradora foi mostrada como Turing completa.
Em seguida, ele mostra o processo em vários slides da compilação de um programa de máquina de registro em um programa FRACTRAN como parte de um processo mecânico.
Basicamente:
E, portanto, devido à equivalência entre esses dois modelos de computação, o FRACTRAN é Turing completo.
Btw, se você realmente quer ter uma ideia, leia Code Golf: Fractran, no qual algumas pessoas escreveram um programa FRACTRAN para executar outro programa FRACTRAN.
fonte