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

2 bytes removidos ,  01h05min de 11 de dezembro de 2008
m (Revertidas edições por 143.107.183.130 para a última versão por VolkovBot (Huggle))
[[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 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 geralementegeralmente 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áramparam. 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.
 
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]].
Utilizador anónimo