Skip to content

lhleonardo/ufla-teoria-computacao-trabalho_final

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

9 Commits
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

Problema da parada

Heurística para solução do problema da parada

O problema

O problema da parada trata-se de um problema de decisão presente no universo das máquinas de Turing. Seja uma máquina/algoritmo qualquer e uma entrada para esta máquina, é impossível dizer se essa máquina pára para esta entrada.

Ideia

Desenvolver um algoritmo capaz de deduzir se uma máquina entra em loop infinito (fica processando infinitamente) a partir da identificação de padrões ocorridos.

Algoritmo

Esta solução foi feita na linguagem Python. A representação de uma máquina de turing qualquer foi realizada seguindo as boas práticas de Programação Orientada a Objetos.

Trata-se, neste trabalho, de uma Máquina de Turing com 1 (uma) fita.

Execução

Este trabalho necessita que um interpretador de comandos Python esteja instalado.

Para execução da lógica do trabalho, espera-se um arquivo de entrada que contenha uma representação da Máquina de Turing no formato R(M), seguido da entrada que será executada pela máquina informada anteriormente.

Exemplo de utilização (utilizando o arquivo de entrada entrada.txt): > python main.py entrada.txt

O arquivo main.py encontra-se na raiz do projeto.

Autores

Trabalho realizado por:

  • Guilherme Barbosa
  • Guilherme Melo
  • Leonardo Braz
  • Wagner Moretti

Sob orientação do prof. Dr. Erick Galani Maziero

Releases

No releases published

Packages

No packages published

Languages