Problema da parada: diferenças entre revisões
Conteúdo apagado Conteúdo adicionado
m Bot: Adicionando: eo:Problemo de halto |
m colocar data, Replaced: {{Wikificar}} → {{Wikificação|data=Fevereiro de 2008}} utilizando AWB |
||
Linha 1:
{{Wikificação|data=Fevereiro de 2008}}
Na [[teoria da computabilidade]] o '''problema da parada''' é um [[problema de decisão]] que pode ser declarado informalmente da seguinte forma:
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
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]]
| |||