Basta codificar em binário e considerar a ( incomputável) mais curta codificação possível.
Sent from my iPhone On 07/03/2013, at 16:42, Tony Marmo <[email protected]> wrote: > Caro João, > > Tenho muita simpatia pela pergunta, mas é aquela velha história do pescador > que se encanta mais pela rede do que pelo mar. Contar o número de regras > usadas e de passos pode ser um meio para medir uma derivação, porém será um > entre vários meios de medição. E segundo, para medir será preciso > considerar sempre a menor derivação "correta" (latu sensu) dentre as > possíveis derivações. > > Na verdade a minha simpatia pela pergunta deve-se a que ela não se limita a > dedução natural, mas traduz a ideia de que a lógica sempre trabalha com > economia ou simplicidade, que essas são características fundamentais da > disciplina. > > > Em 6 de março de 2013 19:38, Joao Marcos <[email protected]> escreveu: > >> Gostaria de fazer uma consulta simples entre os colegas com mais >> intuição do que eu sobre este assunto. >> >> Um aluno me perguntou como poderia fazer para "comparar o nível de >> dificuldade de duas derivações", em dedução natural. A gente faz em >> sala de aula aquelas asserções ingênuas, do tipo "se você usou a regra >> do absurdo clássico, trata-se de uma derivação não trivial", "se você >> usou regras com descarte, a derivação é potencialmente mais complexa", >> "se você precisou usar lemas, a derivação não é tão básica assim", e >> até "se você construiu sua derivação de forma construtiva, ela pode >> até ter custado mais, mas é mais confiável"... >> >> Pois bem, minha primeira sugestão ao aluno foi que comparasse o nível >> de dificuldade de duas derivações executando dois passos: primeiro, >> converta estas derivações para uma forma *normalizada*; em seguida, >> conte o número de nós destas versões normalizadas, e o número de >> aplicações da regra do absurdo clássico. A Valeria me chamou a >> atenção em privado para a necessidade de considerar também outras >> variáveis, como o numero de regras usadas, e não somente o numero de >> regras do absurdo. >> >> E o que acham os colegas? Como vocês comparariam, em princípio, o >> *nível de dificuldade* de duas derivações, digamos, em dedução >> natural? >> >> Abraços, >> Joao Marcos >> >> -- >> http://sequiturquodlibet.googlepages.com/ >> _______________________________________________ >> Logica-l mailing list >> [email protected] >> http://www.dimap.ufrn.br/cgi-bin/mailman/listinfo/logica-l > _______________________________________________ > Logica-l mailing list > [email protected] > http://www.dimap.ufrn.br/cgi-bin/mailman/listinfo/logica-l _______________________________________________ Logica-l mailing list [email protected] http://www.dimap.ufrn.br/cgi-bin/mailman/listinfo/logica-l
