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

3 988 bytes adicionados ,  06h35min de 7 de dezembro de 2011
sem resumo de edição
m (link para experimento mental)
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]].
 
== Histórico do problema da parada ==
{{esboço}}
 
* 1900 - [[David Hilbert]] colocou seus 23 problemas (conhecidos como [[problemas de Hilbert]]) no [[Congresso Internacional de Matemáticos]] em Paris. "Desses, o segundo foi o de provar a consistência dos "axiomas de Peano" em que, como ele tinha mostrado, o rigor da matemática o dependia" (Hodges p. 83, commentário do autor em Davis, 1965, p. 108).
* 1920-1921 - [[Emil Post]] explora o problema da parada para a [[máquina de Post]], o considerando como candidato à insolubilidade.(Fonte: ''Absolutely unsolvable problems and relatively undecidable propositions – account of an anticipation'', in Davis, 1965, pp. 340–433.) Sua insolubilidade não foi estabelecida até muito depois, por [[Marvin Minsky]] [1961].
* 1928 - Hilbert reformula seu segundo problema no Congresso Internacional de Bolonha. Hodges afirma que ele colocou três perguntas: i.e. #1: Era a matemática ''completa''? #2: Era a matemática ''consistente''? #3: Era a matemática ''decidível''? (Hodges p.91). A terceira pergunta é conhecida como [[Entscheidungsproblem]] ([[Problema de decisão]]) (Hodges p. 91, Penrose p. 34).
* 1930 - [[Kurt Gödel]] anunciou uma prova como resposta para as duas primeiras questões de Hilbert de 1928 [cf Reid p. 198]. "No começo, ele [Hilbert] estava só com raiva e frustrado, mas depois ele começou a tentar lidar de forma construtiva com o problema... Gödel sentiu - e exprimiu o pensamento em seu trabalho - que seu trabalho não contradiz ponto de vista formalista de Hilbert" (Reid p. 199).
* 1931 — Gödel publica "On Formally Undecidable Propositions of Principia Mathematica and Related Systems I", (reimpresso em Davis, 1965, p. 5ff).
* 19 de abril de 1935 - [[Alonzo Church]] publicou "An Unsolvable Problem of Elementary Number Theory", em que ele identifica o que significa para uma função a ser efetivamente calculável. Tal função terá um algoritmo, e "... o fato de que o algoritmo tenha terminado torna-se efetivamente conhecido ..." (grifo do autor, Davis, 1965, p. 100).
* 1936 - Church publicou a primeira prova que o problema de decisão era insolúvel. [''A Note on the Entscheidungsproblem'', reimpresso em Davis, 1965, p. 110].
* 7 de outubro de 1936 - O artigo de Post ''"Finite Combinatory Processes. Formulation I"'' foi recebido. Post adiciona ao "processo" uma instrução "(C)Pare". Ele chamou esse processo de "Tipo 1 ... se o processo que determina termina para cada problema específico" (Davis, 1965, p. 289ff).
* 1937 - O artigo de [[Alan Turing]] ''"On Computable Numbers With an Application to the Entscheidungsproblem"'' foi impresso (reimpresso em Davis, 1965, p. 115).
* 1939 – [[J. Barkley Rosser]] observa a equivalência essencial do "método eficaz" definido por Gödel, Church e Turing (Rosser em Davis, 1965, p. 273, "Informal Exposition of Proofs of Gödel's Theorem and Church's Theorem").
* 1943 - Em um artigo, [[Stephen Kleene]] afirma que "Na criação de uma teoria completa e algoritmica, o que fazemos é descrever um procedimento ... qual o procedimento necessariamente termina, e de modo que a partir do resultado podemos ler uma resposta definitiva, 'Sim' ou 'Não' à pergunta, 'É o valor do predicado verdade?'".
* 1952 - Kleene (1952) Capítulo XIII ("funções computáveis​​") inclui uma discussão sobre a indecidibilidade do problema da parada para máquinas de Turing e reformula em termos de máquinas que "eventualmente param", ou seja: "... não há algoritmo para decidir se alguma determinada máquina, quando iniciada a partir de qualquer situação, ''eventualmente '''para'''''" (Kleene (1952) p.382).
1952 - "Davis [Martin Davis] pensa que é provável que ele tenha usado pela primeira vez o termo 'problema da parada' em uma série de palestras que ele deu no Laboratório de Sistemas de Controle da Universidade de Illinois em 1952 (carta de Davis para Copeland, 12 de dezembro de 2001.)" (nota de rodapé 61 em Copeland (2004) pp.40ff).
 
 
[[Categoria:Problemas matemáticos]]
9

edições