HISTÓRICO AUTÔMATO CELULAR E MÁQUINA DE TURING

MÁQUINAS DE TURING

• 1. MÁQUINAS DE TURING

  A Máquina de Turing consiste numa estrutura simples, sendo o modelo utilizado para dizer tudo o que é ou não computável. É a base conceitual dos computadores até os dias de hoje.
  A Máquina de Turing consiste em 3 partes; uma fita infinita, uma unidade de controle e uma função de transição de leitura/gravação, conforme figura 1.
  A fita é usada como um dispositivo de entrada, saída e memória. Ela é dividida em células que armazenam um símbolo de cada vez. A unidade de controle reflete o estado de controle da máquina. Possui uma unidade de leitura e gravação que pode deslocar-se para a esquerda (L) ou para direita (R), da fita, podendo ler e/ou gravar um único símbolo em cada movimento. A função de transição comanda as leituras e gravações, o sentido de movimento da cabeça e define o estado da máquina.  (PRADO, 2009).

Figura 1 – Um modelo de Máquina de Turing

Fonte: PRADO (2009, p. 3).

• 2. UM POUCO DA HISTÓRIA DO CIENTISTA QUE CRIOU A MÁQUINA DE TURING

  Alan Mathison Turing nasceu em 23 de junho de 1912 em Londres, filho de um oficial britânico, Julius Mathison e Ethel Sara Turing. Seu interesse pela ciência começou cedo, logo que aprendeu a ler e escrever, distraia-se fatorando números de hinos religiosos e desenhando bicicletas anfíbias.
  Em 1928, Alan começou a estudar a Teoria da Relatividade, conhecendo Christopher Morcom. Em 1936, com a idade de 24 anos, 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.
  Alan Turing descreveu em termos matematicamente precisos como um sistema formal automático, com regras muito simples de operação, pode ser poderoso. Um sistema formal automático é um dispositivo físico que manipula automaticamente os símbolos de um sistema formal de acordo com as regras dele. 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. 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.
  Quando a II Guerra Mundial eclodiu, Turing foi trabalhar no Departamento de Comunicações da Gran Bretanha (Government Code and Cypher School) em Buckinghamshire, com o intuito de quebrar o código das comunicações alemãs, produzido por um tipo de computador chamado Enigma. Este código era constantemente trocado, obrigando os inimigos a tentar decodifica-lo correndo contra o relógio. Turing e seus colegas cientistas trabalharam num sistema que foi chamado de Colossus, um enorme emaranhado de servo-motores e metal, considerado um precursor dos computadores digitais.
  Durante a guerra, Turing foi enviado aos EUA a fim de estabelecer códigos seguros para comunicações transatlânticas entre os aliados. Supõe-se que foi em Princeton, NJ, que conheceu Von Neumann e daí ter participado no projeto do ENIAC na universidade da Pensilvânia. Terminada a guerra, Alan se juntou ao National Physical Laboratory para desenvolver um computador totalmente inglês que seria chamado de ACE (automatic computing engine). Decepcionado com a demora da construção, Turing mudou-se para Manchester e no dia 7 de junho de 1954, suicidou-se durante uma crise de depressão, comendo uma maçã envenenada com cianureto de potássio. (POZZA; PENEDO, 2002)

Figura 2 – Linha do tempo sobre Alan Turing

Fonte: Autoria Própria, 2019.

3. TESE DE TURING

“Qualquer computação que pode ser executada por meios mecânicos pode se executada por uma Máquina de Turing.” (PRADO, 2009, p. 16).

4. MODELOS DE MÁQUINAS DE TURING:

1)    Máquina de Turing com opção de parada – essa Máquina de Turing acrescenta, na sua função de transição, a possibilidade de não mover a cabeça da fita a cada movimento.

2)    Máquina de Turing com fita semi-infinita – uma Máquina de Turing pode ter uma fita infinita à esquerda e/ou à direita. Se a fita é ilimitada à esquerda e à direita então temos uma Máquina de Turing padrão. Caso haja um limite na fita à direita ou à esquerda ela é chamada de Máquina de Turing com fita semi-infinita. Dessa forma, em uma direção da fita os movimentos são restritos. Não se pode mover para fora da fita.

