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

44 bytes removidos ,  23h19min de 19 de março de 2011
m
artigo já wikificado...
(estava errado)
m (artigo já wikificado...)
{{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:
 
*<math>\{ i \mid \exists n ( \varphi_i(n) \ \mathrm{para})\}</math>
 
==Importância e Consequênciasconsequências==
 
==Importância e Consequências==
 
A importância histórica do problema da parada reside no fato de que foi um dos primeiros problemas a ser provado [[indecidível]]. (A prova de Turing foi lançada em maio de 1936, enquanto a prova de [[Alonzo Church]] da indecidibilidade de um problema no [[cálculo lambda]] já havia sido lançada em abril de 1936). Subsequentemente, muitos outros problemas foram descritos; o método típico de provar que um problema é indecidível é a técnica de redução. Para isso, o cientista da computação mostra que se uma solução para o novo problema foi encontrada, ela poderia ser usada para decidir um problema indecidível (transformando instâncias do problema indecidível em instâncias do novo problema). Como sabemos de antemão que nenhum método pode decidir o problema antigo, então nenhum método pode decidir o problema novo também.
 
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]].
 
 
{{esboço}}
14 611

edições