Na verdade, a gente faz o algoritmo `in abstracto.' Mas não pode juntar tudo porque significaria usar uma regra infinitária. O que acontece é que, implicitamente no algoritmo tem uma função que, nos casos particulares, é algoritmica. Mas juntou tudo, vira um monstro feito o Busy Beaver.
2009/6/4 Francisco Antonio Doria <[email protected]> > 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
