Documentação Completa do Simulador URM

Contexto Histórico

A URM foi desenvolvida como uma alternativa mais simples à Máquina de Turing, mas igualmente poderosa em termos de capacidade computacional. Ela surgiu no contexto da teoria da computabilidade, que busca entender os limites fundamentais da computação.

Fundamentos Teóricos

A URM opera baseada em quatro operações fundamentais:

1. Atribuição de zero a um registrador
2. Incremento de um registrador
3. Cópia entre registradores
4. Salto condicional com base na igualdade de registradores

Estas operações, embora simples, são suficientes para implementar qualquer algoritmo computável, conforme estabelecido pela Tese de Church-Turing.

Componentes Fundamentais

Fluxo de Execução

O ciclo de execução da URM segue os seguintes passos:

1. Inicialização:
   • Registradores são definidos com valores iniciais
   • Contador de Programa (PC) é definido como 1
2. Busca:
   • Instrução na posição PC é carregada
3. Decodificação:
   • A instrução é interpretada
4. Execução:
   • A operação é realizada nos registradores especificados
   • PC é actualizado (incrementado ou definido para um novo valor)
5. Terminação: Ocorre quando PC aponta para uma posição fora do programa

Especificação Formal

Instrução	Sintaxe	Semântica	Descrição Formal
Zero	Z(n)	Rn ← 0	Define o registrador n como zero
Sucessor	S(n)	Rn ← Rn + 1	Incrementa o valor no registrador n
Transferência	T(m,n)	Rn ← Rm	Copia valor de Rm para Rn
Salto	J(m,n,p)	PC ← (Rm = Rn) ? p : PC+1	Salta para instrução p se Rm = Rn

Propriedades de Computabilidade

O conjunto de instruções da URM é Turing-completo, o que significa que pode simular qualquer Máquina de Turing e, portanto, computar qualquer função computável.

Esta completude é alcançada através da combinação das quatro instruções básicas, que permitem:

• Implementação de operações aritméticas básicas
• Controle de fluxo condicional e incondicional
• Manipulação de dados em memória
• Implementação de loops e recursão

Hierarquia de Computabilidade

A URM ocupa um lugar fundamental na hierarquia de modelos computacionais:

Limitações Práticas

Apesar de seu poder teórico ilimitado, implementações práticas da URM possuem restrições:

• Limite de registradores: Implementações reais usam um número finito
• Limite de valores: Restrições de tamanho numérico devido a limitações de hardware
• Detecção de loops infinitos: Problema indecidível na teoria, mas detectável pragmaticamente

Arquitetura do Sistema

O simulador foi implementado usando uma arquitectura em três camadas:

Fluxo de Trabalho

Para utilizar eficientemente o simulador, siga este fluxo:

1. Edição:
   • Insira instruções no editor ou selecione um exemplo
   • Defina valores iniciais para os registradores
2. Compilação:
   • Clique em "Compilar" para preparar a execução
   • Verifique erros de sintaxe
3. Execução:
   • Use "Passo a Passo" para execução didática
   • Use "Executar Tudo" para resultados rápidos
   • Monitore registradores e histórico
4. Análise:
   • Revise o histórico de execução
   • Verifique valores finais dos registradores
   • Identifique possíveis erros lógicos

Recursos Avançados

• Histórico de Execução: Registro completo de cada passo com estado dos registradores
• Limite de Segurança: Detecção automática de loops infinitos
• Exemplos Pedagógicos: Programas pré-implementados para funções computáveis
• Responsividade: Interface adaptável a diferentes dispositivos

Adição (R2 + R3 → R1)

I1: J(3,2,5)  // Se R3 = R2, salta para I5 (fim)
I2: S(1)       // Incrementa R1 (resultado)
I3: S(3)       // Incrementa R3 (contador)
I4: J(1,1,1)   // Salta incondicionalmente para I1

Análise de Complexidade: O algoritmo executa em tempo O(n), onde n é o valor em R2.

Multiplicação (R2 * R3 → R1)

I1: Z(4)      // Contador externo = 0
I2: J(3,4,9)  // Se R3 = R4, salta para I9 (fim)
I3: Z(5)      // Contador interno = 0
I4: J(2,5,8)  // Se R2 = R5, salta para I8
I5: S(1)      // Incrementa resultado
I6: S(5)      // Incrementa contador interno
I7: J(1,1,4)  // Volta para I4
I8: S(4)      // Incrementa contador externo
I9: J(1,1,2)  // Volta para I2

Análise de Complexidade: O algoritmo executa em tempo O(m*n), onde m é R3 e n é R2.

Fatorial (R2! → R1)

I1: T(2,3)    // Copia R2 para R3 (contador)
I2: S(1)      // R1 = 1 (inicializa resultado)
I3: J(3,1,9)  // Se contador = 1, salta para I9 (fim)
I4: T(1,4)    // Salva valor atual de R1 em R4
I5: Z(1)      // Zera R1 para multiplicação
I6: J(4,5,9)  // Se R4 = R5 (sempre falso), salta para I9
I7: S(1)      // Adiciona R3 ao resultado (R1 += R3)
I8: S(5)      // Incrementa contador de multiplicação
I9: J(5,4,12) // Se contador = valor original, termina multiplicação
I10: J(1,1,6) // Continua multiplicação
I11: Z(5)     // Reseta contador de multiplicação
I12: S(3, -1) // Decrementa contador principal (pseudo)
I13: J(1,1,3) // Volta para I3

Bibliografia Fundamental

• CUTLAND, N. Computability: An Introduction to Recursive Function Theory. Cambridge University Press, 1980.
• HOPCROFT, J. E.; ULLMAN, J. D. Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, 1979.

Recursos Adicionais

• Implementações alternativas de máquinas URM

Sobre esta Implementação

Este simulador foi desenvolvido com fins exclusivamente educacionais, utilizando as seguintes tecnologias:

• JavaScript (ECMAScript 2022)
• HTML5
• CSS3
• Font Awesome para ícones