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 <[email protected]>
> 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 <[email protected]>
>
> 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
>
>
--
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
[email protected]
http://www.dimap.ufrn.br/cgi-bin/mailman/listinfo/logica-l
