Olá Doria e Newton. Vejo uma ligação direta entre o que vocês escreveram.
Criar a teoria PA+{x1,...xn}, no qual x1, ..., xn são as sentenças que PA não prova, é equivalente a inserir "com a mão" as decisões de caso de parada que PA não decide, como os algorítimos que o Newton citou, mas, no caso dele, ele insere *todas* as respostas "com a mão". Ricardo. 2009/6/5 Francisco Antonio Doria <famado...@gmail.com> > Alguma coisa tá complicada na comunicação. > > O que, em princípio, bloqueia algoritmos para resolver o problema da parada > é que existem algoritmos parciais; algoritmos que entram em loop infinito. > > Agora: cada caso onde o algoritmo diverge no modelo standard é dada por uma > sentença ∏1. Logo, se PA for sound, ou PA prova essa sentença x, ou PA + x a > prova, no caso trivialmente. A teoria PA + x é uma teoria que inclui os > teoremas de PA, tem sua mesma linguagem, e a mesma ``força de prova.'' > > Não dá pra enumerar instâncias finitas, pois há algoritmos onde os pontos > de divergência são em número infinito. > > 2009/6/5 Newton José Vieira <nvie...@dcc.ufmg.br> > > 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 <nvie...@dcc.ufmg.br <mailto: >>> nvie...@dcc.ufmg.br>> >>> >>> 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 >>> Logica-l@dimap.ufrn.br <mailto:Logica-l@dimap.ufrn.br> >>> 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 > Logica-l@dimap.ufrn.br > http://www.dimap.ufrn.br/cgi-bin/mailman/listinfo/logica-l > > -- Dr. Ricardo Pereira Tassinari - Departamento de Filosofia UNESP - Faculdade de Filosofia e Ciências - Marília Homepage: http://www.marilia.unesp.br/ricardotassinari
_______________________________________________ Logica-l mailing list Logica-l@dimap.ufrn.br http://www.dimap.ufrn.br/cgi-bin/mailman/listinfo/logica-l