 bannerfull_6.gif ( 16846 bytes )

 HISTRIA DA LGICA

 _________________________________________________________________

 * Introduo

 * Primrdios

 + A Lgica de Aristteles

 + A contribuio dos megricos e esticos

 + Euclides e o Mtodo Axiomtico

 + Diophantus e o desenvolvimento da lgebra

 + A automatizao do raciocnio

 * A mecanizao do clculo

 + Leibniz , o precursor da Lgica Matemtica moderna

 + O problema da notao

 * A lgica matemtica no sculo XIX

 + Boole e os fundamentos da Lgica Matemtica e da Computao

 + A importncia de Frege e Peano

 * O desenvolvimento da Lgica Matemtica

 * A crise dos fundamentos , as tentativas de superao e David

 Hilbert

 * Kurt Gdel e o indecidvel

 * Alan Mathison Turing : o bero da Computao

 + A Mquina de Turing

 + O problema da parada e o problema da deciso

 + A tese de Church-Turing e outros resultados tericos

 _________________________________________________________________

 Introduo

 [ topo ]

 Considerando as idias e os conceitos como uma das linhas que

 conduziro ao grande desenvolvimento tecnolgico da Computao a

 partir da dcada de 40 do sculo XX , este captulo far referncia

 a alguns aspectos da evoluo da Cincia da Matemtica , mais

 especificamente de alguns dos seus ramos , no caso a lgebra e a

 Lgica Simblica ou Matemtica , de onde nos vieram o rigor e o

 mtodo axiomtico , at chegar na noo de computabilidade e

 procedimento , com Turing .

 _________________________________________________________________

 Primrdios

 [ topo ]

 Os primeiros passos em direo aos computadores digitais foram

 dados no Egito e na Babilnia , h mais de 4 milnios , com os

 sistemas de medidas de distncias e previso do curso das estrelas .

 Durante a civilizao grega estas pr-cincias tomaram forma

 atravs dos sistemas axiomticos .

 Talvez o passo mais fundamental dado nestes primeiros tempos tenha

 sido a compreenso do conceito de nmero , quer dizer , ver o nmero

 no como uma maneira de se poder contar , mas como uma idia

 abstrata .
 No est registrado como deve ter sido o reconhecimento ,

 pelos nossos antepassados mais primitivos , de que quatro pssaros

 caados eram distintos de dois , assim como o passo nada elementar

 de associar o nmero quatro , relativo a quatro pssaros , e o nmero

 quatro , associado a quatro pedras .

 A viso do nmero como uma qualidade de um determinado objeto  um

 obstculo ao desenvolvimento de uma idia verdadeira de nmero .

 Somente quando , de acordo com o nosso exemplo , o nmero quatro foi

 dissociado dos pssaros ou das pedras tornando-se uma entidade

 independente de qualquer objeto - uma abstrao , como diriam os

 filsofos -  que se pde dar o primeiro passo em direo a um

 sistema de notao , e da para a aritmtica .
 Conforme Bertrand

 Russell , " foram necessrios muitos anos para se descobrir que um

 par de faises e um par de dias eram ambos instncias do nmero

 dois " .

 Uma primeira cronologia que se pode estabelecer  a que vai do ano

 4.200 a.C. at meados do ano 1600 d.C .
 Um museu em Oxford possui um

 cetro egpcio de mais de 5.000 anos , sobre o qual aparecem

 registros de 120.000 prisioneiros e 1.422.000 cabras capturadas .

 Apesar do exagero dos nmeros , fica claro que os egpcios

 procuravam ser precisos no contar e no medir , bastando lembrar o

 alto grau de preciso das pirmides .
 As primeiras tentativas de

 inveno de dispositivos mecnicos para ajudar a fazer clculos

 datam dessas pocas , como por exemplo o baco e o mecanismo

 Antikythera , sobre os quais se falar mais detidamente no captulo

 da Pr-Histria Tecnolgica .

 Sob o foco que se est trabalhando , deve-se ver nestes tempos as

 tentativas de conceituao do nmero , o estabelecimento das bases

 numricas , o estudo da lgebra e geometria que tanto atraram os

 antigos .
 Tempos de evoluo lenta , e em termos de produo efetiva

 de conhecimento matemtico bem abaixo da quantidade e qualidade

 produzida quase que exponencialmente a partir do sculo XV d.C. ,

 mas no menos importantes .
 De fato , para se compreender a Histria

 da Matemtica na Europa  necessrio conhecer sua histria na

 Mesopotmia e Egito , na Grcia antiga e na civilizao islmica dos

 sculos IX a XV .

 A Lgica de Aristteles

 [ topo ]

 A Lgica foi considerada na tradio clssica e medieval como

 instrumento indispensvel ao pensamento cientfico .
 Atualmente 

 parte importante na metodologia dedutiva das cincias , alm de

 constituir-se como um saber prprio , com abertura a relevantes

 problemas teorticos .
 Da Cincia Lgica nasceu a Lgica Matemtica

 e , dentro desta , vrias filosofias da lgica que interpretam os

 clculos simblicos e sua sistematizao axiomtica .
 Para a

 Histria da Computao interessa abordar em particular a questo do

 pensamento dedutivo e matemtico , seus limites , o problema da

 relativa mecanizao do pensamento quantitativo e o problema da

 Inteligncia Artificial .
 Da discussso e busca da soluo desses

 problemas , que entram tambm no campo filosfico , formou-se a base

 conceitual , Teoria da Computabilidade , necessria para o advento do

 computadores .

 O incio da cincia da Lgica encontra-se na antiga Grcia ^ e .
 As

 polmicas geradas pela teoria de Parmnides e os famosos argumentos

 de Zeno , que negavam a realidade do movimento fazendo um uso

 indevido do princpio da no-contradio , contribuiram para a

 distino dos conceitos , para se ver a necessidade de argumentar

 com clareza mediante demonstraes rigorosas , respondendo s

 objees dos adversrios .
 Mais tarde , as sutilezas dos sofistas ,

 que reduziam todo o saber  arte de convencer pelas palavras ,

 levaram Scrates a defender o valor dos conceitos e tentar

 defini-los com preciso .
 Assim a Lgica como cincia vai se

 formando pouco a pouco , principalmente com Scrates e Plato .
 Mas

 Plato pensava que qualquer contedo da mente existia tal qual na

 realidade e Aristteles reage ao seu mestre , dizendo que as idias

 existem somente na mente humana , mas correspondendo a realidades .

 Com Aristteles ( 384 a.C. - 322 a.C. )  que se d o verdadeiro

 nascimento da Lgica , cincia das idias e dos processos da mente .

 Ele redigiu uma srie de trabalhos que seriam editados por

 Andrnico de Rodes no sculo I d.C. e que receberam posteriormente

 o nome de Organon ( " Instrumento " ) , de acordo com a concepo

 segundo a qual a Lgica deveria fornecer os instrumentos mentais

 necessrios para enfrentar qualquer tipo de investigao .

 Aristteles chamava a Lgica como o termo " analtica " ( e justamente

 " Analticos " so entitulados os escritos fundamentais do Organon ) .

 A analtica ( do grego analysis , que significa " resoluo " ) explica

 o mtodo pelo qual , partindo de uma dada concluso , resolve-se

 precisamente nos elementos dos quais deriva , isto  , nas premissas

 e nos elementos de que brota , e assim fica fundamentada e

 justificada .

 Aristteles construiu uma sofisticada teoria dos argumentos , cujo

 ncleo  a caracterizao e anlise dos assim chamados silogismos ,

 os tpicos raciocnios da lgica desse filsofo .
 O argumento

 Todo homem  mortal

 Scrates  homem

 Logo Scrates  mortal

  o exemplo tpico do silogismo perfeito .

 Nos Primeiros Analticos , Aristteles desenvolveu minuciosamente o

 sistema dos silogismos , mostrando os princpios maiores que o

 sustentam e as regras que lhe devem moldar a construo .
 A anlise

 do Filsofo  to ampla quanto engenhosa e envolve tambm as assim

 chamadas " modalidades " e os silogismos modais .

 Entre as caractersticas mais importantes da silogstica

 aristotlica est a de se ter pensado pela primeira vez na histria

 da lgica em fazer uso de letras que poderiam ser usadas para uma

 expresso substantiva qualquer , fundamental para desenvolvimentos

 posteriores .
  tambm com Aristteles que se encontra uma das

 primeiras tentativas de se estabelecer um rigor nas demonstraes

 matemticas .
 Ao definir os dois tipos de demonstrao , quia ( dos

 efeitos s causas ) e propter quid ( das causas aos efeitos ) , dizia

 ( I Anal .
 Post. , lect. 14 ) que as matemticas utilizam

 preferencialmente esse modo de demonstrar , e por isso esta cincia

  essencialmente dedutiva : " algumas vezes o mais conhecido por ns

 em si mesmo e por natureza  tambm o mais cognoscvel em si mesmo

 e por natureza .
 Assim acontece nas matemticas , nas quais , devido 

 abstrao da matria , no se efetuam demonstraes mais do que a

 partir dos princpios formais .
 E assim as demonstraes procedem

 desde o mais cognoscvel em si mesmo " .

 A contribuio dos megricos e esticos

 [ topo ]

 Embora Aristteles seja o mais brilhante e influente filsofo

 grego , outra importante tradio argumentativa formou-se na antiga

 Grcia , com os megricos e esticos .
 Pouco conservada pela

 tradio , merece um melhor tratamento dos historiadores , porque o

 pouco que se conhece sugere que esses gregos eram altamente

 inteligentes .

 Os megricos ( em funo de sua cidade , Mgara ) interessaram-se por

 certos enigmas lgicos como o conhecido " paradoxo do mentiroso " :

 quem diz " O que eu afirmo agora  falso " , enuncia algo verdadeiro

 ou falso ?
 Um deles , Diodoro Cronus , que morreu por volta de 307

 a.C. , formulou interessante concepo modal , relacionando

 possibilidade , tempo e verdade , enquanto outro megrico , de nome

 Flon , estudou proposies do tipo " Se chove ento a rua est

 molhada " , contruda com o auxlio das expresses " se ...
 , ento ...
 "

 conhecidas como condicionais .
 Ele as definiu em termos extremamente

 polmicos , mas que seriam assumidos como corretos , vinte e trs

 sculos mais tarde pelos fundadores da Lgica Contempornea .

 Os esticos ( da chamada escola filosfica de " Stoa " , que quer dizer

 " prtico " ) desenvolveram tambm notveis teorias lgicas .
 Tinham

 bastante presente a diferena que h entre um cdigo de comunicao

 especfico , de um lado , e o que se pode expressar atravs do uso de

 tal cdigo .
 Assim sendo , um conceito de " proposio " anlogo ao

 usado na atual Lgica , j estava presente , de modo virtual , na

 filosofia estica da linguagem .

 Porm a mais notvel contribuio estica  Lgica foi obra de

 Crsipo de Soles ( 280-206 a.C. ) , homem de vasta produo

 poligrfica ( 750 livros ) .
 Ele estudou as sentenas condicionais e

 tambm as disjuntivas ( regidas pela partcula " ou " ) e as

 copulativas ( regidas pelo " e " ) , tendo tambm reconhecido claramente

 o papel lgico desempenhado pela negao .
 Alm disto , Crsipo foi

 capaz de relacionar tais idias com as modalidades , elaborando ,

 ento , um sistema de princpios lgicos que , no seu campo

 especfico , foi muito alm dos poucos resultados obtidos por

 Aristteles e seu discpulo Teofrasto .
 Por tal razo , Crsipo 

 reconhecido como o grande precursor daquilo que hoje se chama

 " Clculo Proposicional " , o primeiro captulo da Lgica desenvolvida

 a partir do ltimo quarto do sculo XIX .

 Euclides e o Mtodo Axiomtico

 [ topo ]

 Com sua obra Elementos , o matemtico grego Euclides ( 330 a 277 a.C .

 aproximadamente ) deu forma sistemtica ao saber geomtrico .
 No

 primeiro livro dos Elementos , ele enuncia vinte e trs definies ,

 cinco postulados e algumas noes comuns ou axiomas .
 Em seguida ele

 deduz proposies ou teoremas , os quais constituem o saber

 geomtrico , como por exemplo : " se em um tringulo dois ngulos so

 iguais entre si , tambm os lados opostos a esses ngulos so iguais

 entre si " .

 Esse  portanto o modo como Euclides ordena o conhecimento

 geomtrico no chamado sistema euclidiano .
 Durante sculos esse

 sistema valeu como modelo insupervel do saber dedutivo : os termos

 da teoria so introduzidos depois de terem sido definidos e as

 proposies no so aceitas se no foram demonstradas .
 As

 proposies primitivas , base da cadeia sobre a qual se desenvolvem

 as dedues sucessivas , Euclides as escolhia de tal modo que

 ningum pudesse levantar dvidas sobre a sua veracidade : eram

 auto-evidentes , portanto isentas de demonstrao .
 Leibniz afirmaria

 mais tarde que os gregos raciocinavam com toda a exatido possvel

 em matemtica e deixaram  humanidade modelos de arte demonstrativa

 .

 Em resumo , Euclides , como j fizera Aristteles , buscou o ideal de

 uma organizao axiomtica , que em ltima instncia se reduz 

 escolha de um pequeno nmero de proposies notoriamente

 verdadeiras daquele domnio do conhecimento , e  posterior deduo

 de todas as outras proposies verdadeiras desse domnio , a partir

 delas .

 Surge com Euclides e Aristteles ( estar plenamente desenvolvida no

 incio do sculo XX com a escola formalista de Hilbert ) a busca de

 uma economia do pensamento ( um bom texto sobre o assunto pode ser

 encontrado em ) .
 A Histria da Computao tem um marco

 significativo nesse ponto da Histria : o comeo da busca da

 automatizao do raciocnio e do clculo .

 Mas havia um problema no sistema de Euclides : suas " evidncias " no

 eram assim to evidentes .
 O seu quinto postulado no convenceu de

 modo algum , e despertou perplexidade na histria do prprio

 pensamento grego , depois no rabe e no renascentista .
 No sculo

 XIX , Karl Friedrich Gauss ( 1777-1855 ) viu com toda a clareza a no

 demonstrabilidade do quinto postulado e a possibilidade da

 construo de sistemas geomtricos no euclidianos .
 Janos Boulay

 ( 1802-1860 ) , hngaro , e Nicolai Ivanovic Lobacewskiy ( 1793-1856 ) ,

 russo , trabalhando independentemente , constrem uma geometria na

 qual o postulado da paralela no vale mais .

 A consequncia desses fatos foi a eliminao dos poderes da

 intuio na fundamentao e elaborao de uma teoria geomtrica : os

 axiomas no so mais " verdades evidentes " que garantem a " fundao "

 do sistema geomtrico , mas puros e simples pontos de partida ,

 escolhidos convencionalmente para realizar uma construo dedutiva .

 Mas , se os axiomas so puros pontos de partida , quem garantir que ,

 continuando-se a deduzir teoremas , no se cair em contradio ?

 Esta questo crucial dos fundamentos da matemtica levar aos

 grandes estudos dos finais do sculo XIX e incios do XX e ser o

 ponto de partida do projeto formalista de David Hilbert , assim como

 de outras tentativas de se fundamentar a matemtica na lgica e na

 teoria dos conjuntos , como as propostas por Frege , Russell e

 Cantor .
 Mas ser dessa sequncia de sucessos e fracassos que se

 produzir a base da Computao , com Turing , von Neumann , Post ,

 Church , e outros mais .

 Diophantus e o desenvolvimento da lgebra

 [ topo ]

 O seguinte problema no Rhind Papyrus , do Museu britnico em

 Londres , foi escrito por volta do ano 1650 a.C. :

 Divida 100 pes entre 10 homens , incluindo um barqueiro , um capataz

 e um vigia , os quais recebem uma dupla poro cada .
 Quanto cabe a

 cada um ?

 Isto naturalmente pode ser resolvido usando-se lgebra .

 O primeiro tratado de lgebra foi escrito pelo grego Diophantus , da

 cidade de Alexandria , por volta do ano 250 .
 O seu Arithmetica ,

 composto originalmente por 13 livros dos quais somente 6 se

 preservaram , era um tratado " caracterizado por um alto grau de

 habilidade matemtica e de engenho : quanto a isto , o livro pode ser

 comparado aos grandes clssicos da idade alexandrina anterior " .

 Antes de Diophantus , toda a ' lgebra ' que havia , incluindo

 problemas , operaes , lgica e soluo , era expressada sem

 simbolismo - palavra chave sobre a qual ainda se voltar a falar -

 ; ele foi o primeiro a introduzir o simbolismo na matemtica grega .

 Para uma quantidade desconhecida usava um smbolo ( chamado

 arithmos ) , que caracterizava um nmero indefinido de unidades .
 Pela

 nfase dada em seu tratado  soluo de problemas indeterminados ,

 tal tratado tornou-se conhecido como anlise diofantina , em geral

 parte de cursos de teoria dos nmeros .
 Seu trabalho , contudo , no 

 suficiente para lhe conferir o ttulo de pai da lgebra .

 Na verdade o termo lgebra vem do rabe al-jabr , ou literalmente , a

 " reunio de partes quebradas " , tendo sido popularizado pelo livro

 ilm Al-jabr wa'l-mukabala ( Restaurao e Confronto ) , escrito pelo

 famoso matemtico e astrnomo persa Abu Ja'far Muhammad ( 800-847 ) ,

 que posteriormente ficou conhecido como al-Kharazmi , o homem de

 Kwarazm ( atualmente Khiva , no Uzbequisto ) .
 Al-Kharazmi introduziu

 a escrita dos clculos no lugar do uso do baco .
 De seu nome

 derivaram as palavras algarismo e algoritmo .
 Vale ressaltar que ,

 alm dos gregos como Diophantus , tambm os hindus tinham

 desenvolvido estudos no campo da lgebra ; coube aos rabes a misso

 de conservar e transmitir a herana matemtica grega e hindu .

 Embora no muito visvel ainda , deve-se chamar a ateno para essa

 disciplina da lgebra , que deve ser colocada entre as cincias que

 fundamentaram o desenvolvimento da Computao .
 Pois o computador e

 todos os instrumentos que o precederam ( rguas de clculo , mquina

 de Pascal , a calculadora de Leibniz , a mquina analtica de

 Babbage , etc. ) so somente as manifestaes prticas que foram

 surgindo , com naturalidade , em resultado da busca pelo homem de

 reduzir os problemas a equaes matemticas , resolvendo-as segundo

 regras .
 E isto , h muitos sculos , j tinha tomado o nome de

 lgebra , a " arte dos raciocnios perfeitos " como dizia Bhaskara , o

 conhecido matemtico hindu do sculo XII .
 Com os rabes , depois de

 relativo obscurecimento da cultura grega , d-se continuidade ao

 processo que proporcionar as bases fundamentais para o raciocnio

 automatizado , fundamental na Cincia da Computao .

 A automatizao do raciocnio

 [ topo ]

 Ainda dentro do perodo acima estabelecido ( 4.200 a.C. at meados

 do ano 1600 d.C ) iniciou-se concretizao de uma antiga meta : a

 idia de se reduzir todo raciocnio a um processo mecnico , baseado

 em algum tipo de clculo formal .
 Isto remonta a Raimundo Llio .

 Embora negligenciado pela cincia moderna , Raimundo Llio

 ( 1235-1316 ) , espanhol , figura pletrica de seu tempo , em seu

 trabalho Ars Magna ( 1305-1308 ) , apresentou a primeira tentativa de

 um procedimento mecnico para produzir sentenas logicamente

 corretas .
 Llio acreditava que tinha encontrado um mtodo que

 permitia , entre outras coisas , tirar todo tipo de concluses ,

 mediante um sistema de anis circulares dispostos concentricamente ,

 de diferentes tamanhos e graduveis entre si , com letras em suas

 bordas .
 Inveno nica , tentar cobrir e gerar , representando com

 letras - que seriam categorias do conhecimento - , todo o saber

 humano , sistematizado em uma gramtica lgica .

 Os procedimentos estabelecidos por Llio no foram muito vlidos .

 Mas o mais importante em Llio  a idia concebida , genial sob

 certo aspecto .
 Tanto que seu trabalho influenciar muitos

 matemticos famosos , do nvel de um Cardano ( 1545 ) , Descartes

 ( 1598-1650 ) , Leibniz ( 1646-1716 ) , Cantor ( 1829-1920 ) , entre outros .

 Raimundo Llio  considerado o precursor da anlise combinatria .

 Como dir R. Blanch : " encontramos em Llio , pelos menos em germe e

 por mais que ele no soubesse tirar partido disso por inabilidade ,

 duas idias que iriam se tornar predominantes nas obras de Lgica ,

 primeiro em Leibniz e depois em nossos contemporneos : as idias de

 caracterstica e as idias de clculo ( ...
 ) .
 Com a ajuda desse

 simbolismo , eles pretendem permitir que as operaes mentais

 frequentemente incertas fossem substitudas pela segurana de

 operaes quase mecnicas , propostas de uma vez por todas " .

 Pode-se ver em Raimundo Llio os primrdios do desenvolvimento da

 Lgica Matemtica , isto  , de um novo tratamento da cincia da

 Lgica : o procurar dar-lhe uma forma matemtica .
 No  do interesse

 deste trabalho aprofundar-se nas discusses filosficas - que ainda

 esto em aberto por sinal - sobre os conceitos " lgica matemtica "

 e " lgica simblica " , se  uma lgica distinta da cincia

 matemtica ou no , etc. , mas em caracteriz-la , pois sem dvida

 alguma a Computao emergir dentro de um contexto da evoluo

 deste novo tratamento da lgica .

 A Lgica Matemtica ergue-se a partir de duas idias metodolgicas

 essencialmente diferentes .
 Por um lado  um clculo , da sua

 conexo com a matemtica .
 Por outro lado , caracteriza-se tambm

 pela idia de uma demonstrao exata e , neste sentido , no  uma

 imitao da matemtica nem esta lhe serve de modelo , mas pelo

 contrrio ,  Lgica caber investigar os fundamentos da matemtica

 com mtodos precisos e oferecer-lhe o instrumento para uma

 demonstrao rigorosa .

 A palavra lgebra voltar a aparecer com o ingls Robert

 Recorde ( 1510 ?
 -1558 ) , em sua obra Pathway of Knowledge ( 1551 ) , que

 introduz o sinal de ' = ' e divulga os smbolos ' + ' e ' - ' ,

 introduzidos por John Widmann ( Arithmetica , Leipzig , 1489 ) .
 Thomas

 Harriot ( 1560-1621 ) prosseguir o trabalho de Recorde , inventando os

 sinais ' > ' e ' < ' .
 Willian Oughtred ( 1574-1621 ) , inventor da rgua

 de clculo baseada nos logaritmos de Napier , divulgou o uso do

 sinal '  ' , tendo introduzido os termos seno , coseno e tangente .
 Em

 1659 J.H. Rahn usou o sinal '  ' .
 Todos esses matemticos ajudaram

 a dar  lgebra sua forma mais moderna .

 _________________________________________________________________

 A mecanizao do clculo

 [ topo ]

 Se  aceito o ponto de vista de estudiosos como Needham , a data de

 1600 pode ser vista como um bom divisor de guas dentro da histria

 da cincia em geral .
 Vale a pena lembrar que o estudo da matemtica

 no tempo anterior a essa data , na Europa , no havia avanado

 substancialmente em relao ao mundo rabe , hindu ou chins .

 A lgebra rabe fora perfeitamente dominada e tinha sido

 aperfeioada , a trigonometria se tornara uma disciplina

 independente .
 O casamento de ambas pela aplicao dos mtodos

 algbricos no terreno da geometria foi o grande passo e Galileu

 ( 1564-1642 ) a tem um papel preponderante .
 Ele uniu o experimental

 ao matemtico , dando incio  cincia moderna .
 Galileu d uma

 contribuio decisiva a uma formulao matemtica das cincias

 fsicas .
 A partir de ento , em resultado desse encontro da

 matemtica com a fsica , a cincia tomou um novo rumo , a um passo

 mais rpido , e rapidamente as descobertas de Newton sucedem s de

 Galileu .

 Trata-se de um perodo de transio por excelncia , que preparou o

 caminho para uma nova matemtica : no j uma coleo de truques ,

 como Diophantus possura , mas uma forma de raciocinar , com uma

 notao clara .
  o comeo do desenvolvimento da idia de formalismo

 na Matemtica , to importante depois para a fundamentao terica

 da Computao .

 Leibniz , o precursor da Lgica Matemtica moderna

 [ topo ]

 A Lgica Moderna comeou no sculo XVII com o filsofo e matemtico

 alemo Gottfried Wilhelm Leibniz .
 Seus estudos influenciaram , 200

 anos mais tarde , vrios ramos da Lgica Matemtica moderna e outras

 reas relacionadas , como por exemplo a Ciberntica ( Norbert Wiener

 dizia que se fosse escolher na Histria da Cincia um patrono para

 a Ciberntica , elegeria Leibniz " ) .

 Entre outras coisas , Leibniz queria dotar a Metafsica ( aquela

 parte da Filosofia que estuda o " ser " em si ) de um instrumento

 suficientemente poderoso que a permitisse alcanar o mesmo grau de

 rigor que tinha alcanado a Matemtica .
 Parecia-lhe que o problema

 das interrogaes e polmicas no resolvidas nas discusses

 filosficas , assim como a insegurana dos resultados , eram

 fundamentalmente imputveis  ambiguidade dos termos e dos

 processos conclusivos da linguagem ordinria .
 Leibnz viu surgir a

 idia central de sua nova lgica precisamente como projeto de

 criao de uma lgica simblica e de carter completamente

 calculstico , anlogos aos procedimentos matemticos .

 Historicamente falando , tal idia j vinha sendo amadurecida ,

 depois dos rpidos desenvolvimentos da Matemtica nos sculos XVI e

 XVII , possibilitados pela introduo do simbolismo .
 Os algebristas

 italianos do sculo XVI j tinham encontrado a frmula geral para a

 resoluo das equaes de terceiro e quarto graus , oferecendo 

 Matemtica um mtodo geral que tinha sido exaustivamente buscado

 pelos antigos e pelos rabes medievais .
 Descartes e Fermat criaram

 a geometria analtica , e , depois de iniciado por Galileu , o clculo

 infinitesimal desenvolveu-se com grande rapidez , graas a Newton e

 ao prprio Leibniz .
 Ou seja , as matemticas romperam uma tradio

 multisecular que as havia encerrado no mbito da geometria , e se

 estava construindo um simbolismo cada vez mais manipulvel e

 seguro , capaz de funcionar de uma maneira , por assim dizer ,

 mecnica e automtica , sujeito a operaes que , no fundo , no eram

 mais do que regras para manipulao de smbolos , sem necessidade de

 fazer uma contnua referncia a contedos geomtricos intuitivos .

 Leibniz deu-se conta de tudo isto e concebeu , tambm para a deduo

 lgica , uma desvinculao anloga com respeito ao contedo

 semntico das proposies , a qual alm de aliviar o processo de

 inferncia do esforo de manter presente o significado e as

 condies de verdade da argumentao , pusesse a deduo a salvo da

 fcil influncia que sobre ela pode exercer o aspecto material das

 proposies .
 Deste modo coube a Leibniz a descoberta da verdadeira

 natureza do " clculo " em geral , alm de aproveitar pela primeira

 vez a oportunidade de reduzir as regras da deduo lgica a meras

 regras de clculo , isto  , a regras cuja aplicao possa prescindir

 da considerao do contedo semntico das expresses .

 Leibniz influenciou seus contemporneos e sucessores atravs de seu

 ambicioso programa para a Lgica .
 Este programa visava criar uma

 linguagem universal baseada em um alfabeto do pensamento ou

 characteristica universalis , uma espcie de clculo universal para

 o raciocnio .

 Na viso de Leibniz a linguagem universal deveria ser como a

 lgebra ou como uma verso dos ideogramas chineses : uma coleo de

 sinais bsicos que padronizassem noes simples no analticas .

 Noes mais complexas teriam seu significado atravs de construes

 apropriadas envolvendo sinais bsicos , que iriam assim refletir a

 estrutura das noes complexas e , na anlise final , a realidade .
 O

 uso de numerais para representar noes no analticas poderia

 tornar possvel que as verdades de qualquer cincia pudessem ser

 " calculadas " por operaes aritmticas , desde que formuladas na

 referida linguagem universal .
 Conforme o prprio Leibniz , " ( ...
 )

 quando aparecer uma controvrsia , j no haver necessidade de uma

 disputa entre dois filsofos mais do que a que h entre dois

 calculistas .
 Bastar , com efeito , tomar a pena na mo , sentar-se 

 mesa ( ad abacus ) e ( ao convite de um amigo , se se deseja ) , dizer um

 ao outro : Calculemos !
 " ^ .

 Essa idia de Leibniz sustentava-se em dois conceitos intimamente

 relacionados : o de um simbolismo universal e o de um clculo de

 raciocnio ( isto  , um mtodo quase mecnico de raciocnio ) .
 Isto

 para a Histria da Computao tem um particular interesse , pois

 esse calculus ratiocinator de Leibniz contm o embrio da machina

 ratiocinatrix , a mquina de raciocinar buscada por Turing e depois

 pelos pesquisadores dentro do campo da Inteligncia Artificial .

 Leibniz , assim como Boole , Turing , e outros - basta lembrar o

 baco , o ' computador ' de Babbage , etc. - , perceberam a

 possibilidade da mecanizao do clculo aritmtico .
 O prprio

 Leibniz , e Pascal um pouco antes , procuraram construir uma mquina

 de calcular .
 Nota-se portanto que o mesmo impulso intelectual que o

 levou ao desenvolvimento da Lgica Matemtica o conduziu  busca da

 mecanizao dos processos de raciocnio .

 Interessa tambm chamar a ateno sobre a idia de uma linguagem

 artificial que j aparece em Leibniz .
 Como j foi dito , ele captou

 muito bem as inmeras ambigidades a que esto submetidas as

 linguagens de comunicao ordinrias e as vantagens que apresentam

 os smbolos ( que ele chamava notae ) da Aritmtica e lgebra ,

 cincias nas quais a deduo consiste no emprego de caracteres .
 Ao

 querer dar  Lgica uma linguagem livre de ambigidades e ao

 procurar associar a cada idia um sinal e obter a soluo de todos

 os problemas mediante a combinao destes sinais , Leibniz acabou

 provocando um novo desenvolvimento da prpria lgica .

 A idia de uma linguagem artificial ou a reduo do raciocnio ao

 clculo , como j visto em Llio e agora em Leibniz , no  ,

 portanto , patrimnio do sculo XX .
 A contribuio de Leibniz ao

 desenvolvimento da lgica aparece sob dois aspectos : ele aplicou

 com sucesso mtodos matemticos para a interpretao dos silogismos

 aristotlicos , e apontou aquelas partes da lgebra que esto

 abertas a uma interpretao no aritmtica .
 Pela primeira vez se

 exps de uma maneira clara o princpio do procedimento formal .

 Leibniz tornou-se assim o grande precursor da Lgica Matemtica .

 Talvez se pudesse perguntar como  possvel que muitos apresentem a

 Lgica Simblica como fruto do nosso tempo , enquanto teve sua

 origem na segunda metade do sculo XVII .
  que , na realidade , a

 aportao de Leibniz ficou substancialmente reduzida a um mero

 programa , do qual s executou alguns fragmentos , muito parciais se

 bem que muito interessantes tambm , capazes de nos dar uma idia de

 como concebia sua obra .
 Nem sequer seus seguidores diretos levaram

 para a frente a construo do clculo lgico mais alm de um nvel

 muito rudimentar .
 Provavelmente a excessiva magnitude do plano de

 sua characteritica universalis o tenha seduzido , afastando Leibniz

 de objetivos mais modestos porm alcanveis , como o de construir o

 primeiro clculo lgico autntico .

 Ainda dentro desses primeiros passos mais concretos em direo 

 construo de um dispositivo para clculo automtico , no se pode

 deixar de falar do ilustre francs Blaise Pascal ( 1623-1662 ) , j

 acima citado , matemtico , cientista e filsofo , que , antecedendo a

 Leibniz , montou uma mquina de clculo digital para ajud-lo nos

 negcios do pai .

 O problema da notao

 [ topo ]

 Nas cincias , as descobertas que podem ser compreendidas e

 assimiladas rapidamente por outros so fonte de progresso imediato .

 E na Matemtica o conceito de notao est relacionado com isso .

 Basta lembrar os algarismos romanos e pensar na complexidade que

 envolve , por exemplo a multiplicao , de MLXXXIV por MMLLLXIX .
 A

 notao de Leibniz usada para o clculo contribuiu mais do que a de

 Newton para a difuso das novas idias sobre integrais , na poca .

 Pense-se por um momento como se resolve ax = b .
 Imediatamente pode

 ser dado como resposta que x = b / a e haveria surpresa se algum

 respondesse a = b / x .
  que normalmente se usam as ltimas letras do

 alfabeto para representar as incgnitas e as do comeo para

 representar as quantidades conhecidas .
 Mas isso no foi sempre

 assim , e somente no sculo XVII , com Descartes , tais convenes

 comearam a ser usadas ^ .

 Geralmente tende-se a apreciar o passado desde o sofisticado posto

 de observao do tempo atual .
  necessrio valorizar e revalorizar

 este difcil e longo passado de pequenas e grandes descobertas .

 Leibniz , em seu esforo no sentido de reduzir as discusses lgicas

 a uma forma sistemtica que pudesse ser universal , aproximou-se da

 Lgica Simblica formal : smbolos ou ideogramas deveriam ser

 introduzidos para representar um pequeno nmero de conceitos

 fundamentais necessrios ao pensamento .
 As idias compostas

 deveriam ser formadas a partir desses " alfabetos " do pensamento

 humano , do mesmo modo como as frmulas so desenvolvidas na

 Matemtica .
 Isto o levou entre outras coisas a pensar em um

 sistema binrio para a Aritmtica e demonstrou a vantagem de tal

 sistema sobre o decimal para dispositivos mecnicos de calcular .
 A

 idia de uma lgica estritamente formal - da construo de sistemas

 sem sentido , interpretveis a posteriori - no tinha surgido .

 Duzentos anos mais tarde , George Boole formularia as regras bsicas

 de um sistema simblico para a lgica matemtica , refinado

 posteriormente por outros matemticos e aplicado  teoria dos

 conjuntos .
 A lgebra booleana constitui a base para o projeto de

 circuitos usados nos computadores eletrnicos digitais .

 _________________________________________________________________

 A lgica matemtica no sculo XIX

 [ topo ]

 A passagem do sculo XVIII para o sculo XIX marca o incio de um

 novo tempo na Histria da Computao .
 Mais do que qualquer perodo

 precedente , mereceu ser conhecido como a idade urea da Matemtica .

 O que se acrescentou ao assunto durante esses 100 anos supera de

 longe tanto em quantidade como em qualidade a produo total

 combinada de todas as pocas precedentes .
 Com uma possvel exceo

 da idade conhecida na matemtica como idade herica , na Grcia

 antiga , foi uma das mais revolucionrias etapas do desenvolvimento

 dessa cincia e consequentemente tambm da Computao .
 Ser

 particularmente objeto de estudo a evoluo da Lgica Simblica -

 ou Lgica Matemtica - que teve Leibniz como predecessor distante .

 A partir de meados do sculo XIX a lgica formal se elabora como um

 clculo algbrico , adotando um simbolismo peculiar para as diversas

 operaes lgicas .
 Graas a este novo mtodo , puderam-se construir

 grandes sistemas axiomticos de lgica , de maneira parecida com a

 matemtica , com os quais se podem efetuar com rapidez e

 simplicidade raciocnios que a mente humana no consegue

 espontaneamente .

 A Lgica Simblica - Lgica Matemtica a partir daqui - , tem o

 mesmo objeto que a lgica formal tradicional : estudar e fazer

 explcitas as formas de inferncia , deixando de lado - por

 abstrao - o contedo de verdades que estas formas possam

 transmitir .
 No se trata aqui de estudar Lgica , mas chamar a

 ateno para a perspectiva que se estava abrindo com o clculo

 simblico : a automatizao de algumas operaes do pensamento .
 A

 Mquina de Turing , conceito abstrato que efetivamente deu incio 

 era dos computadores , baseou-se no princpio de que a simples

 aplicao de regras permite passar mecanicamente de uns smbolos a

 outros , sistema lgico que foi inaugurado por Boole .

 Entretanto a lgica booleana estava limitada ao raciocnio

 proposicional e somente mais tarde , com o desenvolvimento dos

 quantificadores , a lgica formal estava pronta para ser aplicada ao

 raciocnio matemtico em geral .
 Os primeiros sistemas foram

 desenvolvidos por F.L.G .
 Frege e G. Peano .
 Ao lado destes ser

 necessrio citar George Cantor ( 1829-1920 ) , matemtico alemo que

 abriu um novo campo dentro do mundo da anlise , nascida com Newton

 e Leibniz , com sua teoria sobre conjuntos infinitos .

 No comeo do sculo XX a Lgica Simblica se organizar com mais

 autonomia em relao  matemtica e se elaborar em sistemas

 axiomticos desenvolvidos , que se colocam em alguns casos como

 fundamento da prpria matemtica e que prepararo o surgimento do

 computador .

 Boole e os fundamentos da Lgica Matemtica e da Computao

 [ topo ]

 O ingls George Boole ( 1815-1864 )  considerado o fundador da

 Lgica Simblica .
 Ele desenvolveu com sucesso o primeiro sistema

 formal para raciocnio lgico .
 Mais ainda , Boole foi o primeiro a

 enfatizar a possibilidade de se aplicar o clculo formal a

 diferentes situaes , e fazer operaes com regras formais ,

 desconsiderando noes primitivas .

 Sem Boole , um pobre professor autodidata em Matemtica , o caminho

 onde se ligou a Lgica  Matemtica talvez demorasse muito a ser

 construdo .
 Com relao  Computao , se a Mquina Analtica de

 Babbage ( ver captulo sobre a Pr-Histria Tecnolgica ) foi apenas

 uma tentativa bem inspirada que teve pouco efeito sobre os futuros

 construtores do computador , sem a lgebra booleana , no entanto , a

 tecnologia computacional no teria progredido com facilidade at a

 velocidade da eletrnica .

 Durante quase mais de dois mil anos a lgica formal dos gregos ,

 conhecida pela sua formulao silogstica , foi universalmente

 considerada como completa e incapaz de sofrer uma melhora

 essencial .
 Mais do que isso , a lgica aristotlica parecia estar

 destinada a ficar nas fronteiras da metafsica j que somente se

 tratava , a grosso modo , de uma manipulao de palavras .
 No se

 havia ainda dado o salto para um simbolismo efetivo , embora Leibniz

 j tivesse aberto o caminho com suas idias sobre o " alfabeto do

 pensamento " .

 Foi Boole em sua obra The Mathematical Analysis of Logic ( 1847 )

 quem forneceu uma idia clara de formalismo e a desenvolveu de modo

 exemplar .
 Boole percebeu que poderia ser construda uma lgebra de

 objetos que no fossem nmeros , no sentido vulgar , e que tal

 lgebra , sob a forma de um clculo abstrato , seria capaz de ter

 vrias interpretaes .
 O que chamou a ateno na obra foi a clara

 descrio do que seria a essncia do clculo , isto  , o formalismo ,

 o procedimento , conforme o prprio George Boole descrevia , " cuja

 validade no depende da interpretao dos smbolos mas sim da

 exclusiva combinao dos mesmos " .
 Ele concebeu a lgica como uma

 construo formal  qual se busca posteriormente um interpretao .

 Boole criou o primeiro sistema bem sucedido para o raciocnio

 lgico , tendo sido pioneiro ao enfatizar a possibilidade de se

 aplicar o clculo formal em diferentes situaes e fazer clculos

 de acordo com regras formais , desconsiderando as interpretaes dos

 smbolos usados .
 Atravs de smbolos e operaes especficas , as

 proposies lgicas poderiam ser reduzidas a equaes e as equaes

 silogsticas poderiam ser computadas , de acordo com as regras da

 lgebra ordinria .
 Pela aplicao de operaes matemticas puras e

 contando com o conhecimento da lgebra booleana  possvel tirar

 qualquer concluso que esteja contida logicamente em qualquer

 conjunto de premissas especficas .

 De especial interesse para a Computao , sua idia de um sistema

 matemtico baseado em duas quantidades , o ' Universo ' e o ' Nada ' ,

 representados por ' 1 ' e ' 0 ' , o levou a inventar um sistema de dois

 estados para a quantificao lgica .
 Mais tarde os construtores do

 primeiro computador entenderam que um sistema com somente dois

 valores pode compor mecanismos para perfazer clculos .

 Boole estava convencido de que sua lgebra no somente demonstrou a

 equivalncia entre Matemtica e Lgica , mas que tambm representou

 a sistematizao do pensamento humano .
 A cincia , a partir de

 Boole , viu que a razo humana  mais complicada e ambgua , difcil

 de ser conceituada e mais poderosa que a lgica formal .
 Mas do

 ponto de vista da Matemtica e da Computao , a lgica simblica

 booleana foi importante - e s os anos fizeram ver - pois a lgica

 de at ento era incompleta e no explicava muitos princpios de

 deduo empregados em raciocnios matemticos elementares .

 No entanto a lgica booleana estava limitada ao raciocnio

 proposicional , e somente aps o desenvolvimento de quantificadores ,

 introduzidos por Pierce ,  que a lgica formal pde ser aplicada ao

 raciocnio matemtico geral .
 Alm de Peirce , tambm Schder e

 Jevons aperfeioaram e superaram algumas restries do sistema

 booleano : disjuno exclusiva , emprego da letra v para exprimir

 proposies existenciais , admisso de coeficientes numricos alm

 do 0 e 1 e o emprego do sinal de diviso .
 O resultado mais

 importante no entanto foi a apresentao do clculo de uma forma

 extremamente axiomatizada .

 A importncia de Frege e Peano

 [ topo ]

 Frege ( 1848-1925 ) e Peano ( 1858-1932 ) trabalharam para fornecer

 bases mais slidas  lgebra e generalizar o raciocnio matemtico .

 Gottlob Frege ocupa um lugar de destaque dentro da Lgica .
 Embora

 no to conhecido em seu tempo e bastante incompreendido , deve-se

 ressaltar que ainda hoje torna-se difcil descrever a quantidade de

 conceitos e inovaes , muitas revolucionrias , que elaborou de

 forma exemplar pela sua sistematizao e clareza .
 Muitos autores

 comparam seu Begriffsschrift aos Primeiros Analticos de

 Aristteles , pelos pontos de vista totalmente geniais .

 Frege foi o primeiro a formular com preciso a diferena entre

 varivel e constante , assim como o conceito de funo lgica , a

 idia de uma funo de vrios argumentos , o conceito de

 quantificador .
 A ele se deve uma conceituao muito mais exata da

 teoria aristotlica sobre sistema axiomtico , assim como uma clara

 distino entre lei e regra , linguagem e metalinguagem .
 Ele  autor

 da teoria da descrio e quem elaborou sistematicamente o conceito

 de valor .
 Mas isto no  tudo , pois todas estas coisas so apenas

 produtos de um empreendimento muito maior e fundamental , que o

 inspirou desde suas primeiras pesquisas : uma investigao das

 caractersticas daquilo que o homem diz quando transmite informao

 por meio de juzos .

 Na verdade o que Frege chamou de Lgica - assim como seus

 contemporneos Russell e Wittgenstein - no  o que hoje  chamado

 Lgica , fruto do formalismo e da teoria dos conjuntos que acabaram

 por predominar entre os matemticos , mas sim nossa semntica , uma

 disciplina sobre o contedo , natureza desse contedo e estrutura .

 Frege gastou considervel esforo na separao de suas concepes

 lgicas daquelas concepes dos ' lgicos computacionais ' como

 Boole , Jevons e Schreder .
 Estes estavam , como j foi dito ,

 empenhados no desenvolvimento de um clculo do raciocnio como

 Leibniz propusera , mas Frege queria algo mais ambicioso : projetar

 uma lingua characteristica .
 Dizia ele que uma das tarefas da

 filosofia era romper o domnio da palavra sobre o esprito humano .

 O uso de um sistema simblico , que at ento somente se pensava

 para a matemtica , procurou-o usar Frege tambm para a filosofia :

 um simbolismo que retratasse o que se pode dizer sobre as coisas .

 Ele buscava algo que no somente descrevesse ou fosse referido a

 coisas pensadas , mas o prprio pensar .

 Os lgicos tradicionais estavam basicamente interessados na soluo

 de problemas tradicionais de lgica , como por exemplo a validade .
 O

 objetivo de Frege foi mais alm : entrou no campo da semntica , do

 contedo , do significado , onde encontrou o fundamento ltimo da

 inferncia , da validade , etc .
 Frege acabou derivando para uma

 filosofia da lgica e da matemtica e influenciou diretamente a

 Russell , David Hilbert , Alonzo Church e Carnap .
 Destes , Hilbert e

 Church tm um papel decisivo na Histria conceitual da Cincia da

 Computao .

 Frege desejava provar que no somente o raciocnio usado na

 matemtica , mas tambm os princpios subjacentes - ou seja , toda a

 matemtica - so pura lgica .
 Porm ele expressou suas buscas e

 resultados - pelos quais acabou sendo considerado um dos pais da

 Lgica moderna , de uma forma excessivamente filosfica , em uma

 notao matemtica no convencional .
 O mrito maior de Frege foi

 elaborar uma concepo lgica mais abrangente do que a Lgica de

 Aristteles .
 Em um procedimento que lembra a " characteristica

 universalis " ^ .
 Frege construiu um sistema especial de smbolos para

 desenvolver a lgica de maneira exata e foi muito alm das

 proposies e dos argumentos .
 Em sua grandes obras , Begriffsschrift

 ( Ideografia ou Conceitografia ) e Grundgesitze ( Leis Fundamentais da

 Aritmtica , Ideograficamente Deduzidas ) , est contida de modo

 explcito e plenamente caracterizado uma srie de conceitos -

 conectivos , funo , funo proposicional , quantificadores , etc. -

 que seriam vitais para a Lgica Matemtica a partir de ento .

 Foi atravs do contato com a obra de Frege que Bertrand Russell

 procurou levar avante a idia de construir toda a matemtica sobre

 bases lgicas , convencido de que ambas so idnticas .
 Os postulados

 fregianos , adotados primeiramente por Peano , foram incorporados por

 Russell , que extendeu as teses logicistas de Frege  Geometria e s

 disciplinas matemticas em geral .

 Peano tinha objetivo semelhante a Frege , mas mais realista .
 Ele

 desenvolveu uma notao formal para raciocnio matemtico que

 procurasse conter no s a lgica matemtica mas todos os ramos

 mais importantes dela .
 O simbolismo de Peano e seus axiomas - dos

 quais dependem tantas construes rigorosas na lgebra e anlise -

 " representam a mais notvel tentativa do sculo de reduzir a

 aritmtica comum , e portanto a maior parte da matemtica , a um puro

 simbolismo formal .
 Aqui o mtodo postulacional atingiu novo nvel

 de preciso , sem ambiguidade de sentido , sem hipteses ocultas " ^ .

 J Hilbert procurou colocar em prtica a teoria da demonstrao de

 Frege , e pode-se ver nessas palavras de Frege as idias

 implementadas posteriormente no programa hilbertiano : " a inferncia

 procede pois , em meu sistema de escrita conceitual

 ( Begriffsschrift ) , seguindo uma espcie de clculo .
 No me refiro a

 este em sentido estrito , como se fosse um algoritmo que nele

 predominasse , ( ...
 ) , mas no sentido de que existe um algoritmo

 total , quer dizer , um conjunto de regras que resolvem a passagem de

 uma proposio ou de duas , a outra nova , de tal forma que nada se

 d que no esteja de acordo com estas regras .
 Minha meta  pois uma

 ininterrupta exigncia de preciso no processo de demonstrao , e a

 mxima exatido lgica , ao mesmo tempo que clareza e brevidade " .

 Pode-se notar a partir desse momento uma guinada no conceito de

 Lgica : o objeto da investigao lgica j no so mais as prprias

 frmulas , mas as regras de operao pelas quais se formam e se

 deduzem .

 _________________________________________________________________

 O desenvolvimento da Lgica Matemtica

 [ topo ]

 Uma das metas dos matemticos no final do sculo XIX foi a de obter

 um rigor conceitual das noes do clculo infinitesimal ( limite ,

 continuidade , infinito matemtico , etc. ) .
 Tal programa foi chamado

 de " aritmetizao da anlise " , isto  , a busca da reduo dos

 conceitos fundamentais da anlise ( a matemtica que tem como base a

 teoria dos nmero reais ) aos conceitos da aritmtica ( a matemtica

 que tem como base a teoria dos nmero inteiros positivos , isto  ,

 dos nmeros naturais e por extenso dos nmeros racionais ) .

 Por exemplo , ao invs de se tomar o nmero imaginrio como uma

 entidade um tanto misteriosa , pode-se defin-lo como um par

 ordenado de nmeros inteiros ( 0,1 ) , sobre o qual se realizam certas

 operaes de " adio " e " multiplicao " .
 Analogamente , o nmero

 irracional se definia numa certa classe de nmeros irracionais ,

 cujo quadrado  menor do que 2 .
 Dado que a Geometria podia ser

 reduzida  Anlise ( Geometria Analtica ) , a Aritmtica vinha a se

 configurar como a base natural de todo o edifcio matemtico .
 O

 ponto culminante deste processo foram os axiomas de Peano ( 1899 ) ,

 que fundamentaram toda a Aritmtica elementar posterior .

 Ao mesmo tempo , matemticos como Frege , Cantor e Russell , no

 convencidos da " naturalidade " da base constituda pela aritmtica ,

 procuravam conduzir a prpria aritmtica a uma base mais profunda ,

 reduzindo o conceito de nmero natural ao conceito lgico de

 classe , ou para recorrer a Cantor , definir nmero em termos de

 conjunto , de modo que a lgica das classes apresentava-se como a

 teoria mais adequada para a investigao sobre os fundamentos da

 matemtica .
 O esforo dos matemticos foi o de dar  lgebra uma

 estrutura lgica , procurando-se caracterizar a matemtica no tanto

 pelo seu contedo quanto pela sua forma .

 Bochenski , falando da histria da Lgica Matemtica , diz que a

 partir de 1904 , com Hilbert , inicia-se um novo perodo dessa

 cincia ento emergente , que se caracteriza pela apario da

 Metalgica ( Hilbert , Lwenheim e Scholem ) e , a partir de 1930 , por

 uma sistematizao formalista desta mesma Metalgica .
 Iniciaram-se

 discusses sobre o valor e os limites da axiomatizao , o nexo

 entre Lgica e Matemtica , o problema da verdade ( Hilbert , Gdel ,

 Tarski ) .

 A Metalgica , em sua vertente sinttica ocupa-se das propriedades

 externas dos clculos , como por exemplo a consistncia , a

 completude , a decidibilidade dos sistemas axiomticos e a

 independncia dos axiomas .
 Hilbert , Gdel e Church so autores

 neste campo .
 Em sua parte semntica , a Metalgica dirige-se ao

 significado dos smbolos , dos clculos com relao a um determinado

 mundo de objetos .
 Tarski , Carnap e Quino , entre outros se

 interessaram por estas questes .

 Apareceram tambm novos sistemas lgicos : as lgicas naturais , de

 Gentzen e Jaskowski , lgica polivalente de Post e Lukasiewicz , e a

 lgica intuicionista de Heytings .

 Complementando essas idias cabe destacar alguns sistemas originais

 de outros matemticos como Schnfinkel ( 1924 ) , Curry ( 1930 ) , Kleene

 ( 1934 ) , Rosser ( 1935 ) e o j citado Alonzo Church ( 1941 ) .
 Deve-se

 lembrar que quase todos estes ltimos , junto com o logiscista

 ingls Alan M. Turing , acabaram por definir , antes mesmo de existir

 o computador propriamente , a natureza da computao , e as

 implicaes e limites do pensamento humano atravs de uma mquina .

 ______________________________________________________________

 A crise dos fundamentos , as tentativas de superao e David Hilbert

 [ topo ]

 At aqui as disciplinas dedutivas atingiram um alto grau de

 perfeio lgica .
 Mas algumas dvidas comearam a abalar a

 confiana dos matemticos : o surgimento , por volta de 1900 , de

 numerosos paradoxos ou antinomias , especialmente na teoria dos

 conjuntos .
 O surgimento de tais contradies mostrava que havia

 algum defeito nos mtodos .
 Ser que se poderia ter certeza de que

 em se usando os axiomas de um sistema rigidamente lgico - o grande

 sonho de tantos matemticos do incio do sculo XX de reduzir a

 matemtica e o conhecimento  lgica - , nunca se chegaria a uma

 contradio , dentro dos axiomas do sistema ?
 Este quadro estimulou a

 criatividade matemtica .
 Na tentativa de se resolverem os paradoxos

 surgiram 3 grandes escolas da lgica : a Logicista , a

 Intuicionista ^ e a Formalista ( h um excelente trabalho para

 explicar essas escolas , em linguagem apropriada para o

 no-especialista , em ) .

 Mas , retornando ao problema dos paradoxos acima citado , estava

 iminente , nos fins do sculo XIX , uma inevitvel coliso entre

 matemtica e filosofia .
 Alguns vagos conceitos metafsicos

 associados com o pensamento humano j tinham chamado a ateno de

 matemticos das duas primeira dcadas do sculo XX , que passaram a

 procurar a verdadeira natureza do raciocnio dentro da cincia

 matemtica .
 O que  um procedimento correto ?
 , qual a relao entre

 verdade e demonstrao ?
 ,  possvel fornecer uma prova para todos

 os enunciados matemticos verdadeiros ?
 E o problema das

 ambiguidades , j que a matemtica sempre foi feita atravs de uma

 linguagem natural ?
 Sem falar na crise dos paradoxos , subjacente a

 tudo isso !

 A escola logicista rapidamente ficou exposta a fortes crticas .

 Frege , Peano e Russell , devido ao seu platonismo , acreditavam em

 um mundo objetivo , existente por si mesmo , de entes e relaes

 matemticas que o pesquisador deve descobrir e no inventar .

 Bertrand Russell tinha objetivos ainda maiores : utilizar o

 instrumental da lgica como ponto de partida do pensamento

 filosfico , atravs da gerao de uma linguagem perfeita .
 Mas a

 matemtica , enquanto perquirio pura , independe teoricamente

 dessas aplicaes , bastando ver as pesquisas atuais .
 Deve-se no

 entanto destacar o grande mrito dessa escola de incrementar

 grandemente o progresso da logstica e confirmar a unio ntima

 entre matemtica e lgica .

 O programa intuicionista sofreu tambm fortes crticas ,

 principalmente a de desfigurar a matemtica , tornando-a algo

 subjetivo e praticamente impossvel .
 O prprio modo de se provar a

 no-contradio de uma teoria matemtica , buscando um ' modelo ' dos

 axiomas desta teoria dentro de outra teoria j existente ( e que era

 considerada coerente ) mostrou-se pouco confivel : como dar a

 certeza da no-contraditoriedade dessa outra teoria ?
 A maior parte

 dos matemticos dos nossos dias afastou-se desta linha de

 pensamento .
 Positivamente falando , sua severa crtica  matemtica

 tradicional obrigou os especialistas nos fundamentos a

 desenvolverem novos mtodos para reabilitar a teoria clssica .
 A

 escola formalista progrediu bastante atravs das polmicas com os

 intuicionistas ^ .

 Para David Hilbert ( 1862-1943 ) e outros , o problema de estabelecer

 fundamentos rigorosos era o grande desafio ao empreendimento de

 tantos , que pretendiam reduzir todas as leis cientficas a equaes

 matemticas , e que teve como pice os anos da dcada de 1930 .

 Atravs de dois relatrios , em 1922 e 1923 , props o chamado

 Programa Hilbertiano , voltado para uma prova no mais ' relativa ' ( a

 outro sistema ) , mas direta e absoluta de um sistema axiomtico .
 Era

 necessrio colocar a matemtica em bases rigorosamente slidas , com

 axiomas e regras de procedimento que deveriam ser estabelecidos em

 carter definitivo .
 Todos estes estudos denominaram-se

 Metamatemtica ou Metalgica , pela conectividade das duas .

 Hilbert props-se demonstrar a coerncia da aritmtica para depois

 estender tal coerncia aos mbitos dos demais sistemas .
 Ele apostou

 na possibilidade da criao de uma linguagem puramente sinttica ,

 sem significado , a partir da qual se poderia falar a respeito da

 verdade ou falsidade dos enunciados .
 Tal linguagem foi e  chamada

 de sistema formal , e est resumida no anexo III .
 Isto era o centro

 da doutrina formalista , que mais tarde estimularia Turing a fazer

 descobertas importantes sobre as capacidades das mquinas .

 Lembre-se tambm que John von Neumann , a quem muitos atribuem a

 construo do primeiro computador , era um aluno de Hilbert e um dos

 principais tericos da escola formalista .

 Um problema fundamental neste processo de formalizao da

 aritmtica era perguntar se existe um procedimento finito pelo qual

 seja possvel decidir a verdade ou falsidade de qualquer enunciado

 aritmtico .
 Em 1900 , no Segundo Congresso Internacional de

 Matemtica , realizado em Paris , David Hilbert props uma lista de

 23 problemas cuja soluo " desafiar futuras geraes de

 matemticos " .
 Vrios deles foram desde ento resolvidos e alguns

 resistem at hoje , permanecendo ainda em aberto .

 O segundo problema da referida lista estava relacionado com a

 confiabilidade do raciocnio matemtico , isto  , se ao seguir as

 regras de determinado raciocnio matemtico no se chegaria a

 contradies .
 Relacionado com ele , o problema de nmero dez 

 especialmente interessante para a Computao .
 Era de enunciado

 bastante simples : descreva um algoritmo que determine se uma dada

 equao diofantina do tipo P ( u [ 1 ] , u [ 2 ] , ...
 , u [ n ] ) = 0 , onde P  um

 polinmio com coeficientes inteiros , tem soluo dentro do conjunto

 dos inteiros .
  o famoso problema da decidibilidade , o

 Entscheidungsproblem .
 Este problema consistia em indagar se existe

 um procedimento mecnico efetivo para determinar se todos os

 enunciados matemticos verdadeiros poderiam ser ou no provados ,

 isto  , se eles poderiam ser deduzidos a partir de um dado conjunto

 de premissas .

 Tambm a questo da consistncia era decisiva para Hilbert , pois 

 uma condio necessria para o sistema axiomtico do tipo que ele

 tinha em mente .
 Aristteles j tinha mostrado que se um sistema 

 inconsistente , qualquer afirmao poderia ser provada como falsa ou

 verdadeira .
 Neste caso no seria possvel ter um fundamento slido

 para qualquer tipo de conhecimento , matemtico ou no .
 Anos mais

 tarde , em 1928 , no Congresso Internacional de Matemticos ,

 realizado em Bolonha , Itlia , Hilbert lanou um novo desafio , que

 na verdade somente enfatizava aspectos do segundo e no dcimo

 problema j descritos .
 Hilbert queria saber se  possvel provar

 toda assertiva matemtica verdadeira .
 Hilbert estava buscando algo

 como uma " mquina de gerar enunciados matemticos verdadeiros " : uma

 vez alimentada com um enunciado matemtico , poderia dizer se o

 enunciado  falso ou verdadeiro .
  um problema que est

 relacionado com o citado projeto hilbertiano da busca de um sistema

 formal completo ( onde toda assertiva matemtica verdadeira pode ser

 provada no sistema ) e consistente ( uma verdade matemtica e sua

 negao no podem ambas ser provadas no sistema ) .

 Ao mesmo tempo , em 1927 , com 22 anos , von Neumann publicou 5

 artigos que atingiram fortemente o mundo acadmico .
 Trs deles

 consistiam em crticas  fsica quntica , um outro estabelecia um

 novo campo de pesquisas chamado Teoria dos Jogos , e , finalmente , o

 que mais impactou o desenvolvimento da Computao : era o estudo do

 relacionamento entre sistemas formais lgicos e os limites da

 matemtica .
 Von Neumann demonstrou a necessidade de se provar a

 consistncia da matemtica , um passo importante e crtico tendo em

 vista o estabelecimento das bases tericas da Computao ( embora

 ningum tivesse esse horizonte por enquanto ) .

 J foi citado no captulo sobre o Desenvolvimento da Lgica

 Matemtica o desafio dos matemticos do incio do sculo de

 aritmetizar a anlise .
 Eles estavam de acordo no que diz respeito

 s proposies geomtricas e outros tipos de afirmaes

 matemticas : que poderiam ser reformuladas e reduzidas a afirmaes

 sobre nmeros .
 Logo , o problema da consistncia da matemtica

 estava reduzido  determinao da consistncia da aritmtica .

 Hilbert estava interessado em dar uma teoria da aritmtica , isto  ,

 um sistema formal que fosse finitisticamente descritvel ,

 consistente , completo e suficientemente poderoso para descrever

 todas as afirmaes que possam ser feitas sobre nmeros naturais .
 O

 que Hilbert queria em 1928 era que para uma determinada afirmao

 matemtica , por exemplo , " a soma de dois nmeros mpares  sempre

 um nmero par " , houvesse um procedimento que , aps um nmero finito

 de passos , parasse e indicasse se aquela afirmao poderia ou no

 ser provada em determinado sistema formal , suficientemente poderoso

 para abranger a aritmtica ordinria .
 Isto est diretamente

 relacionado com o trabalho de Gdel e Alan Turing .

 Pode-se afirmar que em geral a lgica matemtica prestou nestes

 tempos maior ateno  linguagem cientfica , j que seu projeto era

 o da elaborao de uma linguagem lgica de grande preciso , que

 fosse boa para tornar transparentes as estruturas lgicas de

 teorias cientficas .
 Tal projeto encontrou seus limites , tanto na

 ordem sinttica como na ordem semntica ( por exemplo com os

 clebres teoremas de limitao formal ) .
 Este fenmeno levou a uma

 maior valorizao da linguagem ordinria , que , apesar de suas

 flutuaes e imprecises , encerram uma riqueza lgica que os

 clculos formais no conseguem recolher de todo .
 Dentro da prpria

 matemtica - como se ver mais adiante com Gdel - h verdades que

 no podem ser demonstradas mediante uma deduo formal , mas que

 podem ser demonstradas - o teorema da incompletude de Gdel  uma

 prova disso - mediante um raciocnio metamatemtico informal .
 A

 partir desse propsito de construo de uma linguagem ideal surgiu

 a filosofia da linguagem ( Moore , Wittgenstein , Geach em sua segunda

 etapa ) colocando as questes lgicas sobre nova tica .

 Na verdade , tanto a lgica matemtica em sentido estrito como os

 estudos de semntica e filosofia da linguagem depararam-se com

 problemas filosficos que no se resolvem somente dentro de uma

 perspectiva lgica .
 H questes de fundo da lgica matemtica que

 pertencem j a uma filosofia da matemtica .

 Todos esses desafios abriram uma porta lateral para a Computao e

 deram origem a um novo e decisivo captulo na sua Histria .
 Da

 tentativa de resolv-los ocorreu uma profunda revoluo conceitual

 na Matemtica - o Teorema de Gdel - e surgiu o fundamento bsico

 de todo o estudo e desenvolvimento da Computao posterior : a

 Mquina de Turing .

 _________________________________________________________________

 Kurt Gdel e o indecidvel

 [ topo ]

 Em 1931 , o matemtico Kurt Gdel ( 1906-1978 ) publicou alguns

 resultados de suas pesquisas , que mudaram o rumo dos estudos da

 Cincia Matemtica e atingiram profundamente o formalismo .
 Entre

 eles est o famoso Teorema de Gdel sobre as proposies

 indecidveis , que diz o seguinte :

 A .
 Se S  um sistema formal suficientemente forte para conter a

 aritmtica elementar , ento S  incompleto ou inconsistente ;

 B .
 A eventual consistncia de um tal sistema formal no pode ser

 provada apenas com recursos daquele mesmo sistema .

 Kurt Gdel demonstrou que no  possvel construir uma teoria

 axiomtica dos nmeros que seja completa , como pretendia Hilbert .

 A primeira parte do teorema citado significa que existem

 proposies aritmticas tais que nem elas nem sua negao so

 demonstrveis na aritmtica adotada .
 So proposies indecidveis .

 Logo , em qualquer axiomtica consistente baseada em aritmtica

 existem sentenas indecidveis .
 Como uma proposio e sua negao

 so contraditrias - admitindo-se o princpio do terceiro excludo

 - , ento uma delas  verdadeira .
 Portanto existem sentenas

 aritmticas verdadeiras , formulveis em uma determinada axiomtica

 baseada em aritmtica , que no podem ser provadas .
 A segunda parte

 do teorema diz que a prova de ausncia de contradio em uma

 axiomtica da aritmtica no pode ser realizada apenas com os

 recursos dessa axiomtica .

 Para o desenvolvimento de seus estudos Gdel concebeu uma

 interessante formulao de smbolos , frmulas e provas atravs de

 nmeros , bem como mostrou que as proposies metamatemticas -

 alis sem isso no poderia ter realizado sua prova - podem estar

 adequadamente refletidas dentro do prprio clculo , aritmetizando

 assim a prpria metamatemtica .
 No anexo IV h um pequeno resumo

 sobre a prova de Gdel .

 Gdel acabou com o sonho logicista , visto que no se pode

 desenvolver toda a aritmtica ( e muito menos toda a matemtica ) num

 sistema que seja ao mesmo tempo consistente e completo .
 Tambm

 acabou com o sonho formalista : existem enunciados matemticos que

 so verdadeiros , mas no so suscetveis de prova , isto  , existe

 um abismo entre verdade e demonstrao .

 Gdel , no entanto , ao longo da demonstrao do seu teorema rompeu

 um limiar crucial entre a lgica e a matemtica .
 Ele mostrou que

 qualquer sistema formal que seja to rico quanto um sistema

 numrico qualquer , que contenha os operadores " + " e " = " , pode ser

 expresso em termos aritmticos .
 Isto significa que por mais

 complexa que se torne a matemtica ( ou qualquer outro sistema

 formal redutvel a ela ) , ela pode sempre ser expressa em termos de

 operaes a serem executadas sobre nmeros , e as partes do sistema

 podero ser manipuladas por regras de contagem e comparao .
 Outro

 resultado fundamental do teorema da incompletude de Gdel pode-se

 considerar como sendo a demonstrao de que h algumas funes

 sobre os inteiros que no podem ser representadas por um algoritmo ,

 ou seja , que no podem ser computadas .
 Posteriormente verificou-se

 a existncia de uma equivalncia entre o Teorema da Incompletude de

 Gdel e o problema da parada de Turing .

 _________________________________________________________________

 Alan Mathison Turing : o bero da Computao

 [ topo ]

 A revoluo do computador comeou efetivamente a realizar-se no ano

 de 1935 , em uma tarde de vero na Inglaterra , quando Alan M. Turing

 ( 1912-1954 ) , estudante do King's College , Cambridge , durante curso

 ministrado pelo matemtico Max Neumann , tomou conhecimento do

 Entscheidungsproblem de Hilbert .
 Enquanto isso , conforme foi

 brevemente citado no item precedente , uma parte da comunidade dos

 matemticos buscava um novo tipo de clculo lgico , que pudesse ,

 entre outras coisas , colocar em uma base matemtica segura o

 conceito heurstico do que seja proceder a um cmputo .
 O resultado

 destas pesquisas era fundamental para o desenvolvimento da

 matemtica : tratava-se de saber se  possvel haver um procedimento

 efetivo para se solucionar todos os problemas de uma determinada

 classe que estivesse bem definida .
 O conjunto desses esforos

 acabou por formar a fundamentao terica da que veio a ser chamada

 " Cincia da Computao " .

 Os resultados de Gdel e o problema da deciso motivaram Turing

 primeiramente a tentar caracterizar exatamente quais funes so

 capazes de ser computadas .
 Em 1936 , Turing consagrou-se como um dos

 maiores matemticos do seu tempo , quando fez antever aos seus

 colegas que  possvel executar operaes computacionais sobre a

 teoria dos nmeros por meio de uma mquina que tenha embutida as

 regras de um sistema formal .
 Turing definiu uma mquina terica que

 se tornou um conceito chave dentro da Teoria da Computao .
 Ele

 enfatizou desde o incio que tais mecanismos podiam ser construdos

 e sua descoberta acabou abrindo uma nova perspectiva para o esforo

 de formalizar a matemtica , e , ao mesmo tempo , marcou fortemente a

 Histria da Computao .

 A percepo genial de Turing foi a substituio da noo intuitiva

 de procedimento efetivo por uma idia formal , matemtica .
 O

 resultado foi a construo de uma conceituao matemtica da noo

 de algoritmo , uma noo que ele modelou baseando-se nos passos que

 um ser humano d quando executa um determinado clculo ou cmputo .

 Turing formalizou definitivamente o conceito de algoritmo .

 A Mquina de Turing

 [ topo ]

 O trabalho de Alan Turing ficou documentado no artigo On

 Computable Numbers with an aplication to the

 Entscheidungsproblem , publicado em 1936 .
 Turing descreveu em

 termos matematicamente precisos como pode ser poderoso um

 sistema formal automtico , com regras muito simples de

 operao .

 " O que faz o raciocnio humano quando executa um clculo " ?
 ,

 perguntou-se Turing .
 Ele definiu que os clculo mentais

 consistem em operaes para transformar nmeros em uma srie de

 estados intermedirios que progridem de um para outro de acordo

 com um conjunto fixo de regras , at que uma resposta seja

 encontrada .
 Algumas vezes  usado o papel e o lpis para no se

 perder o estado dos nossos clculos .
 As regras da matemtica

 exigem definies mais rgidas que aquelas descritas nas

 discusses metafsicas sobre os estados da mente humana , e

 Turing concentrou-se na definio destes estados de tal maneira

 que fossem claros e sem ambiguidades , para que tais definies

 pudessem ser usadas para comandar as operaes da mquina .

 Turing comeou com uma descrio precisa de um sistema formal ,

 na forma de " tabela de instrues " que especificariam quais

 movimentos a fazer para qualquer configurao possvel dos

 estados no sistema .
 Provou ento que os passos de um sistema

 axiomtico formal semelhante  lgica e os estados da mquina

 que fazem os " movimentos " em um sistema formal automtico so

 equivalentes entre si .
 Estes conceitos esto todos subjacentes

 na tecnologia atual dos computadores digitais , cuja construo

 tornou-se possvel uma dcada depois da publicao de Turing .

 Um sistema formal automtico  um dispositivo fsico que

 manipula automaticamente os smbolos de um sistema formal de

 acordo com as suas regras .
 A mquina terica de Turing

 estabelece tanto um exemplo da sua teoria da computao como

 uma prova de que certos tipos de mquinas computacionais

 poderiam , de fato , ser construdas .
 Efetivamente , uma Mquina

 de Turing Universal , exceto pela velocidade , que depende do

 hardware , pode simular qualquer computador atual , desde os

 supercomputadores at os computadores pessoais , com suas

 complexas estruturas e poderosas capacidades computacionais ,

 dado o tempo e memria necessrios .
 Alan Turing provou que para

 qualquer sistema formal existe uma Mquina de Turing que pode

 ser programada para imit-lo .
 Ou em outras palavras : para

 qualquer procedimento computacional bem definido , uma Mquina

 de Turing Universal  capaz de simular uma mquina que execute

 tais procedimentos .

 De um ponto de vista terico , a importncia da Mquina de

 Turing est no fato de que ela representa um objeto matemtico

 formal .
 Atravs dela , pela primeira vez , se deu uma boa

 definio do que significa computar algo .
 E isso levanta a

 questo sobre o que exatamente pode ser computado com tal

 dispositivo matemtico .

 O problema da parada e o problema da deciso

 [ topo ]

 Turing mostrou que o funcionamento de sua mquina ( usar-se- a

 sigla MT a partir de agora ) e a aplicao das regras de

 formao de um sistema formal no tm diferena .
 Ele demonstrou

 tambm que seu dispositivo poderia resolver infinitos problemas

 mas havia alguns que no seriam possveis , porque no haveria

 jeito de se prever se o dispositivo pararia ou no .
 Colocando

 de uma outra maneira : dado um programa P para uma MT e uma

 determinada entrada de dados E , existe algum programa que leia

 P e E , e pare aps um nmero finito de passos , gerando uma

 configurao final na fita que informe se o programa P encerra

 sua execuo aps um nmero finito de passos ao processar E ?

 Comparando-se com as afirmaes sobre verdades aritmticas ,

 dentro de um sistema formal consistente da aritmtica , que no

 so passveis de prova dentro deste sistema , percebe-se que o

 problema da parada de Turing nada mais  do que o Teorema de

 Gdel , mas expresso em termos de uma mquina computacional e

 programas ao invs de uma linguagem de um sistema dedutivo da

 Lgica Matemtica .

 Em 1936 Turing provou formalmente o seguinte teorema :

 Teorema da Parada : Dado um programa P qualquer para uma Mquina

 de Turing e uma entrada E qualquer de dados para esse programa ,

 no existe uma Mquina de Turing especifica que pare aps um

 nmero finito de passos , e que diga se P em algum momento

 encerra sua execuo ao processar E .

 A soluo negativa deste problema computacional implica tambm

 numa soluo negativa para o problema de Hilbert .
 Portanto nem

 todos os enunciados verdadeiros da aritmtica podem ser

 provados por um computador .

 Figura : Relacionamento entre os mundos formais , matemticos e

 computacionais

 A tese de Church-Turing e outros resultados tericos

 [ topo ]

 Aps os resultados de Gdel em 1931 muitos lgicos matemticos

 partiram em busca do que seria uma noo formalizada de um

 procedimento efetivo ( por efetivo entenda-se mecnico ) , ou seja , o que

 pode ser feito seguindo-se diretamente um algoritmo ou conjunto de

 regras ( como j visto , antigo sonho de sculos , que remonta a

 Leibniz ) .
 Destas buscas surgiram :

 * a sistematizao e desenvolvimento das funes recursivas

 ( introduzidas nos trabalhos de Gdel ) por Stephen Cole Kleene

 ( 1909-1994 ) em sua teoria lgica da computabilidade ( parte de seu

 livro Introduo  Metamatemtica , um dos cumes da lgica

 matemtica dos ltimos anos ) ;

 * as Mquinas de Turing ;

 * clculo-lambda ( componente caracterstico fundamental da linguagem

 de programao LISP ) de Alonzo Church ;

 * a Mquina de Post , anloga  de Turing , tornada pblica um pouco

 depois , fruto de trabalho independente , e seu sistema para

 reescrita de smbolos ( cuja gramtica de Chomsky  um caso

 particular ) , de Emil L. Post ( 1897-1954 ) .

 Com efeito , todos estes conceitos levaram  mesma concluso e

 acabaram por ter o mesmo significado , dentro do citado escopo

 da busca de uma definio bem elaborada de processo efetivo .
 No

 presente trabalho referirer-se- mais a Church e Turing ( Kleene

 fez em seu trabalho uma ampla abordagem de ambos , tirando

 vrias consequncias , e Post trata do mesmo tema de Turing ) ,

 para se ter uma viso mais clara da diversificao dos estudos

 desta dcada de 1930 para a fundamentao terica de toda a

 Computao .

 Um clebre teorema de Alonzo Church ( 1903-1995 ) demonstrou em

 1936 que no pode existir um procedimento geral de deciso para

 todas as expresses do Clculo de Predicados de 1a ordem , ainda

 que exista tal procedimento para classes especiais de

 expresses de tal clculo .

 Isto pode causar certo espanto se se pensa que o Clculo de

 Predicados de 1a ordem  semanticamente completo , com o que se

 diz implicitamente que o prprio clculo , com seus axiomas e

 regras , constitui um algortmo capaz de enumerar uma aps outra

 todas as sua expresses vlidas .
 De fato , no entanto , estas

 expresses so indefinidamente numerosas , de modo que , mesmo

 sendo verdade que essa infinidade de expresses seja

 enumervel , ou seja , construveis passo a passo a partir dos

 axiomas , essa enumerao no tem fim .
 Compreende-se , ento que ,

 se se consegue demonstrar uma determinada frmula P em um certo

 momento , isto j basta para afirmar que se trata de uma frmula

 vlida .
 Pelo contrrio , se por exemplo depois de haver deduzido

 mil teoremas dos axiomas , P ainda no apareceu , no se pode

 afirmar nada , porque P poderia aparecer talvez aps outro

 milhar de teoremas , permitindo-se reconhecer sua validade , ou

 no aparecer nunca , por no ser vlida .
 Mas no se poder

 afimar em qual caso se est , mesmo depois das mil dedues .

 A deciso , dentro desse clculo seria possvel se se possuisse

 um algoritmo capaz de enumerar as expresses no vlidas .
 A

 expresso P ento aparecia dentro desse conjunto de no vlidas

 em algum momento .
 O teorema de Church de que se est tratando

 consiste fundamentalmente na demonstrao de que no existe

 algoritmo capaz de enumerar as expresses no vlidas , de

 maneira que fica excludo a priori todo procedimento de deciso

 para as expresses do Clculo de predicados , em geral .
 Para

 compreender as razes de semelhante fato seria necessrio

 valer-se das noes tcnicas relacionados com os conceitos da

 matemtica recursiva , que excedem amplamente os limites deste

 trabalho .

 Tambm Church estava interessado no problema de Hilbert .
 O

 resultado a que Turing tinha chegado em 1936 sobre o problema

 da deciso de Hilbert , Church o tinha alcanado tambm , alguns

 poucos meses antes , empregando o conceito formalizado de

 lambda-definibilidade ( ao invs do computvel por uma Mquina

 de Turing definido por Turing ) , no lugar do conceito informal

 procedimento efetivo ou mecnico .
 Kleene em 1936 mostrou que

 lambda-definibilidade  equivalente ao conceito de

 recursividade de Gdel-Herbrand e nesse meio tempo Church

 formulou sua tese que estabelecia que a recursividade  a

 prpria formalizao do efetivamente computvel .
 Isto foi

 estabelecido , no caso das funes dos inteiros positivos , por

 Church e Kleene , em 1936 .
 O clculo-lambda , como sistema

 elaborado por Church para ajudar a fundamentar a Matemtica

 ( 1932/33 ) era inconsistente , como o mostraram Kleene e Rosser

 ( 1935 ) .
 Mas a parte do clculo-lambda que tratava de funes

 recursivas estava correta e teve sucesso .
 Usando sua teoria

 Church props uma formalizao da noo de " efetivamente

 computvel " , atravs do conceito de lambda-definibilidade .

 Turing em 1936 e 1937 , ao dar a sua noo de computabilidade

 associada a uma mquina abstrata , mostrou que a noo

 Turing-computvel  equivalente  lambda-definibilidade .
 O

 trabalho de Church e Turing fundamentalmente liga os

 computadores com as MT .
 Os limites das MT , de acordo com a tese

 de Church-Turing , tambm descreve os limites de todos os

 computadores .

 O processo que determina o valor de uma funo atravs dos

 argumentos dessa funo  chamado de clculo da funo ( ou

 computar uma funo ) .
 Como foi observado , a mquina de Turing

 pode ser matematicamente interpretada como um algoritmo e

 efetivamente toda ao de uma mquina algortmica como o

 computador pode ser considerada como a de calcular o valor de

 uma funo com determinados argumentos .
 Este ' insight ' 

 interessante , pois d uma maneira de se medir a capacidade

 computacional de uma mquina .
 Necessita-se somente identificar

 as funes que se  capaz de computar e usar este conjunto como

 medida .
 Uma mquina que compute mais funes que outra  mais

 poderosa .

 A partir dos resultados de Gdel , Turing e Church , pode-se

 dizer que existem funes para as quais no existe uma

 sequncia de passos que determinem o seu valor , com base nos

 seus argumentos .
 Dizendo-se de outra maneira , no existem

 algoritmos para a soluo de determinadas funes .
 So as

 chamadas funes no computveis .
 Isto significa que para tais

 funes no h nem haver capacidade computacional suficiente

 para resolv-las .
 Logo , descobrir as fronteiras entre funes

 computveis e no computveis  equivalente a decobrir os

 limites do computador em geral .
 A tese de Church-Turing

 representa um importante passo nesse sentido .
 A percepo de

 Turing foi a de que as funes computveis por uma MT eram as

 mesmas funes computveis acima referidas .
 Em outras palavras ,

 ele conjecturou que o poder computacional das MT abarcava

 qualquer processo algoritmico , ou , analogamente , o conceito da

 MT propicia um contexto no qual todas as funes computveis

 podem ser descritas .
 Isto foi a contribuio dada pelo trabalho

 de Turing e Church : as funes computveis so as mesmas

 funes Turing-computveis .
 A importncia disso est na

 possibilidade de se verificar o alcance e limites de um

 computador .

 _________________________________________________________________

 Notas

  1 .
 Em um sistema axiomtico parte-se de premissas aceitas como

 verdadeiras e regras ditas vlidas , que iro conduzir a sentenas

 verdadeiras .
 As concluses podem ser alcanadas manipulando-se

 smbolos de acordo com conjuntos de regras .
 A Geometria de Euclides

  um clssico exemplo de um procedimento tornado possvel por um

 sistema axiomtico .

  2 .
 Parmnides ( 540 a 470 a.C. ) negava a existncia do movimento

 ( " devir " ) e afirmava a existncia de um nico ser ( pantesmo ) ,

 tendo enunciado o princpio da no contradio .
 Seu discpulo Zeno

 ( 490 a 430 a.C. ) foi o fundador da dialtica e radicalizou a

 negao do movimento .
 Este envolveria um paradoxo : para mudar

 completamente  preciso antes mudar parcialmente , e assim

 infinitamente , o que levaria a concluir que o movimento no existe

 ( paradoxos de Aquiles e a tartaruga e os pontos de percurso de uma

 flecha )

  3 .
 Modalidades so as expresses do tipo "  possvel que ...
 " , " 

 necessrio que ...
 " .

  4 .
 As definies pretendem substancialmente explicitar os

 conceitos da geometria ( " ponto  aquilo que no tem partes " ; " linha

  comprimento sem largura " , etc. ) .
 Os postulados representam

 verdades indubitveis tpicas do saber geomtrico ( " pode-se levar

 uma reta de qualquer ponto a qualquer ponto " ; " todos os ngulos

 retos so iguais " ; etc. ) .
 Os axiomas so verdades que valem

 universalmente , no s na geometria ( " o todo  maior que a parte " ;

 " coisas que so iguais a uma mesma coisa so iguais entre si " ,

 etc. ) .

  5 .
 Neste sentido foi o matemtico grego que maior influncia teve

 sobre a moderna teoria dos nmeros .
 Em particular Fermat foi levado

 ao seu ' ltimo ' teorema quando procurou generalizar um problema que

 tinha lido na Arithmetica de Diophantus : dividir um dado quadrado

 em dois quadrados ( ver F.E. Robbins , P.Mich .
 620 : A Series of

 Arithmetical Problems , Classical Philology , pg 321-329 , EUA , 1929 ) .

  6 .
 Sob certo aspecto isto se justificaria .
 Em uma viso um tanto

 arbitrria e simplista poderamos dividir o desenvolvimento da

 lgebra em 3 estdios : ( 1 ) primitivo , onde tudo  escrito em

 palavras ; ( 2 ) intermedirio , em que so adotadas algumas

 simplificaes ; ( 3 ) simblico ou final .
 Neste contexto , Arithmetica

 deve ser colocada na segunda categoria .

  7 .
 A palavra algoritmo na matemtica designa um procedimento

 geral de clculo , que se desenvolve , por assim dizer ,

 automaticamente , poupando-nos esforo mental durante o seu curso ;

 este termo ser depurado e aproveitado dentro da Computao , e dele

 se tornar a falar mais  frente

  8 .
 Lembrando algo que j foi dito ,  importante ressaltar que

 desde suas origens aristotlicas a lgica havia assumido claramente

 alguns recursos fundamentais , como a estrutura formal , o emprego de

 certo grau de simbolismo , a sistematizao axiomtica e o

 identificar-se com a tarefa de determinar as " leis " do discurso

 ( tomando , por exemplo , a linguagem como tema de estudo ) ,

 caractersticas que foram assumidas pela Lgica Moderna .

  9 .
 Deve-se observar que destas conceituaes descenderam a

 notao da matemtica e da lgica do sculo XX .

  10 .
 Newton e Leibniz descobriram o princpio fundamental do

 clculo de que uma integrao pode ser feita mais facilmente pela

 inverso do processo de diferenciao , no clculo das reas .

  11 .
 Em 1673 Gottfried Leibniz , usando uma engrenagem dentada ,

 construiu uma calculadora capaz de multiplicar , na qual um nmero

 era repetidamente e automaticamente somado a um acumulador .

  12 .
 Remonta aos gregos , particularmente Aristteles , como visto

 no captulo dos Primrdios , que a fundiu com a lgica filosfica em

 um conjunto de obras que posteriormente chamou-se Organon .
 A lgica

 formal analisa detalhadamente as diversas formas que podem adotar

 as operaes lgicas , em particular o raciocnio , com uma relativa

 independncia dos seus contedos concretos .

  13 .
 Leibniz j tinha compreendido no sculo XVII que h alguma

 semelhana entre a disjuno e conjuno de conceitos e a adio e

 multiplicao de nmeros mas foi difcil para ele formular

 precisamente em que consistia essa semelhana e como us-la depois

 como base para um clculo lgico .

  14 .
 A base do hardware sobre a qual so construdos todos os

 computadores digitais  formada de dispositivos eletrnicos

 diminutos denominados portas lgicas .
  um circuito digital no qual

 somente dois valores lgicos esto presentes .
 Para se descrever os

 circuitos que podem ser construdos pela combinao dessas portas

 lgicas  necessria a lgebra booleana ( para mais detalhes ver ) .

  15 .
 Jevons foi o primeiro a compreender que os mtodos booleanos

 podem ser reduzidos s regras do clculo elementar , com a

 possibilidade , portanto , de ser mecanizados .
 Em 1869 conseguiu

 construir uma mquina lgica apresentada no ano seguinte ao

 pblico : era um dispositivo de 21 chaves para testar a validade de

 inferncias na lgica equacional .
 Algumas das caractersticas deste

 dispositivo foram usadas mais tarde na implementao do computador .

 A mquina est conservada no museu de Histria da Cincia em

 Oxford .

  16.O emprego de quantificadores para ligar variveis , principal

 caracterstica do simbolismo lgico moderno e que o torna superior

 em alguns aspectos  linguagem vulgar e ao simbolismo algbrico de

 Boole , est entre as maiores invenes intelectuais do sculo XIX .

  17 .
 Como j se disse , idia lanada por Leibniz de uma linguagem

 filosfica que seria um simbolismo atravs do qual o homem estaria

 em condies de expressar seus pensamentos com plena clareza e

 dirimir dvidas atravs de simples clculos .

  18 .
 Sobre nmero , deduo , inferncia , proposies , premissas ,

 etc .

  19 .
 Quando a prpria Lgica Formal reflete sobre seus contedos .

  20 .
 O paradoxo de Russel , o paradoxo de Cantor , o paradoxo de

 Burati Forti , o paradoxo de Richard , etc .
 Para exemplificar , vamos

 ao de Cantor , descoberto por ele prprio em 1899 : se S  o conjunto

 de todos os conjuntos , ento seus subconjuntos devem estar tambm

 entre os seus elementos .
 Consequentemente , o nmero cardinal de S

 no pode ser menor do que o de conjunto dos subconjuntos de S .
 Mas

 isto , pelo teorema do prprio Cantor , deveria ocorrer !

  21.A tese logiscista compe-se de duas partes : 1 ) Toda idia

 matemtica pode ser definida por intermdio de conectivos lgicos

 ( classe ou conjunto , implicao , etc. ) ; 2 ) Todo enunciado

 matematicamente verdadeiro pode ser demonstrado a partir de

 princpos lgicos ( " no contradio " , " terceiro excludo " , etc. ) ,

 mediante raciocnios puramente matemticos .

  22 .
 Para Brower , fundador desta escola - na verdade um

 radicalizador das teses de Kronecker que no aceitava a teoria dos

 conjuntos - o saber matemtico escapa a toda e qualquer

 caracterizao simblica e se forma em etapas sucessivas que no

 podem ser conhecidas de antemo : a atividade do intelecto cria e d

 forma a entes matemticos , aproximando-se do apriorismo temporal de

 Kant .

  23 .
 Basta ler as palavras do matemtico Sylvester em sua

 controvrsia com Huxley .
 Dizia que a matemtica se origina

 " diretamente das foras e atividades inerentes da mente humana , e

 da introspeco continuamente renovada daquele mundo interior do

 pensamento em que os fenmenos so to variados e exigem ateno

 to grande quanto os do mundo fsico exterior. " Para ele a

 matemtica era revelar as leis da inteligncia humana , assim como a

 fsica revela as leis do mundo dos sentidos .

  24 .
 Os logicistas tiveram de apelar a princpios extra-lgicos -

 axioma de Zermelo , axioma do infinito - que ainda hoje encontram-se

 sujeitos a calorosos debates e fortes reparos .

  25 .
 Caminho praticado por Hilbert no seu famoso trabalho

 Fundamentos da Geometria ( 1899 ) , onde axiomatizou de modo rigoroso

 a geometria euclidiana .

  26 .
 No incio do sculo XX a matemtica estava reduzida a 3

 grandes sistemas axiomticos : aritmtica , anlise e conjunto , sendo

 o mais fundamental o primeiro .
 Era natural que ele escolhesse esse

 sistema .

  27 .
 John von Neumann falava 5 lnguas e foi um brilhante fsico ,

 logicista e matemtico .
 Alm de lhe ser atribuda a inveno do

 primeiro computador , ele estava no centro do grupo que criou o

 conceito de " programa armazenado " , que potencializou extremamente o

 poder computacional das mquinas que ento surgiam .

  28 .
 A simplicidade do problema de Hilbert  apenas aparente , e

 somente aps 70 anos de esforos foi encontrada a soluo , por

 Matijasevic , um matemtico russo de apenas 22 anos na poca .
  uma

 soluo bastante complexa , dependendo tanto de resultados da Teoria

 do Nmeros , conhecidos h muitssimos anos , como do trabalho

 anterior de trs americanos , Martin Davis , Julia Robinson e Hilary

 Putnan , que por sua vez baseia-se em certos resultados fundamentais

 sobre lgica e algoritmos descobertos na dcada de 30 por Kurt

 Gdel , Alan Turing , Emil Post , Alonso Church e Stephen Kleene .
 A

 resposta a esse problema de Hilbert  : tal algoritmo no existe : o

 dcimo problema  indecidvel .

  29 .
 O termo finitstico  usado por vrios autores .
 Hilbert quis

 dizer que tal sistema deveria ser construdo com um nmero finito

 de axiomas e regras e todas prova dentro do sistema deveria ter um

 nmero finito de passos .

  30 .
 As concluses de Gdel no significam que seja impossvel

 construir uma prova absoluta e finitista da aritmtica .
 Significam

 que nenhuma prova deste tipo pode ser construda dentro da

 aritmtica. , isto  , que esteja refletida a partir de dedues

 formais da aritmtica .
 Outras provas metamatemticas da

 consistncia da aritmtica foram construdas , em particular por

 Gerhard Gentzen , da escola de Hilbert , em 1936 , embora no

 finitistas e no representveia dentro do cculo aritmtico , ou

 seja , esto fora das condies previstas por Hilbert .

  31 .
 Os resultados de Gdel tem consequncias importantes tambm

 para a filosofia .
 Sabe-se , graas a ele , ser impossvel construir

 uma mquina que , de modo consistente , resolva todos os problemas da

 matemtica , com os recursos de um sistema ( certos problemas , por

 assim dizer , " no se deixam resolver " com os recursos do sistema

 apenas ) .
 Mas de fato o matemtico os resolve muitas vezes .
 A

 concluso a que se chega  que a mente humana  superior a uma

 mquina .

  32.Palavras como procedimento efetivo e algoritmo representam

 conceitos bsicos dentro da Cincia da Computao .
 So noes que

 na poca de Turing j eram utilizadas pelos matemticos , como por

 exemplo Frege e Hilbert ( ver captulos que tratam dessas duas

 importantes figuras ) .

  33 .
 Um ano mais tarde , trabalhando independentemente , Alan Post

 publicou seu trabalho sobre uma mquina semelhante  de Turing .

  34 .
 Uma Mquina de Turing Universal  uma Mquina de Turing

 especfica que l na sua fita de alimentao , alm de dados de

 entrada , um programa R que  uma especificao de uma Mquina de

 Turing qualquer .

  35 .
 Os computadores possuem conjuntos de instrues que

 correspondem a regras fixas de um sistema formal .
 Como provou

 Gdel , existem problemas no solucionveis dentro de um mtodo

 axiomtico e , portanto , h problemas que um computador no resolve .

 Esta afirmao no deve ser vista como algo pessimista dentro da

 Cincia da Computao : que um computador no possa resolver todos

 os problemas no significa que no se possa construir uma mquina

 ou algoritmo especfico para solucionar determinado tipo de

 problema .

 [ topo ]

 Bibliografia

 ___________________________________________________________

 Principal

 | Calorias | Cinena | Histria da Lgica | Loteria | Memria | Novidades do

 cinema |

 | Origem do Natal | Tunico e Xaropinho

