Problema da parada: diferenças entre revisões
Conteúdo apagado Conteúdo adicionado
m Bot: Adicionando: it:Problema della fermata |
|||
Linha 32:
[[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 [[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|heurísticas]] que podem ser usadas para tentar-se construir uma prova, que frequentemente dão
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]].
| |||