Problema da parada: diferenças entre revisões
Conteúdo apagado Conteúdo adicionado
m Bot: Adicionando: sk:Problém zastavenia |
|||
Linha 5:
:''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
==Enunciado Informal==
Linha 22:
*<math>\{ i \mid \exists n ( \varphi_i(n) \ \mathrm{para})\}</math>
==Importância e
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úmero natural|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
[[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 pare. 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 [[número definível|definido]] mas não completamente [[número computável|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
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]].
{{esboço}}
|