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

2 641 bytes adicionados ,  20h58min de 7 de dezembro de 2011
sem resumo de edição
m (pequeno ajuste)
 
[[Alan Turing]] provou em 1936 que um [[algoritmo]] genérico para resolver o problema da parada para ''todos'' pares programa-entrada possíveis não pode existir. Dizemos que o problema da parada é ''indecidível'' nas [[Máquina de Turing|Máquinas de Turing]].
 
==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 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:
 
:<tt>enquanto Verdadeiro: continue</tt>
 
Não para, pelo contrário, entra em loop infinito. Por outro lado, o programa:
 
:<tt>imprimir "Hello World!"</tt>
 
Pára muito rapidamente.
 
Um programa mais complexo pode ser mais difícil de se analisar. O programa pode rodar por um tempo fixo e se ele não parar, não há um jeito de saber se o programa irá parar eventualmente ou se ele irá continuar rodando para sempre. Turing provou que não há um algoritmo que pode ser aplicado a qualquer programa arbitrário, com uma entrada, para decidir se o programa pára ou não com esta entrada.
 
==Enunciado Informal==
 
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]].
 
==Representando o problema da parada como um conjunto==
 
A representação convencional dos problemas de decisão é o conjunto de objectos que possuem a propriedade em questão. O “conjunto da parada”
: ''K'' := { (''i'', ''x'') | programa ''i'' eventualmente irá parar com a entrada ''x''}
Representa o problema da parada.
Este conjunto é [[Conjuntos recursivamente enumeráveis|recursivamente enumerável]], o que significa que há uma função computável que lista todos os pares (''i'',&nbsp;''x'') contidos no conjunto. Porém, o complemento deste conjunto não é recursivamente enumerável.
Existem muitas formulações equivalentes do problema da parada. Qualquer conjunto no qual o [[Grau de Turing]] é igual ao do problema da parada é uma dessas formulações. Exemplos:
*{ ''i'' | programa ''i'' eventualmente para quando a entrada é 0 }
*{ ''i'' | há uma entrada''x'' para que um dado programa ''i'' eventualmente pare com a entrada ''x'' }.
 
 
== Histórico do problema da parada ==
* 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).
 
==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 }}
 
[[Categoria:Problemas matemáticos]]
9

edições