Mathematica Eterna
Acesso livre

Abstrato

Engenharia inversa de máquinas de Turing e insights sobre a conjetura de Collatz.

John Nixon

Neste artigo, estendi o meu trabalho anterior [3] sobre pequenas Máquinas de Turing (TMs), desenvolvendo um método para obter definições recursivas das regras regulares irredutíveis (TIR) ​​para uma TM quando não se conseguem obter fórmulas explícitas para as mesmas. Isto foi ilustrado por dois exemplos. O primeiro exemplo foi escolhido aleatoriamente e o segundo exemplo foi desenhado para simular a conjetura de Collatz. A análise desta MT com base na sua TIR sugeriu novas abordagens que poderiam servir de base para uma prova desta conjetura. O método envolve a execução da TM de trás para a frente a partir de um conjunto de configurações (CS). Isto em geral produz uma árvore de CSs em cada etapa. O objetivo é encontrar CS’s y que sejam alcançáveis ​​a partir de um CS x que simplesmente especifique o símbolo a ler e o estado da máquina. Isto significa que seguindo o cálculo a partir de x adicionando alguns símbolos quando necessário no ponteiro, pode-se atingir o CS y. Estes CS constituem a base dos LHS da TIR.