Mas tô falando in abstracto, Marcelo. 2009/5/30 Marcelo Finger <[email protected]>
> O que poucas pessoas parecem perceber é que pela segunda lei da > termodinâmica, todo programa que rode em qualquer computador real > eventualmente termina; possivelmente, sem dar resposta nenhuma. Portanto, > via Física, o problema da parada na prática é decidível, e a decisão é > sempre sim. > > Neste caso, o que é indecidível é prever qto tempo um programa demora pra > parar. E se ele dará resposta ou não antes de parar. > > 2009/5/30 Francisco Antonio Doria <[email protected]> > >> Não existe nenhum algoritmo capaz de resolver todas as instâncias do >> Problema da Parada, mas - fato pouco percebido - é que, dado um conjunto >> finito de tais instâncias, podemos nesse caso particular escrever sempre um >> algoritmo que resolva o problema específico. Não dá é para fazer um >> algoritmo global; entre outras coisas porque a complexidade computacional >> cresce sem limite. >> >> _______________________________________________ >> Logica-l mailing list >> [email protected] >> http://www.dimap.ufrn.br/cgi-bin/mailman/listinfo/logica-l >> >> > > > -- > Marcelo Finger > Departamento de Ciencia da Computacao > Instituto de Matematica e Estatistica > Universidade de Sao Paulo > Rua do Matao, 1010 > 05508-090 Sao Paulo, SP Brazil > Tel: +55 11 3091-9688, 3091-6135, 3091-6134 (fax) > http://www.ime.usp.br/~mfinger <http://www.ime.usp.br/%7Emfinger> > >
_______________________________________________ Logica-l mailing list [email protected] http://www.dimap.ufrn.br/cgi-bin/mailman/listinfo/logica-l
