Um Caso de Estudo da Lógica Matemática à Máquina Universal de Turing
Elza Figueiredo Chagas *
Resumo
Embora não nos apercebamos, o mundo em que vivemos hoje depende fundamentalmente da Matemática. A computação que revoluciona a vida moderna não poderia fugir a regra: foi desenvolvida inicialmente (em seus aspectos teóricos) por matemáticos como Von Neuman e Alan Turing. Nesse sentido, o trabalho aqui apresentado tem como principal finalidade mostrar a importância de conceitos matemáticos na criação de modelos de máquinas automática, em especial, a criação dos computadores, tendo como base o modelo da Máquina de Turing. Em especial, nos interessa abordar a questão do pensamento dedutivo e matemático, seus limites e o problema da relativa mecanização do pensamento quantitativo.
Palavras-chave: Lógica Matemática, Pensamento Dedutivo, Máquina de Turing.
1. Introdução
Os primeiros estudos que se tem noticia sobre a origem das teorias que, futuramente, sustentariam a criação dos computadores digitais foram dados no Egito e Babilônia, há mais de quatro milênios, com os sistemas de medidas de distâncias e previsão do curso das estrelas.
Os gregos também tiveram importante participação nesse processo, pois foi através deles que surgiram os primeiros sistemas axiomáticos que se tem notícia. Surgem aqui as primeiras teorias de lógica (HUSKEY, 1984).
Em um sistema axiomático parte-se de premissas aceitas como verdadeiras e regras ditas válidas, que irão conduzir a novas sentenças verdadeiras. As conclusões podem ser alcançadas manipulando-se símbolos de acordo com conjuntos de regras. A geometria de Euclides é um clássico exemplo de um procedimento tornado possível por um sistema axiomático formal.
Na realidade, esse sistema é uma ferramenta utilizada para aumentar a capacidade humana de pensar. Exceto por algumas cabeças privilegiadas, a maioria das pessoas não são capazes de somar dois números de seis dígitos mentalmente. Entretanto, utilizando um pedaço de papel e um lápis, qualquer um pode efetuar cálculos matemáticos como apresentado acima em pouco menos de um minuto.
Diante de tal situação, já nas primeiras décadas do século XX, matemáticos e lógicos tentaram formalizar a matemática. Em 1920, David Hilbert e John von Neumann estabelecerem as regras de formalismo. Um pouco antes, Alfered North Whitehead e Bertrand Russel demonstraram em seu livro Principia Mathematica que alguns aspectos do raciocínio humano poderiam ser descritos formalmente.
A partir desses estudos, a idéia de um sistema formal era de especial interesse, porque traçava uma ponte entre abstração matemática e a maneira misteriosa do nosso cérebro discorrer.
Em verdade, um sistema formal deve ser aqui entendido como um "jogo" rigorosamente definido, onde regras para manipulação de símbolos são definidas. Sendo assim, três aspectos desse "jogo" devem ser estabelecidos: a natureza dos símbolos, a descrição da situação inicial do ambiente e uma lista de quais movimentos são permitidos a uma dada posição.
Por volta da década de 1930, os esforços para reduzir a matemática a fundamentos lógicos seguros levaram a várias tentativas de se tratar noções de aritmética - o braço da matemática que lida com operações sobre números - como um sistema formal (LEWIS, 1980).
Baseado nesses conceitos, Alan M. Turing introduzida em 1936, uma máquina que reduzisse os sistemas formais a um sistema básico subjacente neles. Essa máquina é conhecida como Máquina Universal de Turing: uma abstração usada no estudo da Teoria da Computação.
Foi exatamente graças aos esforços de Turing que se tornou possível à criação de computadores digitais como os que conhecemos atualmente.
Um século após a invenção de tal máquina, a computação não foi apresentada em uma feira de informática ou em um laboratório de algum cientista famoso. A possibilidade de se construir um computador digital foi dada ao mundo através de um inusitado artigo, em um jornal de matemática no ano de 1936. No momento, quase ninguém percebera que a descoberta descrita naquele obscuro artigo iria conduzir a uma arrancada mundial no campo tecnológico, embora seu jovem autor, Alan Mathison Turing, já estivesse na busca de uma máquina que simulasse os processos humanos de conhecimento (BRITTON, 1992).
2. A Lógica Matemática e a Automatização do Raciocínio
O início da Lógica encontra-se na antiga Grécia, mas é com os trabalhos desenvolvidos por Aristóteles (384 a.C. - 322 a.C.) que esta ciência tornou-se a ciência das idéias e dos processos da mente.
Aristóteles chamou a Lógica como Analítica, que do grego significa resolução. Esse termo era assim referenciado porque segundo Aristóteles, a Analítica explicava o método pelo qual, partindo de uma dada conclusão, resolve-se precisamente nos elementos dos quais deriva.
Embora Aristóteles seja considerado o mais brilhante e influente filósofo grego, outra importante tradição argumentativa formou-se na antiga Grécia, com os pensadores megáricos e os pensadores estóicos.
Os pensadores megáricos interessaram-se por certos enigmas lógicos como o conhecido paradoxo do mentiroso que diz: "O que eu afirmo agora é falso?" Um importante legado deixado pelos megáricos foi o estudo de proposições do tipo "se chover então a rua está molhada?"
Os pensadores estóicos, por sua vez, desenvolveram código de comunicação bastante específico. Porém, a mais notável contribuição estóica foi dada por Crísipio de Soles, homem de vasta produção poligráfica que estudou sentenças condicionais, disjuntivas e copulativas, tendo também reconhecido claramente o papel lógico desempenhado pela negação.
Tendo como base noções de Lógica, em 4.200 a.C. iniciou-se a concretização de uma antiga idéia de se reduzir todo raciocínio a um processo mecânico, baseado em algum tipo de cálculo formal.
Nesse sentido, encontramos a figura de Raimundo Lúlio (1235-1316) que, através do seu trabalho Ars Magma, apresentou a primeira tentativa de um procedimento mecânico para produzir sentenças logicamente corretas que se tem notícia. Segundo Lúlio, através de um sistema de anéis circulares dispostos concentricamente, de diferentes tamanhos e graduáveis entre si, todo o saber humano podia ser sistematizado em uma gramática lógica.
Os procedimentos estabelecidos por Lúlio não foram muito válidos, entretanto o seu trabalho influenciou muitos matemáticos famosos, do nível de Cardano, Descartes, Leibniz, Cantor, entre outros.
Citando agora mais especificamente o trabalho do matemático alemão Gootfried Leibniz, percebemos que este matemático queria dotar a Metafísica de um instrumento suficientemente poderoso que permitisse alcançar o mesmo grau de rigor que tinha alcançado a Matemática.
Assim, Leibniz concebeu uma desvinculação com relação ao conteúdo semântico das proposições, a qual além de auxiliar o processo de inferência de manter presente o significado e as condições de verdade da argumentação, pusesse a dedução a salvo da fácil influência que sobre ela pode exercer o aspecto material das proposições.
Por tudo isso, Leibniz influenciou seus contemporâneos e sucessores através de seu ambicioso programa para a Lógica, através da criação de uma linguagem universal baseada em um alfabeto do pensamento.
A partir de meados do século XIX, a lógica formal se elabora como um cálculo algébrico, adotando um simbolismo peculiar para as diversas operações lógicas. Isso permitiu a construção de grandes sistemas axiomáticos de lógica de maneira parecida com a matemática, com os quais se podem efetuar com rapidez e simplicidade raciocínios que a mente humana não consegue realizar espontaneamente.
A Lógica Simbólica - Lógica Matemática - passa a ter aqui fundamental importância no estudo de formas de inferência. Definida inicialmente por Boole (1815-1864), a Lógica Simbólica passou a ser definida não mais em termos de números, mas também se utilizando símbolos algébricos.
Boole criou o primeiro sistema bem sucedido para o raciocínio lógico, tendo sido pioneiro em enfatizar a possibilidade de se aplicar o cálculo formal em diferentes situações, utilizando para isso regras formais.
Sendo assim, através da utilização de símbolos e operações específicas, as proposições lógicas poderiam ser reduzidas a equações e, estas, poderiam ser computadas de acordo com as regras da álgebra ordinária.
As idéias defendidas por Boole foram essenciais para o desenvolvimento da Computação, pois segundo ele, o sistema matemático poderia ser representado em duas quantidades: o universo (representado por 1) e o nada (representado por 0), o que levou a um sistema de dois estados para a quantificação lógica. Mais tarde os construtores do primeiro computador entenderam que um sistema com somente dois valores pode compor mecanismos para refazer cálculo.
No entanto, a lógica booleana estava limitada ao raciocínio proposicional; somente após o desenvolvimento de quantificadores, introduzidos por Pierce, é que a lógica formal pôde ser aplicada ao raciocínio matemático geral. O resultado mais importante, no entanto, foi à apresentação do cálculo de uma forma extremamente axiomatizada.
A partir do ano de 1848, o conceito de lógica tomou novos rumos; os objetos da investigação lógica já não são mais as fórmulas, mas regras de operações pelas quais essas fórmulas se deduzem.
Essa mudança de conceito foi influenciada pelos trabalhos desenvolvidos por Frege e Peano, matemáticos que trabalharam para fornecer bases mais sólidas à álgebra e, assim, generalizar o raciocínio matemático.
Mas, por volta de 1900, surgiram algumas dúvidas que abalaram a confiança dos matemáticos, especialmente na teoria dos conjuntos. Estava assim iminente uma inevitável colisão entre matemática e filosofia.
Citando (ASPRAY, 1980), "... o problema de estabelecer fundamentos era o grande desafio de muitos matemáticos que pretendiam reduzir as leis científicas a equações matemática." Nota-se aqui a necessidade de uma matemática definida dentro de bases rigorosamente sólidas, com axiomas de procedimento que deveriam ser estabelecidos em caráter definitivo.
Os problemas propostos inicialmente por Hilbert em 1928, durante o Congresso Internacional de Matemática, realizado em Bolonha, Itália, comprovam que este matemático procurava algo como uma máquina de gerar enunciados matemáticos verdadeiros.
Ao mesmo tempo, em 1927, Von Newmann publica um trabalho que relaciona conceitos de sistemas formais lógicos e limites da máquina, conceitos considerados fundamentais para a futura criação de computadores. Dentro desses conceitos definidos por Newmann, a Lógica aparece com o objetivo de elaborar uma linguagem lógica de grande precisão.
Todos esses conceitos foram essenciais para a criação do que conhecemos hoje como computação, gerando um novo capítulo na história.
3. A Máquina de Turing
O ano de 1935 ficou conhecido como o ano da revolução de computador. Aos 24 anos de idade, o inglês Alan M. Turing consagrou-se como um dos maiores matemáticos do seu tempo quando fez antever aos seus colegas que era possível executar operações computacionais sobre a teoria dos números por meio de uma máquina que tivesse embutidas as regras de um sistema formal.
Considerado por muitos como pai da inteligência artificial, Alan Turing construiu uma conceituação matemática da noção de algoritmo, segundo os passos que um ser humano dá quando executa um determinado cálculo ou cômputo.
Para Turing, os cálculos mentais nada mais são do que operações que transformam números em uma série de estados intermediários, que progridem de um para outro de acordo com um conjunto fixo de regras, até que uma resposta seja encontrada. Como as regras matemáticas exigiam definições rígidas, Turing definiu cuidadosamente os estados de maneira que fossem claros e sem ambigüidades.
Seu trabalho então, começou com uma descrição precisa de um sistema formal, na forma de "tabela de instruções" que descreviam quais movimentos a fazer para qualquer configuração possível dos estados no sistema. Ele então provou que a descrição dessas informações, que os passos de um sistema axiomático formal semelhante à lógica, e o estados da máquina que fazem os "movimentos" em um sistema formal automático são equivalentes entre si. Estes conceitos estão todos subjacentes na tecnologia atual dos computadores digitais, que foram possíveis somente uma década depois da publicação de Turing (HERKEN, 1988).
Figura 1 - Esquema da Máquina Universal de Turing.
Embora propriamente não existisse tal máquina, Turing enfatizou desde o início que tais mecanismos poderiam ser construídos. Sua descoberta abriu uma nova perspectiva no esforço de formalizar a matemática, e, ao mesmo tempo, marcou fortemente a história da computação, pois a máquina teórica de Turing era tanto um exemplo da sua teoria da computação como uma prova de que certos tipos de máquinas computacionais poderiam, de fato, serem construídas (HODGES, 1983).
Para que essa máquina fosse perfeitamente definida, seria necessário unir conceitos de matemática com conceitos de lógica, de forma a propor sistemas que, de alguma maneira, processassem símbolos.
Assim, a Máquina Universal de Turing, como é mais conhecida, pode ser definida como um dispositivo capaz de manipular automaticamente os símbolos de um sistema formal de acordo com as suas regras.
O processo computacional foi graficamente mostrado no artigo de Turing quando ele pediu ao leitor que considerasse em dispositivo que pudesse ler e escrever símbolos em uma fita que estava dividida em quadrados. Uma cabeça de leitura/gravação se moveria em qualquer direção ao longo da fita, um quadrado por vez, e uma unidade de controle poderia interpretar uma lista de instruções simples sobre leitura e gravação de símbolos nos quadrados, movendo-se ou não para a direita ou esquerda. O quadrado que é "lido" em cada etapa é conhecido como "quadrado ativo". A regra que está sendo executada determina o que se convencionou chamar 'estado' da máquina. A fita é potencialmente infinita (HERKEN, 1988).
Dado um quadrado que seja uma posição inicial de uma seção da fita preenchida por quaisquer caracteres ou brancos, o dispositivo executa ações especificadas por uma lista de regras, seguindo-as uma por vez até chegar àquela que force sua parada (se não há uma instrução explícita na tabela para uma determinada configuração da fita, então não há nada que a máquina possa fazer quando alcança aquela configuração, encerrando a execução (BARWISE, 1993).
Cada instrução - ou regra - estabelece uma ação a ser executada se houver determinado símbolo no quadrado ativo no tempo em que é lido. No nosso caso vamos estabelecer quatro diferentes tipos de regra:
* Substituir branco por símbolo
* Substituir símbolo por branco
* Ir um quadrado para a direita
* Ir um quadrado para a esquerda
Cada regra dessa lista será composta pela seguinte seqüência: o número da regra - estado da máquina -, um caracter/branco para comparação, próximo estado e ação.
Em sua essência, toda máquina de Turing move-se ou move símbolos, de uma posição para outra em uma fita, da mesma maneira que no exemplo dado acima ou visto no applet. Nos dias de hoje estes símbolos podem ser impulsos eletrônicos em um microcircuito e a fita uma série de endereços de memória em um chip, mas a idéia é a mesma. Turing provou que sua hipotética máquina é uma versão automatizada de um sistema formal especificado por uma combinação inicial de símbolos e as regras. Os movimentos são mudanças de 'estado' da máquina que correspondem a específicos passos de computação.
Turing provou que para qualquer sistema formal existe uma máquina de Turing que pode ser programada para imitá-lo (HILTON, 1991). Era este sistema formal genérico, com a habilidade de imitar qualquer outro sistema formal, o que Turing procurava. A teoria foi estabelecida pela primeira vez em um "paper" que tinha o título "On Computable Numbers, with an application on the Entscheidungsproblem".
4. CONCLUSÕES E TRABALHOS FUTUROS
Conforme apresentado nesse trabalho, o computador é o resultado da conjunção de dois campos distintos de atividades humanas: a matemática e a tecnologia. Dentro da matemática, a Lógica foi à área que mais impulsionou a criação dos computadores digitais. Já quanto à tecnologia, a história dos computadores iniciou-se com os primeiros mecanismos artificiais construídos para marcar o tempo ou para simular o comportamento de animais ou pessoas, os chamados autômatos. Ao longo do tempo, foram desenvolvidos relógios, máquinas de calcular e, finalmente, computadores.
Podemos dividir a Lógica em antes e depois de Boole. Nesse sentido, as idéias de pospostas por este matemático não só demonstraram a equivalência entre a Matemática e a Lógica como também representaram a sistematização do pensamento humano. Podemos ainda afirmar que a ciência, a partir de Boole, viu que razão humana é mais complicada e ambígua, difícil de ser conceituada e mais poderosa que a lógica formal.
Percebe-se que o desenvolvimento dos computadores foi iniciado nos Estados Unidos pelos matemáticos e lógicos, que continuam a dar importantes contribuições à teoria da ciência da computação. A próxima geração de softwares requer os métodos matemáticos mais recentes daquela que é chamada teoria das categorias, uma teoria de estruturas matemáticas que tem trazido novas perspectivas aos fundamentos da matemática e da lógica. De fato, fica claro através desse trabalho à contribuição dada por dois matemáticos, von Neumann e Turing a construção de computadores.
É inquestionável, portanto, que a análise da computação, e as tentativas de torná-la tão confiável quanto possível, precisa de Matemática profunda, e essa necessidade está aumentando. Um computador, a menos que seja programado, é nada mais do que uma caixa de metal, vidro, silício, etc. A Matemática é necessária como uma linguagem para a especificação, para a determinação do que é que deve ser feito, como e quando, e para a verificação de que os programas e os algoritmos funcionam corretamente. Fica claro, portanto, que a Matemática é essencial para o uso correto dos computadores na maioria das aplicações.
5. REFERÊNCIAS BIBLIOGRÁFICAS
(ASPRAY, 1980) ASPRAY, William F. From Mathematical Constructivity to Computer Science: Alan Turing, John von Neumann, and the Origins of Computer Science in Mathematical Logic. Unpublished Ph. D. Dissertation, Univ. of Wisconsin, Madison WI, 1980.
(BARWISE, 1993) BARWISE, Jon & John Etchemindy. Turing's World 3.0. Cambridge: Cambridge University Press, 1993.
(BRITTON, 1992) BRITTON, J.L. Pure mathematics; with a section on Turing's statistical work by I.J. Good, North-Holland, Amsterdam: Author, 1992.
(HERKEN, 1988) HERKEN, Rolf. The Universal Turing machine: a half-century survey. Oxford: Oxford University Press, 1988.
(HILTON, 1991) HILTON, Peter. Working with Alan Turing. In Mathematical Intelligencer. 1991, vol. 13, no. 4, pp. 22-25.
(HODGES, 1983) HODGES, Andrew. Alan Turing: The Enigma. New York: Simon and Shuster, 1983.
(HUSKEY, 1984) HUSKEY, Harry. ACE to G-15. In Ann. Hist. Comp. 1984, vol. 6, no. 4, pp. 350-371.
(LEWIS, 1980) LEWIS, Harry & PAPADIMITRIOU, Cristhos. Elements of Theory of Computation. New Jersey: Prentice Hall, 1980.
* Faculdades Integradas de Palmas - PR - Departamento de Informática.
Nenhum comentário:
Postar um comentário