PROBLEMA INDECIDÍVEL

2045 palavras 9 páginas
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 é

Relacionados

  • Redutibilidade - Linguagens formais
    920 palavras | 4 páginas
  • Decidibilidade
    1816 palavras | 8 páginas
  • UMA VIAGEM INFORMAL AO  TEOREMA DE GÖDEL 
    7486 palavras | 30 páginas
  • Decidibilida
    281 palavras | 2 páginas
  • Teoria da Computaçao
    1149 palavras | 5 páginas
  • Lógica Clássica
    1512 palavras | 7 páginas
  • Lista 3 Teoria Da Computa O Respondida
    1053 palavras | 5 páginas
  • toeoria
    501 palavras | 3 páginas
  • Caralho de asa
    946 palavras | 4 páginas
  • Teoria da Computação
    2030 palavras | 9 páginas