Problema da parada: diferenças entre revisões

Origem: Wikipédia, a enciclopédia livre.
Conteúdo apagado Conteúdo adicionado
m Bot: Adicionando: hr:Problem zaustavljanja
SieBot (discussão | contribs)
m Bot: Modificando: nl:Stopprobleem
Linha 53: Linha 53:
[[ja:チューリングマシンの停止問題]]
[[ja:チューリングマシンの停止問題]]
[[ko:정지 문제]]
[[ko:정지 문제]]
[[nl:Beslissingsprobleem]]
[[nl:Stopprobleem]]
[[pl:Problem stopu]]
[[pl:Problem stopu]]
[[ru:Проблема останова]]
[[ru:Проблема останова]]

Revisão das 20h32min de 16 de julho de 2007

Na teoria da computabilidade o problema da parada é um problema de decisão que pode ser declarado informalmente da seguinte forma:

Dado uma descrição de um programa e uma entrada finita, decida se o programa termina de rodar ou rodará indefinidamente, dada essa entrada.

Alan Turing provou em 1936 que um algoritmo genérico para resolver o problema da parada para todos pares programa-entrada possíveis não pode existir. Dizemos que o problema da parada é indecidível nas Máquinas de Turing.

Enunciado Formal

Um problema de decisão é um conjunto de números naturais; o "problema" é determinar se um número em particular pertence ao conjunto.

Dada uma enumeração de Gödel de uma função computável (como os números de descrição de Turing) e uma função de pareamento , o problema da parada é o problema de decisão para o conjunto:

com a i-ésima função computável na enumeração de Gödel .

Embora o conjunto K seja recursivamente enumerável, o problema da parada não é solúvel por uma função computável.

Existem diversas formulações equivalentes do problema da parada; qualquer conjunto cujo grau de insolubilidade da Teoria da Computação e da Complexidade Computacional (no inglês, Turing degree) é o mesmo que o do problema da parada pode ser considerado como tal formulação. Exemplos de tais conjuntos incluem:

Importância e Consequências

A importância histórica do problema da parada reside no fato de que foi um dos primeiros problemas a ser provado indecidível. (A prova de Turing foi lançada em maio de 1936, enquanto a prova de Alonzo Church da indecidibilidade de um problema no cálculo lambda já havia sido lançada em abril de 1936). Subsequentemente, muitos outros problemas foram descritos; o método típico de provar que um problema é indecidível é a técnica de redução. Para isso, o cientista da computação mostra que se uma solução para o novo problema foi encontrada, ela poderia ser usada para decidir um problema indecidível (transformando instâncias do problema indecidível em instâncias do novo problema). Como sabemos de antemão que nenhum método pode decidir o problema antigo, então nenhum método pode decidir o problema novo também.

Uma consequência da indecidibilidade do problema da parada é que não pode existir um algoritmo genérico que decida se um dado enunciado sobre os números naturais é verdadeiro ou falso. A razão para isso é que a proposição que afirma que um certo algoritmo vai parar dado uma certa entrada pode ser convertido em um enunciado equivalente sobre os números naturais. Se nós tivéssemos um algoritmo que pudesse resolver todo enunciado sobre os números naturais, ele certamente poderia resolver tal enunciado; mas isso determinaria se o problema original pára, o que é impossível, já que o problema da parada é indecidível.

Uma outra consequência da indecidibilidade do problema da parada é o Teorema de Rice que enuncia que a verdade de qualquer enunciado não-trivial sobre a função definida por um algoritmo é indecidível. Então, por exemplo, o problema da parada "esse algoritmo parará para a entrada 0" já é indecidível. Perceba que esse teorema considera a função definida pelo algoritmo e não o algoritmo propriamente dito. É, por exemplo, possível decidir se um algoritmo vai parar dentro de 100 passos, mas isso não é um enunciado sobre a função que é definida pelo algoritmo.

Gregory Chaitin definiu uma probabilidade de parada, representada pelo símbolo Ω, um tipo de número real que informalmente representa a probabilidade que um programa produzido aleatoriamente páre. Esses números têm o mesmo grau de insolubilidade da Teoria da Computação e da Complexidade Computacional que o problema da parada. É um número normal e um número transcendente que pode ser definido mas não completamente computado. Isso significa que pode ser provado que não existe algoritmo que produza dígitos de Ω, embora seja possível calcular seus primeiros dígitos nos casos simples.

Enquanto a prova de Turing mostrou que não pode existir algoritmo ou método genérico para determinar se um algoritma pára, instâncias individuais de um problema podem muito bem ser suscetíveis a ataques. Dado um algoritmo específico, um pode geralmente mostrar que ele deve parar para qualquer entrada, e de fato cientistas da computação geralemente fazem isso como parte de uma prova exata. Mas cada prova tem que ser desenvolvida especificamente para o algoritmo em mãos; não existe modo mecânico ou genérico para determinar se algoritmos em Máquinas de Turing páram. Entretanto, existem algumas heurísticas que podem ser usadas para tentar-se construir uma prova, que frequentemente dão seguimento a programas típicos.

A introdução de Turing do modelo de máquina que posteriormente ficou conhecido como Máquinas de Turing, introduzido no artigo, provou-se um modelo muito conveniente para a Teoria da Computação.

Este artigo é um esboço. Você pode ajudar a Wikipédia expandindo-o. Editor: considere marcar com um esboço mais específico.