Sobre essa questão do problema da parada, tem um aspecto que acho interessante (minhas leituras são antigas, então não tenho muita certeza de que lembro tudo direito).
A questão está relacionada ao seguinte: O trabalho original do Turing é sobre computações de números reais, o número computado sendo representado em um sistema simbólico qualquer. Isso significa que, para que o número seja computado, a máquina que faz a computação precisa imprimir toda a representação simbólica do número real, que no caso geral é infinita. Portanto, máquinas que computa corretamente número reais não deve terminar nunca suas computações. Se uma computação termina, ele diz que ela tem um "ciclo", se não termina, que é "livre de ciclos" (cycle-free). Daí que o problema da parada, na formulação original do Turing, é invertido: computação significativa, que produz resultado útil, é computação livre de ciclos, que não pára. E computação não significativa, que não produz resultado útil, é a computação que pára. Em algum momento da história da Teoria da Computação, houve um deslocamento: deixou-se de lado o interesse pela computação de números reais e centrou-se o interesse na computação com números naturais. Consequentemente, computação significativa passou a ser a que termina, caracterizando o resultado como finito. O que eu lembro de não ter conseguido localizar foi o momento em que essa passagem se deu, o autor, texto ou conjunto de textos que explicam ou justificam esse deslocamento. Todos os textos didáticos clássicos (Kleene, Rogers, etc.) já estão nessa nova postura. Mas se a teoria começou mais geral, relativa a números reais, porque se particularizou aos naturais? Somente por simplicidade? Dá para entender que os livros didáticos tenham feito essa opção. Mas a pesquisa como um todo parece que ficou confinada à computação com naturais, a ponto de muita gente pensar que computação com reais é desenvolvimento posterior da teoria. Ou houve mais alguma razão para esse movimento, além da razão didática? Alguém conhece algum texto que mencione isso? Abraços, Rocha > 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 > ------------------------------------- Antônio Carlos da Rocha Costa Centro Politécnico Universidade Católica de Pelotas, RS, Brasil. _______________________________________________ Logica-l mailing list [email protected] http://www.dimap.ufrn.br/cgi-bin/mailman/listinfo/logica-l
