Indecidíveis

[Vilya]

Está claro que a base da ciência é a lógica, pois esta é a ferramenta que nos permite concluir (ou até mesmo prever) a partir dos fatos observados, seja em experiências num laboratório da NASA, seja num pomar.

Alguns tópicos daqui do clube já falaram sobre três dos aspectos mais problemáticos encontrados no estudo da lógica: as falácias, os paradoxos e a questão levantada pelo Engethor sobre dedução x opinião.

O objetivo desse tópico é popularizar um quarto tipo de "patologia lógica" os chamados indecidíveis.

Inicialmente vamos compreender ao que a lógica se propõe.

A lógica não é uma ferramenta mágica, muito menos perfeita, e levou muito tempo para tomar a forma que tem hoje. Nesse processo sofreu inúmeras modificações, sempre tentando se adaptar perante aos problemas que só eram percebidos após o seu uso. Basicmente ela foi construída em sistema de tentativa e erro.

A lógica se compõe de duas coisas:

1°. Os axiomas:
São as premissas, os fatos ou as hipóteses, os quais são assumidos como verdades no início da argumentação.
Ex. Vamos assumir que seja verdade que "o céu é azul claro". A partir dessa hipótese se eu disser que "o céu é verde", então eu estarei falando uma mentira. Agora, se minha premissa fosse que "o céu é verde", a frase acima seria verdadeira.
O que eu quero salientar é que os axiomas são fundamentais para as conclusões. O maior problema é escolhe-los de modo adequado para que não cheguemos a conclusões como por exemplo o céu ser verde.

2°. Os argumentos válidos:
São eles que determinam que tipo de raciocínio podemos fazer se nosso objetivo for encontrar a verdade. As falácias são exemplos de argumentos que podem nos conduzir a erros ou a falsidades.

A logica se propõe a saber se uma afirmação é falsa ou verdadeira. Para isso ela se utiliza apenas dos axiomas e dos argumentos válidos.

Agora, o que vem a ser um indecidível ?

Um indecidível é uma afirmação que não podemos determinar se é falsa ou verdadeira, independentemente dos argumentos que tentemos usar.
Ex. Suponhamos que o nosso único e exclusivo axioma seja "o céu é azul", portanto não sabemos nada além do fato do céu ser azul. O único fato que estamos autorizados a usar é este e para sabermos se outra afirmação é ou não verdadeira é apenas nele que poderemos basear nosso raciocínio. Assim, a afirmação "o céu é verde" é falsa, a afirmação "o céu não é laranja" é verdadeira, mas a afirmação "o céu tem estrelas" é um indecidível, pois não há meios de concluir a existência de estrelas no céu usando exclusivamente a informação "o céu é azul".

A esperança dos lógicistas, dos filósofos, dos matemáticos e dos cientistas em geral era encontrar um número de axiômas suficientes de modo a não ocorrerem indecidíveis, mas em meados do século XX essa esperança foi por água abaixo. Gödel provou que não importa quais sejam os axiomas, sempre há afirmações indecidíveis.

Esta descoberta foi a maior revolução nas bases da ciênca e da filosofia ocorrida no século XX, mas vou deixar as implicações desse fato para um post futuro.

Há uma página de um professor amigo meu que trata deste assunto, além de trazer várias informações interessantes (e de fácil compreenção) a quem quiser saber mais sobre divulgação científica, lógica, paradoxos, indecidíveis e Gödel.

http://www.dmm.im.ufrj.br/projeto/diversos/godel.html

 

[Fox]

Muito bom isso. É algo que até recentemente eu enfrentei em discussões.

Nem sempre as indecidíveis são intencionais em conversas, mas já vi vários usando delas como escudos contra a argumentação alheia.

Tanto no fórum como fora dele. Algumas vezes pra contra-argumentar de forma "decisiva" ou pra encerrar uma discussão com a qual ele não consegue lidar.

Acho isso muito irritante.

 

[Vilya]

Como foi citado no meu post anterior, Gödel provou que sempre existem indecidíveis, ou seja, sempre corremos o risco de esbarrar com uma afirmação que não poderemos decidir se é verdadeira ou falsa a partir da lógica.

Isso causou um tremendo reboliço no meio acadêmico. Os logicistas viram cair por terra a sua tentativa de construir uma lógica perfeita. Eles queriam fixar um conjunto de axiomas (premissas) que desse cabo de deduzir logicamente se qualquer afirmação era verdadeira ou falsa, mas Gödel provou que mesmo com um conjunto infinito ( !!!) de premissas, ainda assim, existiriam questões indecidíveis.

A primeira reação foi contestar a validade de sua prova. Mas ela é perfeita. Em seguida partiram para encarar o problema de frente. E agora, já que os indecidíveis são inevitáveis, o que faremos com eles?

