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

92 bytes adicionados ,  11h47min de 29 de novembro de 2018
m
correção de texto extra em parâmetro página e edição
(→‎Introdução: "Para" não leva mais acento)
m (correção de texto extra em parâmetro página e edição)
== Histórico do problema da parada ==
 
* 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 algorítmica, 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).
 
==Notas==
 
==Referências Bibliográficas==
* {{citar livro|autorlink = Michael Sipser |último = Sipser |primeiro = Michael |ano= 2006 |título= Introdução à Teoria da Computação |edição= Segunda edição |publicado= Cengage |isbn= 8522104999 |capítulo= Seção 4.2: O problema da parada |páginas= pp.182–192 }}
* [[Alan Turing]], ''On computable numbers, with an application to the Entscheidungsproblem'', Proceedings of the London Mathematical Society, Series 2, 42 (1936), pp 230–265. [http://www.turingarchive.org/browse.php/B/12 online version] This is the epochal paper where Turing defines [[Turing machine]]s, formulates the halting problem, and shows that it (as well as the [[Entscheidungsproblem]]) is unsolvable.
* [[c2:HaltingProblem]]
* {{citar livro|autorlink = Martin Davis|último =Davis|primeiro =Martin|título= The Undecidable, Basic Papers on Undecidable Propositions, Unsolvable Problems And Computable Functions|publicado= Raven Press|local= New York|ano=1965}}. Turing's paper is #3 in this volume. Papers include those by Godel, Church, Rosser, Kleene, and Post.
* {{citar livro|autorlink = Martin Davis|último =Davis|primeiro =Martin|título= Computability and Unsolvability|publicado=McGraw-Hill|local=New York|ano= 1958}}.
* [[Alfred North Whitehead]] and [[Bertrand Russell]], ''Principia Mathematica'' to *56, Cambridge at the University Press, 1962. Re: the problem of paradoxes, the authors discuss the problem of a set not be an object in any of its "determining functions", in particular "Introduction, Chap. 1 p. 24 "...difficulties which arise in formal logic", and Chap. 2.I. "The Vicious-Circle Principle" p. 37ff, and Chap. 2.VIII. "The Contradictions" p.  60ff.
* [[Martin Davis]], "What is a computation", in ''Mathematics Today'', Lynn Arthur Steen, Vintage Books (Random House), 1980. A wonderful little paper, perhaps the best ever written about Turing Machines for the non-specialist. Davis reduces the Turing Machine to a far-simpler model based on Post's model of a computation. Discusses [[Chaitin]] proof. Includes little biographies of [[Emil Post]], [[Julia Robinson]].
* [[Marvin Minsky]], ''Computation, Finite and Infinite Machines'', Prentice-Hall, Inc., N.J., 1967. See chapter 8, Section 8.2 "The Unsolvability of the Halting Problem." Excellent, i.e. readable, sometimes fun. A classic.
* [[Ernest Nagel]] and [[James R. Newman]], ''Godel’s Proof'', New York University Press, 1958. Wonderful writing about a very difficult subject. For the mathematically-inclined non-specialist. Discusses [[Gentzen]]'s proof on pages 96–97 and footnotes. Appendices discuss the [[Peano Axioms]] briefly, gently introduce readers to formal logic.
* [[Taylor Booth]], ''Sequential Machines and Automata Theory'', Wiley, New York, 1967. Cf Chapter 9, Turing Machines. Difficult book, meant for electrical engineers and technical specialists. Discusses recursion, partial-recursion with reference to Turing Machines, halting problem. Has a [[Turing Machine]] model in it. References at end of Chapter 9 catch most of the older books (i.e. 1952 until 1967 including authors Martin Davis, F. C. Hennie, H. Hermes, S. C. Kleene, M. Minsky, T. Rado) and various technical papers. See note under Busy-Beaver Programs.
* [[Busy Beaver]] Programs are described in Scientific American, August 1984, also March 1985 p.  23. A reference in Booth attributes them to Rado, T.(1962), On non-computable functions, Bell Systems Tech. J. 41. Booth also defines Rado's Busy Beaver Problem in problems 3, 4, 5, 6 of Chapter 9, p.  396.
* [[David Bolter]], ''Turing’s Man: Western Culture in the Computer Age'', The University of North Carolina Press, Chapel Hill, 1984. For the general reader. May be dated. Has yet another (very simple) Turing Machine model in it.
* [[Stephen Kleene]], ''Introduction to Metamathematics'', North-Holland, 1952. Chapter XIII ("Computable Functions") includes a discussion of the unsolvability of the halting problem for Turing machines. In a departure from Turing's terminology of circle-free nonhalting machines, Kleene refers instead to machines that "stop", i.e. halt.