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

6 947 bytes adicionados ,  21h28min de 8 de dezembro de 2011
sem resumo de edição
==Introdução==
 
O problema da parada é um problema de decisão sobre as propriedades de programas de computadores em um determinado modelo [[Turing-completo]] de computação, por exemplo todos os programas que podem ser escritos em uma [[linguagem de programação]] que generalizaé geral o suficiente para ser equivalente a uma máquina de Turing. O problema é determinar para uma dada entrada o programa irá parar com ela. Nesta área de trabalho abstrata não há limitações de memória ou tempo necessário para a execução de um programa, pois poderão ser necessários tempo e espaço arbitrários para o programa parar. A questão é se o programa simplesmente poderá parar com uma certa entrada.
 
Por exemplo, em [[pseudocódigo]], o programa:
[[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 pare. 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 algoritmo para, 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 geralmente 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]] param. Entretanto, existem algumas [[heurística]]s que podem ser usadas para tentar-se construir uma prova, que freqüentemente dão seguimento a programas típicos. Este campo de pesquisa é conhecido como [[análise terminatória]] automatizada.
 
Devido ao fato de que a resposta negativa ao problema da parada demonstra que existem problemas que não podem ser resolvidos por máquinas de Turing, a tése de Church-Turing limita o que pode ser atingido por qualquer máquina que implemente métodos efetivos. Porém, nem todas as máquinas imagináveis são sujeitas à tese de Church-Turing (i.e. [[Máquina Oráculo]] não são). Ainda não se pode afirmar se é possível ou não existir um processo físico determinístico que a longo prazo possa contornar uma simulação por máquina de Turing, desta forma, também é relevante saber se este processo hipotético pode ter utilidade na forma de uma máquina calculadora (um hipercomputador) que poderia resolver o problema da parada para uma máquina de Turing, assim como outras coisas. Também se pergunta se qualquer um destes processos físicos desconhecidos estão envolvidos no funcionamento do cérebro humano e se humanos podem resolver o problema da parada.<ref>[[B. Jack Copeland]], ''Computation'' in Luciano Floridi (ed.), ''The Blackwell guide to the philosophy of computing and information'', Wiley-Blackwell, 2004, ISBN 0-631-22919-1, p. 15</ref>
 
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]].
* 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==
 
{{reflist}}
 
==Referências Bibliográficas==
* {{cite book | authorlink = Michael Sipser | last = Sipser | first = Michael | year = 2006 | title = Introdução à Teoria da Computação | edition = Segunda edição | publisher = Cengage | id = ISBN 8522104999 | chapter = Seção 4.2: O problema da parada | pages = 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.
* [[Wiki:HaltingProblem]]
* [[B. Jack Copeland]] ed. (2004), ''The Essential Turing: Seminal Writings in Computing, Logic, Philosophy, Artificial Intelligence, and Artificial Life plus The Secrets of Enigma,'' Clarendon Press (Oxford University Press), Oxford UK, ISBN 0-19-825079-7.
* {{cite book | authorlink = Martin Davis| last=Davis|first=Martin|title= The Undecidable, Basic Papers on Undecidable Propositions, Unsolvable Problems And Computable Functions| publisher= Raven Press| location= New York|year=1965}}. Turing's paper is #3 in this volume. Papers include those by Godel, Church, Rosser, Kleene, and Post.
* {{cite book | authorlink = Martin Davis| last=Davis|first=Martin|title= Computability and Unsolvability|publisher=McGraw-Hill|location=New York|year= 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.
* [[Roger Penrose]], ''The Emperor's New Mind: Concerning computers, Minds and the Laws of Physics'', Oxford University Press, Oxford England, 1990 (with corrections). Cf: Chapter 2, "Algorithms and Turing Machines". An overly-complicated presentation (see Davis's paper for a better model), but a thorough presentation of Turing machines and the halting problem, and Church's Lambda Calculus.
* [[John Hopcroft]] and [[Jeffrey Ullman]], ''Introduction to Automata Theory, Languages and Computation'', Addison-Wesley, Reading Mass, 1979. See Chapter 7 "Turing Machines." A book centered around the machine-interpretation of "languages", NP-Completeness, etc.
* [[Andrew Hodges]], ''Alan Turing: The Enigma'', Simon and Schuster, New York. Cf Chapter "The Spirit of Truth" for a history leading to, and a discussion of, his proof.
* [[Constance Reid]], ''Hilbert'', Copernicus: Springer-Verlag, New York, 1996 (first published 1970). Fascinating history of German mathematics and physics from 1880s through 1930s. Hundreds of names familiar to mathematicians, physicists and engineers appear in its pages. Perhaps marred by no overt references and few footnotes: Reid states her sources were numerous interviews with those who personally knew Hilbert, and Hilbert's letters and papers.
* [[Edward Beltrami]], ''What is Random? Chance and order in mathematics and life'', Copernicus: Springer-Verlag, New York, 1999. Nice, gentle read for the mathematically-inclined non-specialist, puts tougher stuff at the end. Has a Turing-machine model in it. Discusses the [[Chaitin]] contributions.
* [[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.
 
[[Categoria:Problemas matemáticos]]
9

edições