Poderiam abandonar totalmente o modelo sob o qual a lógica foi construída ou remendar a lógica a cada indecidível que aparecesse. Como ninguém estava disposto a abandonar um trabalho de séculos de pesquisa, e que estava longe de ser ruim, ficaram com a segunda alternativa.

A partir daí, sempre que um indecidível era identificado tentava-se buscar, se possível, outras argumentações que não precisassem dele. Muitas vezes isso deu certo e os logicistas meio que faziam vistas grossas para o indecidível e procuravam outro caminho, mais longo é verdade, para concluir suas argumentações. Mas em alguns casos o indecidível crucial na argumentação e sem ele nunca poderiam concluir o raciocínio. E neste caso, o que fazer?

A resposta é simples, porém não agrada nada aos mais céticos: arbitrariamente escolhe-se se o indecidível vai ser falso ou verdadeiro e a partir daí ele passa a ser um novo membro no conjunto das premissas.

Logicamente falando isso resolve o problema. Pois no ponto da argumentação em que aparecia o indecidível, agora aparece uma premissa, que por definição não pode ser questionada, assim a argumentação prossegue sem nenhum entrave e o raciocínio pode ser concluído.

No próximo post vou trazer alguns exemplos para esclarecer os pontos mais obscuros e mostrar porquê, mesmo assim, o problema dos indecidíveis é muito delicado.

 

[Swanhild]

Vilya, existe alguma relação entre esse resultado do Gödel, e teoria da complexidade e linguagens formais? Nessas disciplinas também ocorrem problemas e linguagens indecidíveis.

Em linguagens formais:
Existem palavras para as quais não sabemos responder à pergunta "esta palavra pertence à linguagem?" se a linguagem (dada por uma gramática) for indecidível.

Em complexidade:
Não existe um algoritmo (mq. Turing ou algo equivalente) que resolva todas as instâncias de um problema indecidível.

 

[Vilya]

O problema dos indecidíveis é inerente à lógica. Nunca estudei linguagens formais e complexidade (apenas tenho alguma noção muito básica), mas tenho certeza que por serem displinas que tratam da estruturação lógica, os indecidíveis vão aparecer de forma crucial.

O resultado obtido por Göedel (Teorema de Gödel) usa o fato de que algumas frases "metaligüísticas" (sobre o modelo lógico) geram indecidíveis ao se tentar respondê-las apenas com as ferramentas (já existentes) do modelo lógico e com isso prevê que mesmo modificando o modelo lógico sempre existirão outros indecidíveis.

Em complexidade:
Não existe um algoritmo (mq. Turing ou algo equivalente) que resolva todas as instâncias de um problema indecidível.

Esta é exatamente uma das conclusões mais importantes do Teorema de Gödel.

 

[Swanhild]

Eu arrumei uma listagem (porca ) do paper do Alan Turing, ainda não tive tempo de dar uma boa olhada, mas ele cita algumas coisas de Gödel. (Faz um tempão que eu li esse paper, e foi uma leitura muito superficial.) Mas se um dos resultados do Gödel é esse da máquina de Turing, isso é muito legal. Umas das consequências desse resultado em computação teórica, é que não existe um algoritmo único que possa dizer se um algoritmo pára ou não. (Ou seja, é impossível arrumar-se um jeito de prever, sem rodar um algoritmo, se ele vai ou não vai entrar em loop. O máximo a que a gente pode querer chegar em termos de resolver esse problema é bolar heurísticas que funcionem para algumas classes de algoritmos ou de problemas em particular.)

 

[Vilya]

Voltando aos indecidíveis.

Numa argumentação lógica se é encontrado um indecidível há duas possibilidades: ou dá-se meia volta e procura-se por um novo argumento, ou inclui-se o indecidível na lista de premissas ou como verdadeiro ou como falso.

Nos casos em que haja um outro caminho que evite o indecidível, não há maiores problemas, pelo menos não há problemas para a estruturação da lógica.

Nos casos em que um caminho alternativo não existe a coisa complica. Do ponto de vista formal a solução é simples, basta incluí-lo na lista de axiomas, mas do ponto de vista prático não é tão simples. Há duas maneiras de incluí-lo e cada uma delas dá origem a um sistema lógico diferente. Em alguns casos ambos os sistemas dão origem a aplicações úteis, portanto não existe uma melhor forma de incluí-lo, simplesmente formas diferentes (e necessárias) de o fazê-lo. Quando uma forma de inclusão parece ser melhor do que a outra, não há muita dúvida, pega-se a que parece ser melhor. Mas em outros casos nenhuma das duas formas de incluí-lo parece estar relacionada com aplicações práticas imediatas e assim, a escolha é realmente aleatória.

O desenvolvimento da ciência está recheados de entraves gerados por indecidíveis. Na matemática dentre os mais famosos temos como exemplos o "Quinto postulado de Euclides", a "Hipótese do Continuun" e o "Axioma da Escolha", sendo que praticamente toda a física desenvolvida do meio do século XX para cá foi montada sobre eles.