Dória e amigos, Entendi perfeitamente que estava falando do problema da parada.
Seja P um conjunto finito de programas e E um conjunto finito de entradas possíveis para programas. Então o problema de determinar se o programa p pára se sua entrada for x, para qualquer par (p,x) em P x E é *obviamente* decidível: se P x E tem n elementos, existem 2^n tabelas de n respostas sim/não, apenas uma delas com todas as respostas corretas e cada uma das restantes 2^n-1 tabelas com alguma resposta incorreta. Assim, dos 2^n algoritmos baseados no uso das tabelas para resolver o problema, apenas um é correto; os outros 2^n-1 são incorretos. O algoritmo correto existe, mesmo que não se saiba qual é. Costumo brincar com os alunos que o seguinte problema é decidível (supondo que a resposta só possa ser sim ou não): *Deus existe?* . Como ele tem apenas uma instância, existem 21=2 algoritmos: A1: retorne sim. A2: retorne não. Embora não saibamos qual, um deles é o correto! Em resumo: qualquer problema de decisão constituído de um conjunto finito de instâncias (incluindo qualquer subconjunto finito de instâncias do problema da parada) é decidível. Ou seja, o fato de um subconjunto *finito* de instâncias do problema da parada ser decidível não depende do fato de que ele seja constituído de instâncias do *problema da parada*! Peço desculpas se não fui claro da outra vez ou se continuo sem entender o que disse... Newton. Francisco Antonio Doria escreveu: > 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] > <mailto:[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] <mailto:[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 > > -- 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
