Não, é o halting problem, em ciência da computação, para meaquinas de Turing. Decidir onde há divergências é a questão. O teorema de Turing é:
Para uma máquina de Turing qualquer, e um input arbitrário, não há um algoritmo geral que decida se a máquina para ou não. 2009/6/4 Newton José Vieira <[email protected]> > Prezado Dória, > > Tenho ficado encucado com o que disse, lendo e relendo para ver onde é que > entendi errado... Para mim é óbvio que todo problema de decisão com conjunto > finito de instâncias é decidível (se n é o número de instâncias, um > algoritmo para o problema é aquele que consulta a tabela de respostas > corretas dentre as 2^n tabelas possíveis). Você acha que isso é pouco > percebido em geral ou quiz dizer alguma outra coisa? > > Newton. > > Francisco Antonio Doria escreveu: > >> 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 >> >> > > -- > You don't really understand something if you only understand it in one way. > Marvin Minsky > >
_______________________________________________ Logica-l mailing list [email protected] http://www.dimap.ufrn.br/cgi-bin/mailman/listinfo/logica-l
