Oi Dória. Claro que eu sei do que v está falando. Só estava levantando um ponto que eu acho curioso.
[]s Marcelo 2009/5/30 Francisco Antonio Doria <[email protected]> > 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> >> >> > -- 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
_______________________________________________ Logica-l mailing list [email protected] http://www.dimap.ufrn.br/cgi-bin/mailman/listinfo/logica-l
