Pois é, gozado isso; cada caso particular tem um algoritmo - mas em geral não.
2009/6/4 Marcelo Finger <[email protected]> > 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 <http://www.ime.usp.br/%7Emfinger> > >
_______________________________________________ Logica-l mailing list [email protected] http://www.dimap.ufrn.br/cgi-bin/mailman/listinfo/logica-l
