Decidibilidade

Disponível somente no TrabalhosFeitos
  • Páginas : 8 (1816 palavras )
  • Download(s) : 0
  • Publicado : 18 de março de 2013
Ler documento completo
Amostra do texto
[pic]












Teoria da Computação

Decidibilidade










Grupo: Marcello Almeida
Victor Lélis

1. 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 passosque pudessem sempre retornar resultados corretos para uma mesma questão. Apesar de não ter sido 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.
Mesmo com o problema não resolvido (ou provado que não pode ser resolvido), um grande avanço permitiu uma melhor análise do mesmo: a publicação dachamada Tese de Church-Turing, em 1936. O artigo definia precisamente a noção de algoritmo que se fazia ausente até então e estava inviabilizando a continuidade do estudo na área.
A Tese de Chuch-Turing afirma que, possuindo tempo e capacidade de espaço suficiente, qualquer função que pode ser computada naturalmente pode ser computada através de um algoritmo em um computador. Através disso épossível perceber que até o mais simples computador (em questão de velocidade e tamanho de memória) , possui teoricamente poder equivalente que um outro qualquer. Para a realização da tese o importante conceito de Máquina de Turing foi definido e associado com algoritmos, da forma “um algoritmo é um processo descrito por uma Máquina de Turing” (Gurevich 2000).2. Decidibilidade

Entende-se por decidibilidade, o estudo da capacidade de solução de algumas classes de problemas através de certos modelos computacionais.
A investigação da solubilidade desses problemas ajuda a evitar a pesquisa de soluções inexistentes, bem como a simplificação do problema original, fazendo com que busquemos novas perspectivas computacionais.Um problema é dito decidível ou indecidível levando-se em conta determinado modelo computacional, ou seja, um problema decidível utilizando Máquinas de Turing pode não ser decidível quando se tenta resolver com Autômatos Finitos Determinísticos.
Problemas decidíveis são aqueles que retornam, para qualquer entrada pertencente ao seu domínio, um valor satisfatório (sim ou não), ou seja, se e somentese, existe um algoritmo que o resolva, podendo ser escrita uma função recursiva para solucioná-la e essa função sempre termina.
Problemas semi decidíveis são assim caracterizados por pararem no caso de respostas positivas, mas poderem entrar em loop quando a resposta for negativa, ou seja, A solução não é precisa no caso de uma entrada que deva retornar uma resposta negativa.
A classe dosproblemas indecidíveis abrange aqueles desafios para os quais não existe um algoritmo que seja capaz de resolvê-los.

1. Linguagens Decidíveis

Uma linguagem decidível é uma linguagem em que existe uma máquina de Turing que, quando recebe uma cadeia de entrada aceita-a ou à rejeita, dessa forma, a máquina de Turing sempre a decide.

Exemplo:
Neste exemplo será testado o problema deaceitação referente a um AFD, ou seja, se o mesmo aceita uma cadeia w. Para isso será estabelecida uma linguagem Aafd e sua decibilidade é constatada após o processo, ela esta definida como:

Aafd = { | B é um AFD que aceita a cadeia de entrada w}



Algoritmo para a máquina de Turing M:
1- Simule o autômato B com respeito à entrada w
2- Verifique se ela termina em um estado...
tracking img