Diferenças entre edições de "Problema da parada"

1 byte removido ,  13h23min de 15 de março de 2008
sem resumo de edição
m (colocar data, Replaced: {{Wikificar}} → {{Wikificação|data=Fevereiro de 2008}} utilizando AWB)
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árepare. 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 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áquina de Turing|Máquinas de Turing]] páram. Entretanto, existem algumas [[heurística]]s que podem ser usadas para tentar-se construir uma prova, que frequentemente dão seguimento a programas típicos.
17

edições