3)    Máquina de Turing com múltiplas fitas - essa Máquina de Turing possui mais que uma fita e para cada uma dessas fitas existe uma cabeça de leitura/escrita.

4)    Máquina de Turing com múltiplas cabeças - essa Máquina de Turing possui uma única fita e k (k>1) cabeças de leitura/gravação sobre a mesma fita. O processamento dependerá do estado corrente e do símbolo lido em cada uma das cabeças.

5)    Máquina de Turing com múltiplas trilhas - essa Máquina de Turing possui uma única fita e uma cabeça de leitura/gravação, só que possui múltiplas trilhas na fita. Isso implica em ter mais de um símbolo em cada posição de leitura/escrita da cabeça da fita.

6)    Máquina de Turing Multidimensional - nessa Máquina de Turing a fita é substituída por uma estrutura m-dimensional, infinita em todas as suas direções.

7)    Máquina de Turing Não Determinístico - essa Máquina de Turing é equivalente as Máquinas de Turing Determinísticas (uma sétupla).

8)    Máquina de Turing com fita limitada ou Autômato Limitado Linearmente – a Máquina de Turing tem uma fita ilimitada. Para fazer a restrição de limites nas duas direções, a fita irá possuir um número de células que conterá a entrada mais duas células. Essas duas células a mais armazenarão os símbolos especiais: ‘[‘ e ‘]’ que simbolizam o início e o final da entrada (PRADO, 2009).

5. APLICAÇÃO E IMPORTÂNCIA

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. 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 (POZZA; PENEDO, 2002). Logo, foi a tese de Alan Turing que originou os atuais computadores.

6. AUTÔMATOS CELULARES E MÁQUINA DE TURING

 

Autômatos celulares são suficientemente simples para permitir análises matemáticas detalhadas, mas suficientemente complexos para exibir uma grande variedade de fenômenos complicados. Autômatos celulares são idealizações matemáticas de sistemas físicos nos quais o espaço e o tempo é discreto, e as quantidades físicas assumem um conjunto finito de valores discretos. Um autômato celular consiste em uma rede uniforme regular (ou "matriz"), geralmente infinita em extensão, com uma variável discreta em cada site ("célula").

Os autômatos celulares são a principal maneira de implementar a abordagem de sistemas auto-organizáveis.

O conceito foi desenvolvido inicialmente pelos matemáticos Stan Ulam e John von Neumann na década de 1940 e foi aplicado por John Conway em 1960 no seu famoso “Jogo da Vida” (BERLEKAMP; CONWAY; GUY, 2004).

O autômato é completamente especificado pelos valores das variáveis ​​em cada site. Um autômato celular evolui em intervalos de tempo discretos, com o valor da variável em um site sendo afetado pelos valores das variáveis ​​nos sites em sua "vizinhança" na etapa de tempo anterior. A vizinhança de um site geralmente é considerada o próprio site e todos os sites imediatamente adjacentes. As variáveis ​​em cada site são atualizadas simultaneamente ("síncrona"), com base nos valores das variáveis ​​em sua vizinhança na etapa anterior e de acordo com um conjunto definido de "regras locais".

Os autômatos celulares têm sido amplamente utilizados no processamento de imagens e reconhecimento visual de padrões (Deutsch, 1972; Sternberg, 1980; Rosenfeld, 1979, apud Wolfram, 1983). A geração de padrões auto-similares foi, portanto, considerada uma característica genérica de autômatos celulares evoluindo de simples estados iniciais. Este resultado pode fornecer algumas explicações para a ocorrência generalizada de auto-similaridade em sistemas naturais.

Modelos baseados em autômatos celulares fornecem uma abordagem alternativa, envolvendo coordenadas e variáveis ​​discretas, bem como etapas de tempo discretas. Eles exibem comportamento complicado análogo ao encontrado com equações diferenciais ou iteradas mapeamentos, mas em virtude de sua construção mais simples são potencialmente passíveis de análise mais detalhada e completa.

 

