Fiquei estarrecido com o artigo ``Escreva bem ou pereça- Cursos e serviços ajudam pesquisadores a redigir um bom trabalho científico''
publicado em PESQUISA FAPESP, n. 162, abril de 2011, pp. 34-42.
O artigo está diponível aqui:
http://dl.dropbox.com/u/6465890/PESQUISA%20FAPESP-%20Escreva%20bem%20ou%20perecca.pdf
No artigo, a FAPESP faz uma descarada publicidade para a empresa Publicase, que tem como sócias as biólogas Marcia Triunfol Elblink e Andrea Kaufmann-Zeh, as quais foram editoras de ``Science'' e ``Nature''. ``Nature'' é publicada pela Nature Publishing Group, uma divisão da Macmillan Publishers Limited:
http://www.nature.com/nature/index.html
e ``Science'' é publicada pela HighWire Press, associada à American Association for the Advancement of Science:
http://www.nature.com/nature/index.html.
É claro que todos devemos aprender, e ensinar, como redigir bem, escolher bem as referências, colocar os resultados da melhor maneira possível,
mostrar a relevância dos resultados, etc., etc. Isso vale para artigos teses, monografias, e tudo o mais que se escreve-- inclusive é usual que se paguem revisores em língua estrangeira, ou mesmo ajuda para editar textos. Mas pagar uma empresa que escolha os tópicos da pesquisa, e que atue quase em co-autoria, me parece um absurdo tão grande comop pagar um maratonista premiado que me empurre na Maratona de Nova Iorque e querer o troféu!
Sim, porque ao ensinar, como redigir bem, escolher bem as referências, colocar os resultados da melhor maneira possível,
mostrar a relevância dos resultados, etc., o objetivo é que a futuro cientista aprenda a fazer isso sozinho!
O texto da FAPESP, na página 36, quase dá a tabela de preços do ``serviço prata'' e do ``serviço ouro'':
``Desde 2008, a Nature Publishing Group (NPG), editora que publica a revista Nature, disponibiliza um serviço de edição de papers. O NPG
Language Editing é dividido em duas categorias. No serviço ouro, o texto é retrabalhado por dois editores especialistas no assunto e revisto por outros dois profissionais. No serviço prata, há um editor a menos no processo. A NPG não faz traduções – e deixa claro que o serviço não implica compromisso de
aceitação do artigo pelas revistas da editora. Outro exemplo é a empresa norte- -americana American Journal Experts (AJE), que reúne uma rede de doutores em vários campos do conhecimento. A AJE começou a operar em 2004. ``
E continua, na p. 38:
``A Unicamp prepara reforços na estratégia de aperfeiçoar as habilidades de redação científica de pesquisadores. Nesse ano, vai oferecer
novos workshops com a Publicase e um seminário com Carl Schwarz, diretor da editora Elsevier, para atingir estudantes de pós-graduação.''
De fato a UNICAMP já fez isso em maio de 2011: foi promovido um certo ``Seminário para Autores e Revisores- Como publicar artigos em periódicos internacionais”, no Auditório DGA da UNICAMP, em 04 de maio de 2011, 10h.
Os palestrantes, cujo preço não sabemos, mas cujo custo somado em pelo menos passagens e diárias assustaria a maior dos pesquisadores que recebem no máximo R$ 4.000,00 por ano, sujeitos a atrozes burocratas, para gastar com viagens e pesquisa, foram Rose Olthof formada em matemática aplicada na Erasmus University de Rotterdam e com mestrados em Literatura Inglesa e Ciência Literária. Atualmente cursando o MBA na Rotterdam School of Management, e Carl Schwarz formado em física pela Utrecht University. Ambos trabalharam (ou talvez ainda trabalhem) para a Elsevier.
Nenhum deles com doutorado ou com carreira acadêmica-- ou seja, a UNICAMP paga a estas pessoas para ``ensinar'' seus professore, inclusive titulares , como ser revisores e como publicar artigos, ao invés de buscar nos seus quadros os cientistas que são editores e revisores internacionais há anos!
Ao invés s de melhorar as revistas que temos, os recursos da FAPEPS agora irão para melhorar o nível dos artigos das revistas da Elsevier, da Science e sa Nature, que depois serão bem indexados pela Web of Science da Thomson Learning, o que vai melhorar o desempeho das ações da Macmillan Publishers Limited Group, da HighWire Press, da Elsevier e da própria Thomson Learning na bolsa de NY!
Será que a FAPESP vai também liberar recursos para pagar gente boa para fazer aqueles procedimentos chatos de laboratório, demonstrar teoremas e propor conjecturas? E para escrever relatórios? Estou procurando sócios para a empresa PROOFCASE, e para a REPORTCASE!
quinta-feira, 23 de junho de 2011
sábado, 16 de abril de 2011
Cono se iniciou a lógica polivalente?
Os sistemas de lógica polivalente (ou multivalente) partem do princípio de que pode haver mais de dois valores de verdade; estes podem ser verdade, falsidade, e meia-verdade, ou mesmo diversos (finitos ou infinitos) graus de aproximação entre verdade e falsidade. Até aí, nada de espantoso; o mais interessante e difícil é de fato *construir* lógicas que operem dessa forma.
Pois bem,; dizem as mal-informadas línguas (ou copiam de quem diz) que Jan Lukasiewics teria "iniciado" o estudo das lógicas multivalentes ao tentar (com sucesso discutível) uma saída filosófica honrosa para o problema dos futuros contingentes de Aristóteles.
Fans de Charles Peirce, o "Aristóteles americano" (!!), clamam que sua lógica trivalente, anterior à de Lukasiewicz, teria sido o início do movimento multivalorado. Outros buscam tal origem em MacColl, Vasil'ev e Post, e até em Kleene.
Defendo, ao contrário, que quem de fato indicou o movimento na direçao dos valores de verdade como elementos reais, e não artifícios "ad hoc", foi Paul Bernays. No artigo
"Paul Bernays and the eve of non-standard models
in logic"
disponível em
http://dl.dropbox.com/u/6465890/Introducao%20aa%20Logica/On%20Paul%20Bernays.pdf
argumento que Bernays olhava os valores de verdade como elementos necessários a partir de suas provas de independência dos axiomas do Principia Mathematica de Whitehead e Russell. Bernays trabalhava na direção dos geômetras, que não "inventam" retas distorcidas para tentar resolver pendengas, mas chegam a elas quase que de forma necessária a partir da noção do que chamo de "espaço lógico", ou seja, de ampliar os horizontes para evidenciar propriedades antes invisíveis, como a independência do 5. Postulado de Euclides. Detalhes no artigo, que vai sair na Anthology on Non-Classical Logics (Birkhauser).
A briga com os devotos dos santos de plantão, notadamente de Peirce e Lukasiewicz, já está lançada...
Pois bem,; dizem as mal-informadas línguas (ou copiam de quem diz) que Jan Lukasiewics teria "iniciado" o estudo das lógicas multivalentes ao tentar (com sucesso discutível) uma saída filosófica honrosa para o problema dos futuros contingentes de Aristóteles.
Fans de Charles Peirce, o "Aristóteles americano" (!!), clamam que sua lógica trivalente, anterior à de Lukasiewicz, teria sido o início do movimento multivalorado. Outros buscam tal origem em MacColl, Vasil'ev e Post, e até em Kleene.
Defendo, ao contrário, que quem de fato indicou o movimento na direçao dos valores de verdade como elementos reais, e não artifícios "ad hoc", foi Paul Bernays. No artigo
"Paul Bernays and the eve of non-standard models
in logic"
disponível em
http://dl.dropbox.com/u/6465890/Introducao%20aa%20Logica/On%20Paul%20Bernays.pdf
argumento que Bernays olhava os valores de verdade como elementos necessários a partir de suas provas de independência dos axiomas do Principia Mathematica de Whitehead e Russell. Bernays trabalhava na direção dos geômetras, que não "inventam" retas distorcidas para tentar resolver pendengas, mas chegam a elas quase que de forma necessária a partir da noção do que chamo de "espaço lógico", ou seja, de ampliar os horizontes para evidenciar propriedades antes invisíveis, como a independência do 5. Postulado de Euclides. Detalhes no artigo, que vai sair na Anthology on Non-Classical Logics (Birkhauser).
A briga com os devotos dos santos de plantão, notadamente de Peirce e Lukasiewicz, já está lançada...
sexta-feira, 25 de fevereiro de 2011
Duas novas resenhas
Acabo de terminar duas trabalhosas resenhas, sobre dois livros bem diferentes:
2) Davide Bondoni sobre Ernst Schröder e suas "Operações do Cálculo Lógico" (
"Parafrasi Schröoderiane, ovvero Ernst Schröder- Le operazioni del Calcolo Logico" em italiano), que vai sair no Logic and Logical Philosophy,
link direto:
http://dl.dropbox.com/u/6465890/Reviews/Review%20Davide%20Bondoni.pdf
e
2) Dov M. Gabbay, Valentin Shehtman e Dmitrij Skvortsov, "Quantification in Nonclassical Logic", Elsevier, 2009, esta para oo Mathematical Reviews,
link direto:
http://dl.dropbox.com/u/6465890/Reviews/Review%20%20MR%20%20Gabbay%20et%20allia.pdf
2) Davide Bondoni sobre Ernst Schröder e suas "Operações do Cálculo Lógico" (
"Parafrasi Schröoderiane, ovvero Ernst Schröder- Le operazioni del Calcolo Logico" em italiano), que vai sair no Logic and Logical Philosophy,
link direto:
http://dl.dropbox.com/u/6465890/Reviews/Review%20Davide%20Bondoni.pdf
e
2) Dov M. Gabbay, Valentin Shehtman e Dmitrij Skvortsov, "Quantification in Nonclassical Logic", Elsevier, 2009, esta para oo Mathematical Reviews,
link direto:
http://dl.dropbox.com/u/6465890/Reviews/Review%20%20MR%20%20Gabbay%20et%20allia.pdf
segunda-feira, 21 de fevereiro de 2011
Disciplina HF001 - Introdução à Lógica
Disciplina de Pós-Graduação- Curso de Filosofia, IFCH-UNICAMP
Primeiro semestre de 2011
Disciplina HF001 - Introdução à Lógica
Programa:
1. Introdução: histórico e paradoxos.
2. Linguagens formais: indução e recursão estrutural.
3. Semântica dos conectivos clássicos.
4. Formas normais. Conjuntos adequados de conectivos.
5. Conseqüência semântica.
6. Sistemas axiomáticos: axiomática para a lógica proposicional clássica.
7. Teoremas de correção, de completude e de compacidade.
8. Outros métodos de prova: tablôs, seqüentes, dedução natural.
9. Linguagens de primeira ordem. Estruturas de primeira ordem.
10. Axiomatização da lógica de predicados. Completude e compacidade. Aplicações.
11. Tablôs, seqüentes e dedução natural para lógica de primeira ordem.
12. Teoremas de Compacidade e Löwenheim-Skolem
13. As limitações da lógica de primeira ordem.
14. Lógica de segunda ordem.
15. Caracterização da lógica de primeira ordem: o Teorema de Lindström
Ementa:
Curso introdutório de lógica clássica, abordando primeiramente o cálculo proposicional clássico e apresentando as principais técnicas da lógica formal. Estudo detalhado do cálculo de predicados clássico, com exemplos de teorias de primeira ordem. Análise dos teoremas principais: completude, compacidade, Lowenhëim-Skolem e o o Teorema de Lindström.
Bibliografia:
Principal:
Canielli, W. A; Coniglio, M.E.; Bianconi, R. Lógica e aplicações: Matemática, Ciência da Computação e Filosofia (versão Preliminar, incluindo Teorema da Completude para lógica de primeira ordem). Disponível em: http://www.cle.unicamp.br/prof/coniglio/teaching.htm.
Ebbinghaus, H.D.; Flum, J.; e Thomas, W., Mathematical Logic. Springer Verlag, segunda edição (1996).
Secundária
Kleene, S.C., Introduction to Metamathematics. John Wiley & Sons, Inc. (1967).
Mendelson, E., Introduction to Mathematical logic. International Thomson Publishing, quarta edição (1997).
Schoenfield, J.R. Mathematical Logic. Addison-Wesley Publishing Company (1967)
Smullyan, R., First-Order Logic. Springer Verlag (1968).
Smullyan, R. Lógica de Primeira Ordem, (Traducão de Andrea Loparic, Rene P. Mazak e Luciano Vicente). Editora UNESP, 2009
Primeiro semestre de 2011
Disciplina HF001 - Introdução à Lógica
Programa:
1. Introdução: histórico e paradoxos.
2. Linguagens formais: indução e recursão estrutural.
3. Semântica dos conectivos clássicos.
4. Formas normais. Conjuntos adequados de conectivos.
5. Conseqüência semântica.
6. Sistemas axiomáticos: axiomática para a lógica proposicional clássica.
7. Teoremas de correção, de completude e de compacidade.
8. Outros métodos de prova: tablôs, seqüentes, dedução natural.
9. Linguagens de primeira ordem. Estruturas de primeira ordem.
10. Axiomatização da lógica de predicados. Completude e compacidade. Aplicações.
11. Tablôs, seqüentes e dedução natural para lógica de primeira ordem.
12. Teoremas de Compacidade e Löwenheim-Skolem
13. As limitações da lógica de primeira ordem.
14. Lógica de segunda ordem.
15. Caracterização da lógica de primeira ordem: o Teorema de Lindström
Ementa:
Curso introdutório de lógica clássica, abordando primeiramente o cálculo proposicional clássico e apresentando as principais técnicas da lógica formal. Estudo detalhado do cálculo de predicados clássico, com exemplos de teorias de primeira ordem. Análise dos teoremas principais: completude, compacidade, Lowenhëim-Skolem e o o Teorema de Lindström.
Bibliografia:
Principal:
Canielli, W. A; Coniglio, M.E.; Bianconi, R. Lógica e aplicações: Matemática, Ciência da Computação e Filosofia (versão Preliminar, incluindo Teorema da Completude para lógica de primeira ordem). Disponível em: http://www.cle.unicamp.br/prof/coniglio/teaching.htm.
Ebbinghaus, H.D.; Flum, J.; e Thomas, W., Mathematical Logic. Springer Verlag, segunda edição (1996).
Secundária
Kleene, S.C., Introduction to Metamathematics. John Wiley & Sons, Inc. (1967).
Mendelson, E., Introduction to Mathematical logic. International Thomson Publishing, quarta edição (1997).
Schoenfield, J.R. Mathematical Logic. Addison-Wesley Publishing Company (1967)
Smullyan, R., First-Order Logic. Springer Verlag (1968).
Smullyan, R. Lógica de Primeira Ordem, (Traducão de Andrea Loparic, Rene P. Mazak e Luciano Vicente). Editora UNESP, 2009
Aspectos filosóficos e conceituais das lógicas não-clássicas
Disciplina Graduação- Curso de Filosofia, IFCH-UNICAMP
Primeiro semestre de 2011
Aspectos filosóficos e conceituais das lógicas não-clássicas
Nível:Graduação
Disciplina: HG903 A- Tópicos Especias de Filosofia da Lógica I
Professor: Walter A. Carnielli
Monitor (PED): Samir Bezerra Gorsky
Ementa:
Abordaremos as motivações histórico-filosóficas bem como as características formais e estruturais dos principais sistemas de lógica não-clássica, incluindo conceituali-zação, axiomatização, semântica e meta-teoremas a respeito de alguns sistemas de lógica intuicionista, modal, polivalente e paraconsistente. Os tópicos serão tratados de maneira introdutória, porém rigorosa.
Programa
1. Introdução
2. Lógica modal
2.1. Motivações histórico-filosóficas
2.2. Sistemas normais. Axiomatização e principais teoremas
2.3 Semânticas de Kripke
2.4 Alguns meta-teoremas
3. Lógica Intuicionista
3.1. Motivações histórico-filosóficas
3.2. Álgebra de Heyting, axiomatização e principais teoremas
3.3 Semânticas de Kripke e semântica topológica
3.4 Alguns meta-teoremas
4. Lógica Paraconsistente
4.1. Motivações histórico-filosóficas
4.2. Taxonomia das lógicas paraconsistentes e principais teoremas
4.3 Semânticas de valorações e semânticas de traduções possíveis
4.4 Alguns meta-teoremas
5. Lógicas polivalentes
5.1. Motivações histórico-filosóficas
5.2. Axiomatização e principais teoremas
5.3 Semânticas tabulares
5.4 Alguns meta-teoremas
6. Discussão e significado: a lógica contemporânea
Bibliografia Básica
L. E. J. Brouwer. 1912, “Intuitionism and Formalism,” Tradução em
íngua inglesa de A. Dresden, Bull. Amer. Math. Soc. 20 (1913): 81–96, republicado em Benacerraf e Putnam (eds.) 1983: 77–89.
Patrick Blackburn, Maarten de Rijke, e Yde Venema. Modal Logic. Cambridge,
2001.
Walter Carnielli e Claudio Pizzi. Modalities and Multimodalities.
Logic, Epistemology, and the Unity of Science. Vol. 12. Springer, Amsterdam, 2008.
Walter Carnielli, Marcelo E. Coniglio e João . Marcos. Logics of Formal Inconsistency. In: Handbook of Philosophical Logic, vol. 14, pp. 15–107. Eds.: D. Gabbay; F. Guenthner. Springer, 2007.
Disponível nos CLE e-Prints Vol. 5(1), 2005
ftp://logica.cle.unicamp.br/pub/e-prints/vol.5,n.1,2005-revised.pdf
Susan Haack. Filosofia das lógicas. Tradução de Cezar Augusto Mortari e
Luiz Henrique de AraújoDutra. São Paulo: Editora UNESP, 2002.
Sítios Internet
Joan Moschovakis. 'Intuitionistic Logic' . Stanford Encyclopedia of Philosophy
http://plato.stanford.edu/entries/logic-intuitionistic/
Siegfried Gottwald. 'Many-Valued Logic' .
Stanford Encyclopedia of Philosophy
http://plato.stanford.edu/entries/logic-manyvalued/
Walter Carnielli e Marcelo E. Coniglio. 'Combining Logics'.
Stanford Encyclopedia of Philosophy
http://plato.stanford.edu/entries/logic-combining/
quinta-feira, 3 de fevereiro de 2011
Como demonstar em lógicas modais manuseando polinômios
Uma das ideias mais interessantes que me ocorreu foi tratar expressões lógicas por meio
de polinômios formais sobre corpos finitos. Mostrei que isso pode ser feito com lógicas polivalentes
finitárias em geral (incluindo a lógica clássica, obviamente), com lógicas paraconsistentes, e com o fragmetno monádico da lógica de primeira ordem. Recetnemente, com meu ex-estudante Juan Calos Agudelo, agora professor
em Bogotá, Colômbia, mostramos que várias lógicas modais podem ser tratadas por meio de polinômnios,
inclusive (por meio da conhecida tradução de Gödel) a lógica intuicionista.
O artigo "Semantics and Proof Method for Modalities" (Juan Carlos Agudelo e Walter Carnielli) vai sair no "The Review of Symbolic Logic", e já apareceu online:
The Review of Symbolic Logic
doi: 10.1017/S1755020310000213
Published online: 14 Set 201
----------------------------------------------------------
Abstract
A new (sound and complete) proof style adequate for modal logics is defined from the polynomial ring calculus (PRC). The new semantics not only expresses truth conditions of modal formulas by means of polynomials, but also permits to perform deductions through polynomial handling. This paper also investigates relationships among the PRC here defined, the algebraic semantics for modal logics, equational logics, the Dijkstra–Scholten equational-proof style, and rewriting systems. The method proposed is throughly exemplified for S5, and can be easily extended to other modal logics.
----------------------------------------------------------
de polinômios formais sobre corpos finitos. Mostrei que isso pode ser feito com lógicas polivalentes
finitárias em geral (incluindo a lógica clássica, obviamente), com lógicas paraconsistentes, e com o fragmetno monádico da lógica de primeira ordem. Recetnemente, com meu ex-estudante Juan Calos Agudelo, agora professor
em Bogotá, Colômbia, mostramos que várias lógicas modais podem ser tratadas por meio de polinômnios,
inclusive (por meio da conhecida tradução de Gödel) a lógica intuicionista.
O artigo "Semantics and Proof Method for Modalities" (Juan Carlos Agudelo e Walter Carnielli) vai sair no "The Review of Symbolic Logic", e já apareceu online:
The Review of Symbolic Logic
doi: 10.1017/S1755020310000213
Published online: 14 Set 201
----------------------------------------------------------
Abstract
A new (sound and complete) proof style adequate for modal logics is defined from the polynomial ring calculus (PRC). The new semantics not only expresses truth conditions of modal formulas by means of polynomials, but also permits to perform deductions through polynomial handling. This paper also investigates relationships among the PRC here defined, the algebraic semantics for modal logics, equational logics, the Dijkstra–Scholten equational-proof style, and rewriting systems. The method proposed is throughly exemplified for S5, and can be easily extended to other modal logics.
----------------------------------------------------------
segunda-feira, 19 de fevereiro de 2007
Estará a computação quântica "passando por cima" do problema P = NP?
Recentemente a empresa canadense D-Wave Systems Inc.
(dwavesys.com) realizou um teste com o "primeiro" computador
quântico de verdade, chamado "Orion", com 16 qubits (um "qubit"
é um "bit quântico") e que poderia ser produzido em escala.
Veja detalhes aqui.
O anúncio da própria empresa, porém, provoca um erro grave
(certamente querendo elevar o preço das ações) ao inventar:
"Quantum-computer technology can solve what is known as
“NP-complete” problems. "
Isso é falso. Na verdade, nem o que o "Orion" pode fazer, nem o
que o famoso "Algoritmo de Shor" para fatorar números inteiros
faz, sequer chega perto da questão "P =?NP".
Primeiro é essencial definir o que seria a "complexidade de um
computador quântico". A classe de problemas que um computador
quântico pode resolver eficientemente é chamada "classe BQP",
acrônimo para "bounded error quantum in polynomial time".
Conforme Michael Nielsen e Isaac Chuang, "Quantum Computation
and Quantum Information". Cambridge: Cambridge University Press,
(2000), ISBN 0-521-63503-9, a classe BQP é definida como a
classe de problemas solúveis em tempo polinomial (relativo aos
dados da entrada do problema) cuja probabilidade de erro é
limitada por um certo fator.
O problema da fatoração resolvido pelo algoritmo de Shor e as
façanhas do "Orion" estão certamente fora da classe P (isto é,
da classe dos problemas solúveis em tempo polinomial por uma
máquina de Turing determinística).
Contudo, é importante notar que o problema da fatoração de inteiros
não é (ou pelo menos nunca foi demonstrado ser) NP-completo: veja
"Integer factorization" da Wikepedia
Suspeita-se, mas parece que não se sabe, que estes problemas
estariam fora da classe BPP (isto é, da classe dos problemas
solúveis por uma máquina de Turing probabilística (não-determinística)
com erro limitado.
Pois bem: a classe BQP, onde estão os problemas os quais um
computador quântico pode resolver eficientemente, não é a mesma
coisa que a classe dos problemas NP-completos (nem se sabe se
são classes disjuntas ou não).
Dessa forma, é um erro imaginar que computadores quânticos podem
resolver problemas NP-completos, ou mesmo "passar por cima" da
questão "P =? NP".
Os computadores quânticos não podem fazer nada a mais do que os
clássicos podem fazer: uma máquina de Turing pode simular
perfeitamente um computador quântico (pelo menos os tratados na
literatura atualmente).
Temos então as seguintes conclusões:
1) Um computador quântico não pode resolver nenhum problema que
uma máquina de Turing não possa resolver (por exemplo, não
poderão passar a barreira do "Problema da Parada" de Turing,
(ver o capítulo 14 de Walter Carnielli e Richard L. Epstein, "Computabilidade,
funções computáveis, lógica e os fundamentos da Matemática"
Editora da UNESP, 2006, ISBN: 85-7139-650-7).
2) Consequentemente, um computador quântico não pode levar a
nenhuma objeção filosófica contra a Tese de Church (ver discussão
sobre a Tese de Church no Capítulo 24 de "Computabilidade...”).
O que pode acontecer então com a computação quântica? Na verdade,
mesmo sem tocar nas questões de fundamentos da computabilidade, o
algoritmo Shor, se implementado num computador mais potente
como o "Orion", pode levar a quebrar os códigos de criptografia
de chave pública como o famoso RSA (porque o RSA se baseia no
produto de dois primos muito grandes, e portanto quem souber
fatorar rapidamente quebra os códigos!)
Recentemente postamos (meu estudante de Doutorado Juan Carlos
Agudelo e eu) um artigo ousado, "Quantum Computation via
Paraconsistent Computation" (Juan C. Agudelo e Walter Carnielli)
que acabamos de postar em "arXiv".
Tratamos das "Máquinas de Turing Paraconsistentes" e mostramos
como estas podem simular algoritmos quânticos, resolvendo alguns
problemas lógicos do paralelismo quântico. É interessante notar
que as "Máquinas de Turing Paraconsistentes" resolvem alguns
problemas em tempo exponencialmente mais rápido que as máquinas
de Turing determinísticas usuais. Mas nunca tocamos diretamente
na questão "P =? NP".
O que sugerimos é que esta tenebrosa questão possa ser vista como "lógico
dependente", no sentido em que a solução da questão possa
passar pela lógica, e não só pela análise de algoritmos. Se assim
for, pode-se esclarecer o fato de tal questão ser independente
do "status" atual da computação, como alguns cientistas pensam.
(dwavesys.com) realizou um teste com o "primeiro" computador
quântico de verdade, chamado "Orion", com 16 qubits (um "qubit"
é um "bit quântico") e que poderia ser produzido em escala.
Veja detalhes aqui.
O anúncio da própria empresa, porém, provoca um erro grave
(certamente querendo elevar o preço das ações) ao inventar:
"Quantum-computer technology can solve what is known as
“NP-complete” problems. "
Isso é falso. Na verdade, nem o que o "Orion" pode fazer, nem o
que o famoso "Algoritmo de Shor" para fatorar números inteiros
faz, sequer chega perto da questão "P =?NP".
Primeiro é essencial definir o que seria a "complexidade de um
computador quântico". A classe de problemas que um computador
quântico pode resolver eficientemente é chamada "classe BQP",
acrônimo para "bounded error quantum in polynomial time".
Conforme Michael Nielsen e Isaac Chuang, "Quantum Computation
and Quantum Information". Cambridge: Cambridge University Press,
(2000), ISBN 0-521-63503-9, a classe BQP é definida como a
classe de problemas solúveis em tempo polinomial (relativo aos
dados da entrada do problema) cuja probabilidade de erro é
limitada por um certo fator.
O problema da fatoração resolvido pelo algoritmo de Shor e as
façanhas do "Orion" estão certamente fora da classe P (isto é,
da classe dos problemas solúveis em tempo polinomial por uma
máquina de Turing determinística).
Contudo, é importante notar que o problema da fatoração de inteiros
não é (ou pelo menos nunca foi demonstrado ser) NP-completo: veja
"Integer factorization" da Wikepedia
Suspeita-se, mas parece que não se sabe, que estes problemas
estariam fora da classe BPP (isto é, da classe dos problemas
solúveis por uma máquina de Turing probabilística (não-determinística)
com erro limitado.
Pois bem: a classe BQP, onde estão os problemas os quais um
computador quântico pode resolver eficientemente, não é a mesma
coisa que a classe dos problemas NP-completos (nem se sabe se
são classes disjuntas ou não).
Dessa forma, é um erro imaginar que computadores quânticos podem
resolver problemas NP-completos, ou mesmo "passar por cima" da
questão "P =? NP".
Os computadores quânticos não podem fazer nada a mais do que os
clássicos podem fazer: uma máquina de Turing pode simular
perfeitamente um computador quântico (pelo menos os tratados na
literatura atualmente).
Temos então as seguintes conclusões:
1) Um computador quântico não pode resolver nenhum problema que
uma máquina de Turing não possa resolver (por exemplo, não
poderão passar a barreira do "Problema da Parada" de Turing,
(ver o capítulo 14 de Walter Carnielli e Richard L. Epstein, "Computabilidade,
funções computáveis, lógica e os fundamentos da Matemática"
Editora da UNESP, 2006, ISBN: 85-7139-650-7).
2) Consequentemente, um computador quântico não pode levar a
nenhuma objeção filosófica contra a Tese de Church (ver discussão
sobre a Tese de Church no Capítulo 24 de "Computabilidade...”).
O que pode acontecer então com a computação quântica? Na verdade,
mesmo sem tocar nas questões de fundamentos da computabilidade, o
algoritmo Shor, se implementado num computador mais potente
como o "Orion", pode levar a quebrar os códigos de criptografia
de chave pública como o famoso RSA (porque o RSA se baseia no
produto de dois primos muito grandes, e portanto quem souber
fatorar rapidamente quebra os códigos!)
Recentemente postamos (meu estudante de Doutorado Juan Carlos
Agudelo e eu) um artigo ousado, "Quantum Computation via
Paraconsistent Computation" (Juan C. Agudelo e Walter Carnielli)
que acabamos de postar em "arXiv".
Tratamos das "Máquinas de Turing Paraconsistentes" e mostramos
como estas podem simular algoritmos quânticos, resolvendo alguns
problemas lógicos do paralelismo quântico. É interessante notar
que as "Máquinas de Turing Paraconsistentes" resolvem alguns
problemas em tempo exponencialmente mais rápido que as máquinas
de Turing determinísticas usuais. Mas nunca tocamos diretamente
na questão "P =? NP".
O que sugerimos é que esta tenebrosa questão possa ser vista como "lógico
dependente", no sentido em que a solução da questão possa
passar pela lógica, e não só pela análise de algoritmos. Se assim
for, pode-se esclarecer o fato de tal questão ser independente
do "status" atual da computação, como alguns cientistas pensam.
Assinar:
Postagens (Atom)