PROBLEMA INDECIDÍVEL

PROBLEMA INDECIDÍVEL

Juraci XXXXXXXX.
Semestre

CIDADE – ESTADO

ANO

PROBLEMA INDECIDÍVEL

Trabalho da matéria Linguagens Formais
Autômatos e Computabilidade XXXXXXXXX apresentado à Universidade Estadual da
Bahia – UNEB.
Orientador: Profº. XXXXXX.

Juraci XXXXXXXX.
Semestre

CIDADE – ESTADO

ANO

INTRODUÇÃO

Muito antes dos computadores modernos terem sido inventados, a teoria da computação já havia sido iniciada e estava em desenvolvimento. Matemáticos de todo o mundo buscavam resolver problemas através de processos com um número finito de passos que pudessem sempre retornar resultados corretos para uma mesma questão.
Apesar de não bem definido durante séculos, o conceito de algoritmo sempre foi utilizado e aperfeiçoado de forma implícita pela comunidade matemática. Durante o Segundo Congresso Internacional de Matemática, realizado em Paris no ano de
1900, David Hilbert apresentou 23 questões não resolvidas pertinentes à toda a sociedade matemática. Nesta lista o décimo problema dizia respeito aos algoritmos, usados ainda sem um conceito concreto, Hilbert requisitou explicitamente um algoritmo para a identificação de existência de raízes inteiras para um polinômio.
Na teoria da computação e na teoria da complexidade computacional, um problema indecidível é um problema de decisão em que é impossível construir um algoritmo que sempre responde corretamente sim ou não. E é sobre esse assunto que sera abordado neste trabalho ―problema indecidível‖.

2

PROBLEMA INDECIDÍVEL

Antes de entrar de vez em ―problema indecidível‖ será explanado um pouco sobre ―Máquina de Turing‖, que um modelo computacional semelhante a um autômato finito, porém muito mais poderoso e com propósito de uso geral. A rigor trata-se de um modelo abstrato de computador, restrito apenas aos aspectos lógicos do funcionamento do mesmo: Capacidade de armazenamento, estados e transições ignorando sua implementação física.
Um problema de decisão é