6.1 CORRELAÇÃO ENTRE AUTÔMATOS CELULARES E MÁQUINA DE TURING

Segundo Dilão (1993, p. 8):

Um autómato celular é uma sequência de símbolos, distribuídos sobre os nós de uma rede a uma, duas ou mais dimensões, e que evoluem no tempo de acordo com uma regra ou programa”; diz ainda que “Os autômatos celulares são modelos matemáticos discretos, facilmente implementáveis em computador e com aplicações na simulação em tempo real de sistemas físicos, biológicos e sociais, com um grande número de componentes em interação. (DILÃO, 1993, p. 3).

Uma vez que Máquina de Turing é a base conceitual dos computadores, que consiste numa estrutura simples, sendo o modelo utilizado para dizer tudo o que é ou não computável.

E um computador é uma máquina capaz de calcular todos os processos ou funções que sejamos capazes de imaginar, afirmação esta que se baseia na existência de um modelo teórico para a computação, construído por A. Turing em 1936.

Assim, ao tratar de correlação entre Máquina de Turing e Autômatos celulares, cabe dizer que modelos de autômatos celulares têm uma descrição facilmente implementável num programa para uma máquina de Turing.

 

7. APLICABILIDADE NA EDUCAÇÃO E EM OUTRAS ÁREAS

Na educação, tanto para estudantes de computação, como tamém para os de áreas relacionadas, o desenvolvimento de máquinas de Turing é uma forma pedagógica para que possam ver um exemplo prático e relativamente complexo de formas de processamento.

Inclusive, ao falar do rigor teórico da Ciência da Informação, a máquina de Turing, é capaz de dar-lhe a devida utilidade e o reconhecimento social, tornando-a útil em todas as áreas do conhecimento.

Autômatos Celulares aplica-se na educação e em áreas como:

·         Arquitetura;
·         Meio ambiente (conservação);
·         Ciências biológicas;
·         Arquitetura;
·         Na natureza – estudo da turbulência química;
·     Medicina – precisão de diagnósticos, na documentação de experimentos, ferramentas matemáticas para representar o espelhamento de epidemias, controle da propagação epidêmica, modelar os impulsos em músculos cardíacos, controle da propagação de epidemias, estratégias de controle por meio da vacinação, estudar a evolução do Vírus da Imunodeficiência Adquirida (HIV) de infecção e o início da Síndrome Imunodeficiência Adquirida (AIDS) no organismo de um indivíduo.

 REFERÊNCIAS

DILÃO, Rui. Autómatos celulares, máquinas de Turing ou a natureza como máquina de cálculo. Colóquio Ciências, Lisboa, n. 12, p. 3-20, 1993.

MELOTTI, Gledson. Aplicação de autômatos celulares em sistemas complexos: um estudo de caso em espalhamento de epidemias. 2009. 93f. Dissertação (Mestrado em Engenharia Elétrica) – Pós-Graduação em Engenharia Elétric, Universidade Federal de Minas Gerais, Belo Horizonte, 2009.

MORAES, André Luiz Silva de Moraes. Um estudo sobre a aplicação de autômatos celulares na simulação de fenômenos ambientais e aspectos dinâmicos. 2007. 43f. Trabalho Individual. Programa de Pós-Graduação em Informática, Escola de Informática, Universidade Católica de Pelotas, Pelotas, 2007.

PRADO, Simone. Teoria da Computação e linguagens Formais. 2009. Disponível em:<http://wwwp.fc.unesp.br/~simonedp/zipados/TC06.pdf>Acesso em: 23 ago 2019.

POZZA, Osvaldo Antonio.; PENEDO, Sérgio. A Máquina de Turing. 2002. Disponível em:<http://www.inf.ufsc.br/~j.barreto/trabaluno/MaqT01.pdf>Acesso em 23 ago 2019.

WOLFRAM, S. Statistical mechanics of cellular automata. Reviews of Modern Physics, v. 55, n. 3, p. 601-644, 1983.