Você pode converter a questão original de Turing na formulação atual. 2009/6/4 <[email protected]>
> 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
