Os autores do levantamento são os alunos Deividi Rodrigo Santiago da Silva, Guilherme de Sá Gevaerd, Luis Fernando de Mattos Schwindlem e Northonn Tibério, sob a orientação do professor Adolfo Gustavo Serra Seca Neto.
Os autores do levantamento são os alunos Deividi Rodrigo Santiago da Silva, Guilherme de Sá Gevaerd, Luis Fernando de Mattos Schwindlem e Northonn Tibério, sob a orientação do professor Adolfo Gustavo Serra Seca Neto.
The success of theoretical computer science is measured both by its impact on practice and by its contribution to the understanding of computation and the limits thereof.
Theoretical computer science has made contributions to many areas. In the 1930's Church, Godel, Kleene, Turing and others developed fundamental models of computation that continue to be relevant. In the 1940's Shannon, von Neumann and Weiner and advanced computer science through the study of circuits and other models of computation. The 1950's and 60's saw development of formal languages as well as models of computation such as the finite-state machine and the pushdown automaton. This work continues to be used in programming and the design and translation of languages today.
Algorithms and data structures is an area that has seen an enormous amount of effort by theoreticians whose impact on practice has been immense. Activity began in this area as early as the 1950's and has grown in importance to the present time. Among its notable achievements are fast and efficient algorithms for sorting, searching and data retrieval, computations on strings and graphs, computational geometry, scientific computation, and constraint and optimization problems.
During the 1960's the foundations of computational complexity were developed. Hierarchies of problems were identified and speed-up and gap theorems established. This area flourished in the 1970's and beyond, in particular, through the identification of the NP-complete, P-complete and PSPACE-complete languages. In the 1970's connections were established between Turing and circuit complexity, thereby spawning a new examination of this topic. Space-time tradeoff studies were also initiated. Research in all of these areas continues today.
The late 1970's saw the emergence of the VLSI model as well as methods of analysis for it. This led to a burst of activity on the part of theoreticians in the 1980's in this area and to the rebirth of computer architecture under the label of VLSI.
The early 1980's saw the introduction of the first models for memory hierarchies and to the development of I/O complexity as an important area of research. Several different models capturing various aspects of memory hierarchies emerged and research in this area is now leading to a redesign of I/O systems.
Public key cryptography emerged in the mid to late 1970's and has spawned a flood of interesting ideas having to do with secure communication and interactive and zero-knowledge proof systems. Today systems based on some of these ideas are used to provide security for purchases over the Internet.
Beginning in the late 1970's, theoretical research on parallelism has resulted in new parallel computer architectures and new paradigms for programming parallel machines that have been offered in products. We have learned that even the ``simple'' PRAM parallel machine model is very difficult to program efficiently. New algorithms have had to be invented for old problems because old ones could not exploit parallelism. Through theoretical studies we have come to better understand why some problems are much more difficult to program in parallel than others. Since computers will become increasingly parallel as we approach the limits of performance of serial VLSI-based computers, the impact of research in this area will continue to grow.
The formal study of the semantics of programming languages, an area that became active in the 1960's, has led to a much better understanding of programming constructs, thereby guiding the design of successors to pioneering languages, such as LISP, Prolog, and Simula, that were invented to simplify the design and maintenance of complex applications. The study of programming language semantics also provides a fundamental tool for the development of static analysis and program transformations, two key steps in compiler optimization.
The formal study program verification techniques also began in the late 1960's. It has also had an important impact on programming language design. Recent results in model checking show high promise for a significant industrial impact.
Relational database theory emerged in the early 1970's and, together with many advances in data structures, optimization methods and other contributions, has had a major impact on practice. Today relational database are commonplace commercial products that are widely used throughout the world.
The often subtle behavior of concurrent and distributed systems, which became and active area of research on the late 1960's and early 1970's, has benefited immensely from formal modeling and analysis. Models of concurrent systems have been introduced and tools to understand concurrency applied. Transactions processing, which involves issues of serializability, locking, logging, timestamping, replication and orphan handling, have also been subjected to modeling and analysis, thereby insuring correct handling of these issues. The same is true of I/O which depends on the correct and efficient implementation of data structures used in this context. All of this work has a direct impact on practice.
Learning theory, which saw a burst of activity on the part of theoretical computer scientists in the 1980's, has led to new and deeper understanding of the problems for which active and passive learning is possible, thereby serving as a guide for the intelligent use of computers.
Computational biology and the human genome project have benefited from the algorithm design and complexity analysis that theoretical computer scientists have brought to them. This work will continue to be important in the future.
Approximation algorithms for hard computational problems have long been sought. The development of a theory of polynomially checkable proofs provides a major improvement in our understanding of the degree to which NP-complete problems are approximable. This knowledge will serve as an important guide in the search for good approximation algorithms.
Fonte: http://www.cs.brown.edu/~jes/future.theory/node4.html#SECTION00040000000000000000QUESTIONÁRIO PARA A PROVA 2 DE TEC
24/06/2008
Complexidade de Algoritmos:
O matemático e lógico Newton da Costa compartilha com outros pesquisadores a mesma paixão pelo que fazem. Com freqüência, se emociona ao falar de assuntos que parecem estranhos àqueles alheios a sua paixão. Alguns geólogos sentem ternura por pedras que contam histórias de outras eras e entomólogos têm grande carinho por insetos repugnantes. Costa vê beleza em cálculos intrincados, problemas sem solução e teorias que, de tão abstratas, só são entendidas por um número pequeno de pessoas. Newton Carneiro Affonso da Costa, paranaense nascido em Curitiba há 78 anos, casado, pai de uma filha e dois filhos e avô de duas netas, talvez tenha mais motivos que os demais pesquisadores para se entusiasmar ao falar do próprio trabalho. Ele é reconhecido no Brasil e exterior – provavelmente mais no exterior – como autor de uma teoria original criada a partir de 1958, mas muito citada e aplicada de 1976 para frente, quando finalmente ganhou o nome pelo qual ficou conhecida, a lógica paraconsistente. Trata-se de uma teoria que permite trabalhar com situações e opiniões contraditórias. Não à toa, é chamado pelos discípulos e colaboradores de “pensador da contradição”. Costa formou-se engenheiro na Universidade Federal do Paraná (UFPR) em 1952 e chegou a trabalhar por 1 ano no ramo, na empreiteira do pai de sua mulher. Mas parou de resistir à própria vocação e cursou matemática, fez licenciatura na mesma área e virou professor e pesquisador em tempo integral na UFPR, ganhando menos da metade do que ganhava na empreiteira. Lá fez seu doutorado e virou catedrático. Nos anos 1960 migrou para o Instituto de Matemática e Estatística da Universidade de São Paulo (IME/USP) e ficou 2 anos na Universidade Estadual de Campinas (Unicamp). Nos dois lugares foi professor titular. Passou por instituições da Austrália, França, Estados Unidos, Polônia, Itália, Argentina, México e Peru como professor visitante ou pesquisador. Tem mais de 200 trabalhos publicados entre artigos, capítulos e livros. Entre outros prêmios, ganhou o Moinho Santista e o Jabuti em Ciências Exatas. Na segunda quinzena deste mês, a editora Hucitec vai relançar três de seus livros esgotados há muitos anos. São eles: Introdução aos fundamentos da matemática, de 1961, Ensaio sobre os fundamentos da lógica, de 1979, e Lógica indutiva e probabilidade, de 1990. Quando se aposentou do IME/USP, Newton da Costa tornou-se professor titular da Faculdade de Filosofia, Ciências Humanas e Letras da USP e passou a estudar e ensinar filosofia da ciência. Há 4 anos decidiu morar perto dos dois filhos em Florianópolis e lecionar filosofia na Universidade Federal de Santa Catarina (UFSC). Sua paixão pela pesquisa e ensino continua intacta. Quando fui entrevistá-lo em seu apartamento no centro de Florianópolis, ele entregou um artigo sobre lógica, escrito especialmente para a revista. No final desta entrevista, o leitor poderá ler o artigo. Newton da Costa prefere escrever à mão e admite ter grande aversão em lidar com computadores. O que torna ainda mais curioso um dos seus últimos trabalhos, ainda não publicado. O título é How to build a hypercomputer (Como construir um supercomputador) e trata de uma investigação sobre os limites da teoria da computação. Abaixo, os principais trechos da entrevista. O senhor se formou em engenharia, fez carreira na matemática e terminou na filosofia. Como foi isso? Quando eu tinha uns 15 anos, mais ou menos, dois acontecimentos foram fundamentais para mim. Primeiro, ler o Discurso do método, de Descartes, que se tornou minha bíblia. Em segundo lugar, a convivência com meu tio Milton Carneiro, professor da Universidade Federal do Paraná. Nós discutíamos muito sobre filosofia e ciência. Ele me deu dois livros que nunca mais saíram da minha cabeça, O sentido da nova lógica, de W.O. Quine, de 1944, publicado naquela época no Brasil, e Logique, de L. Liard, um livro de lógica absolutamente clássico, embora tenha uma parte sobre metodologia científica. Pode-se dizer então que seu maior trabalho, sobre a lógica paraconsistente, começou a brotar naqueles momentos? Acho que custou um pouco ainda. As conversas com o meu tio e ler Descartes obviamente ajudaram. Meu problema central sempre foi pensar sistematicamente o que é o conhecimento. Especialmente o que é o conhecimento científico. Até hoje penso nisso. Então percebi perfeitamente que teria que estudar lógica, matemática e alguma ciência, como física. Pouco tempo depois comecei a ler Bertrand Russell por sugestão da minha mãe. Russell motiva qualquer um a estudar questões desse tipo. Foi quando notei que precisava conhecer também as aplicações da matemática, não só matemática. Por isso, estudar engenharia seria interessante. Mas precisava, especialmente, conhecer matemática melhor. E cursei matemática. Finalmente percebi que tudo isso, no fundo, tem a ver com filosofia – que, aliás, é o que eu mais gostava mesmo. Mais do que a matemática? Ah, muito mais. A matemática e a lógica são para mim instrumentos para entender o que é o conhecimento científico. O que vai levar, depois, ao que é o conhecimento em geral e se há conhecimento metafísico. Daí a necessidade de me embrenhar na filosofia. Ainda não cheguei à metafísica porque preciso compreender direito o conhecimento científico. Eu gostaria de entrar na lógica paraconsistente. Como o senhor a explicaria para alguém que não entende nem de lógica nem de matemática? Em 1874, um matemático russo chamado Georg Cantor criou a teoria dos conjuntos. Em pouco tempo se viu que toda a matemática padrão poderia ser construída sobre a teoria dos conjuntos e ela se tornou essencialmente a base da matemática. Convém observar, no entanto, que a noção de conjunto é algo extremamente abstrato e não se confunde com o sistema de objetos ou totalidades da vida cotidiana. Mas cerca de 30 anos depois começaram a surgir paradoxos nessa teoria. O paradoxo de Russell, o paradoxo de Burali-Forti e vários outros, que não convém explicar aqui porque levaria muito tempo. Essas questões se tornaram um problema filosoficamente incrível: como eram possíveis paradoxos na matemática e na lógica tradicionais, até então o exemplo mais perfeito de conhecimento? Aquilo era aterrador, completamente estranho, ninguém conseguia explicar, causou um rebuliço. Essa foi considerada a terceira grande crise da história da matemática. A primeira foi com os pitagóricos, quando descobriram os números irracionais. A segunda foi com o cálculo diferencial e integral, que era uma área completamente sem fundamento lógico, mas também foi superada. E, finalmente, a terceira grande crise foi a cantoriana, quando se descobriu que a teoria dos conjuntos era inconsistente e contraditória, não se sustentava. Tentou-se então resolver a questão mantendo a lógica clássica e imaginando quais as modificações que poderíamos fazer na teoria dos conjuntos para superar os paradoxos. A lógica clássica é essencialmente a lógica que nasceu com Aristóteles e teve sua formulação atual por Gottlob Frege e Russell por volta de 1870 e 1914, respectivamente. O problema da contradição é absolutamente fundamental para a lógica clássica, que não a admite.
A idéia era corrigir a teoria dos conjuntos sem destruí-la ou abandoná-la? Era isso. Em meio a esses estudos e análises surgiu algo interessantíssimo. Ficou claro que havia caminhos alternativos para superar essas dificuldades, que não eram equivalentes entre si. Ou seja, havia várias teorias de conjuntos possíveis baseadas na lógica clássica. A idéia básica quando se começou a estudar essas questões era manter a lógica clássica nas soluções usuais desses paradoxos e mudar os princípios da teoria ingênua dos conjuntos. Baseado numa frase do próprio Cantor – “A essência da matemática radica na sua completa liberdade” –, pensei, “Por que não fazer o contrário?”. Eu quero manter o máximo possível dos princípios da teoria dos conjuntos, mas mudar a lógica subjacente clássica. O que isso quer dizer? Significa que essa lógica tem de suportar contradição. Na lógica clássica, a razão básica de ela não aceitar a contradição, do ponto de vista técnico, é que a mais simples contradição numa teoria a destrói, porque tudo vira teorema. Era preciso mudar e eu comecei a construir várias lógicas. Demonstrei que existem infinitas lógicas que satisfazem essas condições e que existem infinitas teorias dos conjuntos correspondentes. Comecei a desenvolver e aplicar a lógica em outras coisas. Mas, na verdade, a saída, o pontapé inicial, foi um ponto puramente matemático relativo aos fundamentos da teoria dos conjuntos da obra cantoriana. Não o acusaram de destruir a lógica clássica? Todo mundo já disse isso, especialmente no começo, quando apresentava minha teoria por aqui. É uma das coisas que mais me deixam amolado. Por quê? Eu seria um idiota se achasse que a lógica clássica está errada. O que acredito é que ela tem um domínio de aplicações, mas, em certas circunstâncias, não se aplica. Vou dar só um exemplo: a teoria geral da relatividade e a mecânica quântica são duas das teorias mais assombrosas que apareceram na história da cultura até hoje – pelas aplicações, pela precisão das medidas, por tudo enfim. É uma loucura o que elas explicam. Por exemplo, mecânica quântica explica o laser, o maser, a estrutura química... No entanto, essas duas teorias, se você olhar bem de perto, são logicamente incompatíveis. Só tem uma maneira de juntar as duas e os físicos fazem isso com freqüência, embora não saibam como isso se faz, do ponto de vista lógico. Quer dizer, eles juntam as duas teorias naturalmente para resolver problemas que surgem, sem saber que estão usando uma lógica diferente? Exatamente. Essa lógica é a lógica paraconsistente. No momento estou trabalhando nisso, esclarecendo que a lógica da física tem de ser uma lógica paraconsistente. Ela é localmente clássica, mas globalmente paraconsistente. A física atual, que trabalha com uma combinação de teorias incompatíveis, só é possível porque existe a lógica paraconsistente. Por exemplo, a teoria do plasma tem muitas aplicações e envolve três outras teorias: a mecânica clássica, o eletromagnetismo e a quantização. Duas a duas, elas são contraditórias. No entanto, são usadas. Todo o estudo que faço no momento utiliza a teoria quântica de campo, a mecânica quântica, a relatividade e outras, para sistematizar a ciência. Essa é uma das tarefas do filósofo da ciência, sistematizar diversas ciências e compará-las. Não há solução se não fizermos isso com uma lógica diferente da lógica tradicional. Não nos dias de hoje. E quanto às aplicações da lógica paraconsistente? Durante uns 30 anos desenvolvi a lógica paraconsistente do ponto de vista puramente abstrato. Interessado apenas na beleza matemática que ela implica. Qual não foi minha surpresa quando comecei a receber do exterior, principalmente dos Estados Unidos, informações sobre aplicações em economia, na computação, em robótica, nos sistemas especialistas... No Brasil, o grupo de Jair Abe, da Universidade Paulista (Unip), tem obtido resultados muito interessantes em inteligência artificial. Recentemente um amigo japonês, Kazumi Nakamatsu, esteve comigo e mostrou as aplicações de certo tipo de lógica paraconsistente para o controle de tráfego de trens, no Japão. Nada mais prático do que isso. Já se sabe que se pode usar a lógica paraconsistente no controle do tráfego aéreo também. Quando se tem muitos aviões que não podem aterrissar, por exemplo, por mau tempo, o controlador de vôo recebe e manda informações. Elas nunca são exatas porque não se sabe exatamente a qual altura o avião está. A altura sempre tem um pequeno erro. Logo, deve ser corretamente interpretada pelo computador do controlador para evitar acidentes. A lógica paraconsistente é uma das maneiras pensadas para resolver o problema. A lógica paraconsistente é, então, uma teoria que aceita e acomoda situações contraditórias? Situações e opiniões contraditórias. Hoje há centenas de pessoas que se dedicam à lógica paraconsistente no mundo inteiro. Alguns são fundamentalistas. Acham que é a única lógica verdadeira e a lógica clássica não passa de besteira. Um dos meus melhores amigos, que foi professor na Universidade Nacional da Austrália e esteve várias vezes no Brasil, professor Richard Routley, todos os dias pela manhã quando me encontrava lá em Canberra ou mesmo em São Paulo, me saudava dizendo, “A lógica clássica está acabada”. Eu dizia sempre que não, as duas têm seu campo. A lógica clássica é a mãe da lógica paraconsistente.
Poderia ser usada também em outros campos, como na psicanálise? Segundo vários psicanalistas, especialmente os lacanianos, ela tem uma aplicação enorme nessa área. Já existe uma literatura grande na psicanálise sobre isso. A repercussão da lógica paraconsistente parece não ter arrefecido após tantos anos. Isso é algo inacreditável para mim até hoje. Pensava nisso quando era muito jovem, em 1949, 1950, meus primeiros trabalhos começaram em 1958, mas só comecei a publicar na França em 1963. Até que, lá por meados dos anos 1970, escrevi uma carta para um grande amigo, o filósofo da ciência Francisco Miró Quesada, ex-ministro da Educação no Peru. Pedi a ele, “Preciso de um nome para essa minha lógica”. Quesada foi um dos primeiros a defender a teoria pelo mundo afora, quando era embaixador. Ele me sugeriu “paraconsistente”, “ultraconsistente” ou “metaconsistente”. Escolhi paraconsistente. Depois que comecei a escrever com esse nome, não se passou 1 ano e todo o mundo da lógica começou a falar de lógica paraconsistente. Da França à ex-União Soviética, dos Estados Unidos ao Japão surgiram artigos citando de alguma forma a lógica paraconsistente. Essa é uma daquelas coisas muito difíceis de acontecer outra vez. Quesada passou a brincar dizendo, “Newton, na verdade o criador da lógica paraconsistente fui eu, porque uma coisa só existe depois que tem nome. Está na Bíblia, ‘No começo foi o verbo...’”. O que o atraiu exatamente na palavra paraconsistente? “Para” quer dizer “ao lado”. Eu nunca quis destruir a lógica clássica. É “ao lado de”, “complemento de”. Assim como a relatividade geral não destruiu a mecânica newtoniana. Nem a mecânica quântica acabou com a mecânica newtoniana. E elas não existem sem a mecânica newtoniana. Qual era o nome da lógica antes de ser batizada pelo Quesada? Teoria dos sistemas formais inconsistentes. Comprido demais. As muitas aplicações de sua teoria fez o senhor ganhar algum dinheiro com ela? Viajei muito, conheci o mundo inteiro e nunca despendi um tostão. Agora ganhar dinheiro mesmo não. Teoria não tem patente. Mas quando chegava à ex-União Soviética, por exemplo, eu tinha um automóvel com motorista à disposição, um intérprete, um quebra-galho para tudo. Aos 78 anos o senhor parece seguir mantendo suas atividades de pesquisa com vigor. Fazer o que faço é um prazer tão grande que sou capaz de pagar para continuar fazendo. O dia em que não puder estudar o que gosto, dar minhas aulas, é melhor morrer mesmo. Aliás, contam que para Einstein parecia que a diferença entre estar vivo e estar morto era que enquanto ele estava vivo tinha certeza de que podia fazer física. Depois de morto não sabia se dava para fazer. Por que saiu da UFPR? Jamais quis sair do Paraná. Minha família toda é de lá e eu estava bem na UFPR. Mas gostaria de montar um grupo de lógica e fundamentos da ciência. Aos poucos, porém, cheguei à conclusão de que isso era inexeqüível lá, nos anos 1950 e 1960, por mais que eu me esforçasse. Qual a razão? Acho que, com exceção da USP, nenhuma outra universidade dava condições para se fazer um trabalho de nível internacional em lógica e matemática no Brasil. Convidar professores estrangeiros, passar temporadas no exterior, mandar jovens para estudar em outros países. Eu me tornei catedrático na UFPR, mas, por mais boa vontade que tivessem comigo, eu me sentia patinando, sem sair do lugar. Foi para a USP, mas passou primeiro pela Unicamp, não é? Rapidamente. Tenho uma relação muito grande com a Unicamp. Quando fui professor do IME era permitido acumular por 2 anos tempo integral na USP e tempo parcial na Unicamp, desde que fosse bem justificado. Fiquei nos dois lugares e, surpreendentemente, consegui formar um grupo muito maior de pesquisa na Unicamp. Posteriormente doei minha biblioteca e arquivos para o Centro de Lógica, Epistemologia e História da Ciência da Unicamp. O senhor é um daqueles cientistas que consideram matemática e física mais difíceis de entender do que as demais ciências? Não sei se são mais difíceis. Sei que para alguns trabalhos nessas duas áreas é preciso ter um grande senso de abstração, principalmente em física-matemática e física teórica. É preciso dizer que há um sentido de beleza nessas teorias. Edgar Allan Poe dizia, “A beleza é aquilo que resiste à familiaridade”. Quanto mais voltamos a ela, mais somos atraídos a voltar. E sempre que voltamos percebemos coisas novas. A música de Bach é eterna porque se pode ouvir milhões de vezes sem cansar. Sempre veremos um aspecto novo nela. Se ouvirmos uma música comum qualquer ela não desperta novas idéias, basta repetir três ou quatro vezes e ela não oferece nada a mais. Já Bach, Beethoven, Brahms jamais cansam. Um artigo de matemática trivial você lê e não se interessa mais. Agora, a um bom artigo podemos voltar dezenas, centenas de vezes. Sempre tem mais uma coisinha, mais uma idéia, mais um aspecto que não percebemos antes. Sempre digo aos meus alunos que a matemática tem uma suprema beleza exatamente por isso. Mesmo em obras como a de Isaac Newton, em que ninguém mais vai estudar mecânica, nem astronomia pelos princípios já muito conhecidos e, algumas vezes, superados, isso ocorre. Mas se voltarmos lá e entrarmos nos detalhes da obra vai ver que lá não tem fim. É uma sinfonia à la Bach. E, veja, não importa o tamanho da obra. O doutorado do matemático americano John Nash, Prêmio Nobel de Economia, tinha cinco páginas. É genial. Eu andava com cópias na minha pasta para distribuir aos alunos e mostrar que tamanho não significa nada. Se Nash tivesse escrito essa tese na USP, não teria sido aprovado porque hoje parece que exigem pelo menos cem páginas.
Como vê o baixo nível do ensino e aprendizagem de matemática no Brasil? É uma barbaridade. Convivi com o ensino secundário dos Estados Unidos, na escola pública de Berkeley. Lá existe o que eles chamam de honour courses, cursos de honra. Os alunos que querem fazer cursos técnicos, como mecânica de automóveis, têm um mínimo de aulas de inglês, história etc. Depois, se quiserem, podem completar os créditos com os outros cursos. Mas os honour courses só fazem aqueles que querem ir para a universidade. São turmas pequenas, de 10, 12 alunos, com professores em tempo integral. O ensino envolve cálculo diferencial, cálculo integral, computação, geometria analítica... A pessoa entra de livre e espontânea vontade e se compromete a não ter nota baixa. Se não acompanhar, sai. Depois que acaba o curso, bastam duas cartas de recomendação dos professores para entrar na universidade. Se o aluno for bom nesses cursos, já está na universidade. Por várias vezes sugeri fazer algo semelhante aqui, mas sempre me dizem que não é democrático, que é elitista... O senhor é contra essa espécie de cobrança social que há no Brasil para todos cursarem universidade, mesmo os que não têm nenhuma vontade ou vocação? Nivelar todos é impossível. Não dá. Os honour courses e os demais cursos disponíveis são um jeito de contemplar todos os interessados. Faz quem quer. Vi lá, também em Berkeley, um ótimo curso de mecânica de automóveis. Os alunos pegavam um automóvel e o desmontavam inteiro, parafuso por parafuso, para depois reconstruí-lo sem deixar nenhuma peça sobrando. O estudante sai entendendo de carro, vira um excelente mecânico e pode ser tão feliz no trabalho quanto alguém que passa a vida estudando algo muito teórico e abstrato. Havia um encanador no campus da Universidade da Califórnia, quando trabalhei lá, tão competente e eficiente que ganhava mais do que um dos meus colegas mais brilhantes, o professor polonês Alfred Tarski, um grande lógico e o melhor salário do departamento. Gostaria que falasse sobre filosofia da ciência. Como é o conceito quase verdade ou verdade parcial? Acho que a ciência hoje não é algo que procura retratar o real. Quando uma proposição quer refletir o real como ele é, isso se chama teoria da correspondência da verdade. Quer dizer, o pensamento corresponde à verdade. Eu acho que a ciência não é assim, ela reflete apenas em parte o real. Ela é uma quase verdade. A mecânica quântica funciona por quê? Porque ela diz que, em certas circunstâncias, se eu apertar um parafuso, obtenho certo resultado. As grandes proposições, as grandes teorias, tudo se passa no Universo como se isso fosse verdade. Formalizei essa noção de verdade – é uma generalização da noção clássica de verdade. Ela é uma generalização da definição clássica de verdade de Tarski. Esse lógico deu uma definição notável para se poder tratar da noção de verdade em matemática, que é onde funciona. Quando se trata de física, é preciso de algo mais elástico. Propus para isso o conceito de quase verdade ou verdade parcial. Mas acho que minha concepção de verdade, rigorosamente, que é matemática, reflete mais ou menos as idéias de Charles Sanders Peirce [1839-1914], um dos maiores filósofos de todos os tempos. E acho que as grandes teorias, como a teoria quântica de campo, a mecânica quântica, a mecânica clássica de Newton, todas elas são quase verdadeiras, por exemplo. É comum dizerem que a relatividade desbancou a mecânica newtoniana. Isso é falso. Um avião ou uma ponte, por exemplo, são calculados pela mecânica newtoniana. E a mecânica quântica e a relatividade precisam da mecânica newtoniana. Senão, não funcionam. Como algo falso é usado em ciência? Exatamente porque, embora seja falso, é quase verdadeiro entre certos limites. Porque ela funciona para algumas coisas em algumas situações. Exatamente, tudo se passa em certas circunstâncias como se ela fosse verdadeira. É o “como se”. E isso é expresso matematicamente. Matematicamente. Sistematizei a teoria da ciência atual na quase verdade. Todas as grandes teorias físicas não são verdadeiras ipsis litteris, são quase verdadeiras. Se compararmos exatamente a relatividade com a realidade, há divergências. E, mesmo que ela refletisse exatamente a realidade, como é que saberíamos que ela reflete? Não dá para comparar teoria com realidade, estritamente falando. De quando é essa sua teoria? Da década de 1980, já faz algum tempo. E, note o seguinte, para a mesma teoria quase verdadeira há infinitas outras teorias quase verdadeiras, posso provar isso. E essas infinitas teorias quase verdadeiras são incompatíveis entre si. Então, a lógica da quase verdade é uma lógica paraconsistente. Para terminar, o que é o conhecimento científico? Penso que conhecimento científico é uma crença quase verdadeira e justificada. Essa é minha versão da concepção clássica de conhecimento que remonta a Platão. Nesta, o conhecimento deveria ser verdade estritamente falando; o que fiz foi substituir verdade por quase verdade. Sobre a lógica paraconsistente
A lógica clássica, bem como várias outras lógicas, não é apropriada para a manipulação de sistemas de premissas ou de teorias que encerram contradições (nas quais sem a proposição e sua negação são ambas teoremas da teoria ou conseqüências dos sistemas de premissas). Porém, nas ciências figuram contradições que são difíceis ou impossíveis de ser eliminadas (o que ocorre, por exemplo, em física, onde a teoria da relatividade geral e a mecânica quântica são logicamente incompatíveis, em direito, onde os códices jurídicos sempre apresentam inconsistências etc.). Por isso, tornou-se imperativo que se criassem lógicas que pudessem “suportar” contradições: tal é essa essência da paraconsistência. Em geral, uma lógica paraconsistente não implica que a clássica está errada, mas a generaliza. A lógica paraconsistente engloba a lógica fuzzy e tem encontrado as mais variadas aplicações, tanto teórica como prática. Em especial, ela inspirou uma nova filosofia da ciência e estendeu o campo da razão.
SOBRE A LÓGICA EM GERAL
Por Newton da Costa
A lógica, segundo a tradição, nasceu com Aristóteles (384-322 a.C). Pouco evoluiu no curso da história até os séculos XIX e XX, quando sofreu uma transformação extraordinária, dando origem, por assim dizer, a uma nova ciência.
A lógica era a disciplina das inferências válidas, das deduções. Porém, hoje, ela é uma ciência matemática, absolutamente não trivial, como tinha sido até o século XIX. O estudo das inferências válidas constitui, apenas, uma das possíveis aplicações da lógica. Ela encerra atualmente temas tais como lógica algébrica, teoria de modelos, teoria da recursão, lógicas probabilísticas, forcing, fundamentos da teoria de conjuntos e de categorias, forking, lógicas não clássicas, máquinas de Turing e teoria das valorações. Ela está intimamente correlacionada com a matemática e tem contribuído para a solução de problemas abertos em matemática.
Por outro lado, sua influência na cultura em geral é extraordinária. Os teoremas de incompletude de Gödel, por exemplo, contribuíram para a melhor compreensão do poder da matemática e da própria razão, evidenciando que um tema técnico e difícil de lógica pode ter conseqüências filosóficas de relevo. Os trabalhos de computação teórica, ramo muito rico da teoria lógica da recursão, devidos ao lógico Turing, governam toda a informática atual, com enorme influência em ciência, tanto pura como aplicada, e em filosofia da matemática e da ciência em geral.
A lógica encontrou aplicações as mais variadas: em filosofia, ciência e tecnologia. Deixando-se de lado as aplicações à filosofia (definição de verdade de Tarski, axiomatigação de aspectos da ética, fundamentação de sistemas metafísicos, etc.), à ciência (reformulação da lógica da inferência indutiva, lógica quântica, etc.), mencionaremos algumas tecnologias de uma lógica não-clássica, a lógica paraconsistente: em controle de tráfico de trens, em controle de tráfego aéreo, em finanças e economia, em inteligência artificial e em teoria da decisão.
Sobre a lógica paraconsistente
A lógica clássica, bem como várias outras lógicas, não é apropriada para a manipulação de sistemas de premissas ou de teorias que encerram contradições (nas quais uma proposição e sua negação são ambas teoremas da teoria ou conseqüências dos sistemas de premissas). Porém, nas ciências figuram contradições que são difíceis ou impossíveis de serem eliminadas (o que ocorre, por exemplo, em física, onde a teoria da relatividade geral e a mecânica quântica são logicamente incompatíveis, em direito, onde os códices jurídicos sempre apresentam inconsistências, etc.). Por isso, tornou-se imperativo que se criassem lógicas que pudessem “suportar” contradições: tal é essa essência da paraconsistência. Em geral, uma lógica paraconsistente não implica que a clássica está errada, mas a generaliza. A lógica paraconsistente engloba a lógica fuzzy e tem encontrado as mais variadas aplicações, tanto teórica como práticas. Em especial, ela inspirou uma nova filosofia da ciência e estendeu o campo da razão.
Aprenda a modelar software de forma orientada ao negócio e utilizando técnicas de modelagem ágil, neste workshop focado em práticas e dinâmicas. Saia Planejando, Modelando e Desenvolvendo Softwares com Produtividade.
Alguns dos tópicos abordados:
A Innolution Sistemas de Informática Ltda. é uma empresa de pesquisa e desenvolvimento (P&D) de software sediada na SUPERA (Incubadora de Empresas de Base Tecnológica) de Ribeirão Preto/SP.
A Innolution está oferecendo vagas para graduados e pesquisadores mestres e doutores para participarem de projetos de P&D com foco em Informática Biomédica.
Para todos os perfis acima, o candidato deverá ter experiência comprovada em desenvolvimento na linguagem Java e disponibilidade para trabalhar 40 horas semanais.