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

15 bytes adicionados ,  15h18min de 10 de fevereiro de 2008
m
colocar data, Replaced: {{Wikificar}} → {{Wikificação|data=Fevereiro de 2008}} utilizando AWB
m (Bot: Adicionando: eo:Problemo de halto)
m (colocar data, Replaced: {{Wikificar}} → {{Wikificação|data=Fevereiro de 2008}} utilizando AWB)
{{Wikificação|data=Fevereiro de 2008}}
{{Wikificar}}
 
Na [[teoria da computabilidade]] o '''problema da parada''' é um [[problema de decisão]] que pode ser declarado informalmente da seguinte forma:
[[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]]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]].
 
[[Categoria:Lógica]]
 
{{esboço}}
 
[[Categoria:Lógica]]
 
[[ca:Problema de la parada]]
1 137 298

edições