Teoria da Informação, Máquinas de Turing

 NOÇÕES SOBRE TEORIA DA INFORMAÇÃO


A finalidade deste capítulo é introduzir o leitor nas noções fundamentais da teoria da informação, como parte de leitura complementar do meu próximo livro "Teoria da Informação e o Código da Vida". São noções importantes para lidar com genes em qualquer instância, seja na dinâmica de genes em populações, seja na dinâmica de epidemias, seja na evolução da informação biológica, etc.

Como se trata de copyright, a transcrição de parte deste artigo deve ter a fonte citada: Portela Câmara F. Linguagens naturais, sequência de símbolos, informação, In: Genes, Populações e Epidemias, blog, popdinamica.blogspot.com.br. 

1. Linguagens naturais. Sequências de símbolos. Informação.

Fernando Portela Câmara, Prof. Associado UFRJ

O “segredo” da vida repousa nas sequências codificadas em tripla de bases nitrogenadas no DNA e RNA envolvidos no armazenamento, transferência e tradução da informação genética, em outras sequências de aminoácidos que formarão proteínas funcionais. Todos os processos biológicos, genéticos, fisiológicos, neurais, linguísticos são processados por informação codificada em sequências no input e no output. Este é o princípio fundamental da Teoria da Informação e da Teoria da Computação.

O processo da computação genética mostra que tais sequências, denominadas de genes, contém informação, pois são traduzidas em proteínas que executam a construção e manutenção da célula. Essas proteínas, por sua vez, resultam de sequências de aminoácidos que contem informação que leva o polipeptídio formado a se dobrar de tal forma que, pela forma e aproximação de certos grupos químicos, gera uma estrutura funcional ativa. Proteínas resultam da tradução de genes, portanto, o processador da informação genética assemelha-se a um compilador (computador que traduz uma linguagem em outra). Essas sequências, portanto, possuem as propriedades de uma linguagem, portanto formam mensagens, que são o objeto de comunicação da informação. Uma mensagem é comunicada de uma fonte a um receptor através de um canal. Uma linguagem é um código formado por símbolos (“letras” ou código-fonte) selecionados de um conjunto finito (“alfabeto”) e combinados em sequências (“palavras” ou códigos-bloco) segundo um conjunto de regras. Nossa linguagem ordinária é, de fato, um código para as nossas ideias e conceitos.

Nas linguagens naturais, certos símbolos ou letras ocorrem mais frequentemente que outras, e se examinarmos um grande número de textos veremos que essas probabilidades são estacionárias, isto é, tendem para um valor fixo. Por exemplo, na língua portuguesa, a letra “a” ocorre com uma frequência de 14,6%, enquanto a letra “d” é de 5%, etc. (veja tabela no Apêndice F); as probabilidades de ocorrência de certas letras ou grupos de letras são mais frequentes quando uma determinada letra ou grupo delas ocorre (probabilidade condicional), por exemplo, a letra “q” é seguida via de regra pela letra “u”; etc. Esse padrão é conhecido como homogeneidade estatística de uma linguagem.

A homogeneidade estatística gera redundância, sendo esta é a razão pela qual podemos reconstituir um texto danificado segundo o contexto e os códigos mais prováveis. P. ex., o telegrama “SEV NETO NACCEU NOITE PASSADA TUDOF B5EM” não deixa dúvida do que se trata. Igualmente, em um dado contexto, também certas palavras e expressões são mais pronunciadas que outras, o que nos permite acompanhar uma conversa em ambiente barulhento ou uma palestra com alguns cochilos. A redundância permite a recuperação de uma mensagem em um canal com ruídos (perturbações aleatórias externas que causam erros na transmissão da mensagem).

Uma mensagem, portanto, ocorre numa sequência (portanto são variáveis aleatórias), em que determinados símbolos ocorrem mais frequentemente quando um dado símbolo ou grupo de símbolos ocorrem. Esse tipo de “processo estocástico” é chamado de cadeia ou processo de Markov, e como essas probabilidades são estacionárias, elas caracterizam um processo ergódico, temos aqui especificamente cadeias de Markov do tipo ergódico. Suponha, por exemplo, a sequência abaixo:

CCACBCBACACBABCACBCACCCB…

E que a análise de uma amostra de sequências oriundas da mesma fonte tenha revelado padrões repetitivamente semelhantes. A análise revela que as frequências de A, B e C são, respectivamente, 1/4, 1/4 e 1/2 (recorde-se que a soma das probabilidades sempre deve ser 1), e que tais probabilidades se repetem nas outras sequências de mesma origem, e a ocorrência dos símbolos é independente uns dos outros, sugerindo que a sequência é aleatória, isto é, um símbolo não ocorre em preferencia a outro.

Nas linguagens naturais, incluindo a genômica e proteômica, essas probabilidades observadas nas sequências não são totalmente independentes, ou seja, a ocorrência de um determinado evento é mais provável após um dado evento ocorrer e menos quando outro ocorre, exibindo esse padrão repetitivamente. Por exemplo, a sequência:

ACCCBACCBBAABBACBACCCCCBAACBAACCCC…

…mostra que uma letra tem maior chance de ocorrer quando uma dada letra ocorreu. Isso permite construir uma tabela de probabilidades denominada de matriz de transição:

	A	B	C
A→	1/4	1/4	1/2
B→	3/4	1/4	0
C→	0	1/3	2/3

Percebe-se que A sucede B em 75% das vezes, mas nunca sucede a C; e C sucede a si mesmo em 33% dos casos, mas nunca sucede a B; e as demais se sucedem com diferentes probabilidades. Com tabelas semelhantes podemos caracterizar qualquer linguagem natural (incluindo aqui a genética) com diferentes etapas de transições. Da mesma forma, podemos construir uma tabela para regras gramaticais e com ela gerar frases. Isso nos mostra que muitas teorias do comportamento, da aprendizagem, formação de linguagens, etc., onde estão implicados sequências de eventos ou ações, e não apenas símbolos ou letras, possuem a propriedade das cadeias de Markov ergódicas. Assim, linguagens naturais podem modeladas como geradores markovianos.

Temos, portanto, que a propriedade de homogeneidade estatística das linguagens (e outros processos sequenciais como o comportamento) torna modeláveis os processos codificáveis em sequências de símbolos (ou variáveis aleatórias).

Sequências markovianas do tipo ergódico podem ser quantificadas de modo menos complicado usando uma simplificação da teoria das probabilidades que é a Teoria da Informação, criada por Claude Shannon (Shannon, 1948; Shannon e Weaver, 1949). Sequências complexas podem ser reduzidas a medidas simples e altamente precisas, que nos permitem comparar sequências, capacidade de armazenagem de informação, propriedades dos códigos usados para armazenar e transferir informações, etc.

O significado da informação na teoria de Shannon 

A informação de Shannon não diz respeito a semântica ou significado, mas a fidelidade da transmissão de sequencias de símbolos ou mensagens codificadas. Os sistemas de comunicação não são cognitivos, mas emissores e receptores de sequências que são processos envolvidos na comunicação de mensagens de um ponto a outro. Assim, a célula processa indistintamente uma informação armazenada em uma sequência de DNA quer seja dela mesma, ou de uma célula diferente ou de um vírus invasor. É o sistema de comunicação que determina se uma mensagem será corretamente transmitida e lida, e para isso ela deve ser codificada apropriadamente. 

Teorema Central da Teoria da Informação. Capacidade de canal com ruído.

Enquanto a medida de informação, confusamente denominada de "entropia de Shannon", é confundida frequentemente com a entropia de Boltzmann, o principal teorema da Teoria da Informação não se confunde entre as leis da física e está intimamente relacionado à biologia molecular, no que se refere ao código genético. O teorema da capacidade de canal sem ruído estabelece que não é possível transmitir mais informação que a suportável pelo canal, do contrário haverá perda. O teorema da capacidade de canal com ruído estabelece que é possível evitar significativamente a incidência de ruídos na transmissão da informação usando-se códigos digitais construídos de tal forma a detectar e filtrar os erros. Esses códigos podem ser aperfeiçoados a ponto de quase poder igualar a capacidade do canal. Embora o teorema não diga como esses códigos são construidos (para isso foi desenvolvida a Teoria da Codificação), ele foi fundamental para o compreensão que levou à elucidação do código genético e proporicona importantes insights sobre a Evolução e a Origem da Vida, assunto que, juntamente com a teoria da computação, é assunto central no meu livro "A Teoria da Informação e o Código da Vida".


2. Resumo matemático da Teoria da Informação
 

Considere uma mensagem como uma sequência de símbolos emitidos cada um com uma probabilidade especifica. A posição de cada símbolo na sequência é importante para que a informação tenha a destinação para a qual foi criada. Ao considerar que um e somente um símbolo pode ocupar uma posição na mensagem, assim como somente um códon pode ocupar uma dada posição na sequência de um gene, estamos fazendo o que em física é conhecido como estatística de Fermi-Dirac, que se aplica a partículas tais como o elétron que tem 1/2 spin (a estatística que permite múltipla ocupação, como, p. ex., fótons e partículas alfa que têm spins integrais, é a de Bose-Einstein, que não é a seguida pela teoria da informação).

H é assim uma função dos componentes do vetor probabilidade p no espaço de probabilidades Ω. Temos três condições a observar:

     - Se todas as probabilidades forem iguais, H será máximo; e se todas as probabilidades forem zero, exceto uma (p = 1) então H será zero;

      - Pequenas mudanças nos componentes de p devem resultar em pequenas mudanças em H;    

      - Se os eventos são conjuntos (evento x, y) a medida da incerteza é a soma ponderal dos valores esperados dos eventos.

A função que satisfaz essas condições é a entropia de Shannon:

H = -∑ p_i log₂ p_i 

Uma forma de se obter essa equação foi apresentada por Brillouin (1962) a partir do seguinte argumento: Seja N o número total de posições numa molécula de DNA (ou RNA ou proteína), N_i o número de códons do tipo i, e que um e somente um códon ocupa uma dada posição na molécula. O número de modos W que N códons podem ser arrumados nas N_i posições do DNA é dado pela combinatória

W = N! / N₁!N₂!…N_m!

Para evitar números imensos que crescem exponencialmente com as multiplicações, e considerando que as mensagens não se multiplicam, mas se somam no canal de transmissão, a medida de entropia de Shannon H é dada pela função logarítmica:

H = lnW 

Como não estamos especificando que tipo de código será usado, empregamos o logaritmo natural na formulação da expressão. No caso de usarmos o código binário, a expressão pode ser escrita como

A expressão da entropia de Shannon se obtém da seguinte forma. Escrevemos a expressão acima como

H = - log₂W 

Que é reescrita como

H = - log₂N! - ∑log₂N_i! 

Como N é grande, usamos a aproximação de Stirling lnN‼ ≈ NlnN, e fazendo p_i = N_i/N, chegamos à fórmula de Shannon:

H = -∑ p_i log₂ p_i  

O sinal negativo é adicionado par tornar o resultado positivo, pois estamos lidando com eventos que pode ou não pode acontecer. A expressão satisfaz às condições estipuladas por Shannon. 

Todo esse tratamento só é aplicável aos sistemas ergódicos, isto é, a sistemas cujas probabilidades de estado são estacionárias. E além disso, os que seguem uma estatística de Fermi-Dirac. 

 ***

MÁQUINAS DE TURING

Este capítulo é introdutório para a leitura do livro "Teoria da Informação e o Código da Vida", portanto está protegido por copyright e por isso a fonte deve ser citada: Portela Câmara F. Computabilidade, Máquinas de Turing, Vida, In: Genes, Populações e Epidemias, blog, popdinamica.blogspot.com.br.

Fernando Portela Câmara, Prof. Associado UFRJ

O que denominamos "processamento da informação" é o mesmo que "computação". A computação lida com linguagens ou códigos mediante os quais uma máquina executa uma série de instruções precisas e logicamente dispostas (algoritmo) para encontrar a solução de um problema, executar uma tarefa ou comportar-se segundo um determinado padrão. A linguagem deve ser precisa e sem ambiguidades para que a máquina opere corretamente e pare ao concluir a tarefa determinada. Esta característica é a propriedade fundamental dos algoritmos.

Um computador é uma máquina controlada por uma linguagem que a faz executar um algoritmo. As instruções para isto são dadas na forma de uma lista de etapas a serem cumpridas, ou "programa". Este tipo de máquina que funciona por meio de um programa é também conhecida como "autômato". 

O ponto essencial é ter em mente que um computador recebe uma entrada (ou input) de dados codificados em uma linguagem ou fileira de símbolos, processa esses dados segundo um algoritmo específico, e dá o resultado (saída ou output) igualmente em linguagem codificada. Qualquer informação, textual, numérica, geométrica, abstrata, enfim, tudo que pode ser verbalmente descrito com um número finito de palavras, é computável. Toda informação computável, portanto, é dada na forma de mensagens, ou seja, fileira de símbolos dispostos segundo certas regras que assim produzem um sistema de código. DNA, RNA, polipeptídios, impulso bioelétrico em vias nervosas, etc., são informação veiculadas por mensagens.

As propriedades informacionais de qualquer mensagem, incluindo as biomacromoléculas, não se originam de suas propriedades físicas ou químicas, mas unicamente da sequência de seus monômeros que passam a representar símbolos. Informação é simbólica, não se trata de matéria ou energia, mas de sequências especificadas por um código de símbolos. Se o processamento da informação for conduzido com um mínimo de erros, numa incidência tal que não afete a fidelidade da mensagem a ser transmitida e traduzida, então ela se propagará no tempo e no espaço sem perder suas características essenciais. Há 4 bilhões de anos os genes fundamentais para a existência da vida se transmitem e propagam-se com um mínimo de variação, e a razão disto é que a vida foi criada por um código digital, linear e replicante, que incorporou redundância suficiente para minimizar drasticamente os erros ou ruídos (mutações pontuais) causados por tunelamento quântico na estrutura molecular do mesmo.

Para que isso aconteça, é preciso que o código de transmissão seja capaz de corrigir erros, e isto é o objeto central da teoria da codificação que deriva do teorema central da teoria da informação, o teorema de Shannon da capacidade de canal, assunto tratado no meu livro "Teoria da Informação e o Código da Vida".

Desde que tenhamos um código genético já acabado, e que por isso não mais evolui (é a variância de erros e combinação de informações que permitem que as espécies evoluam), a questão essencial é saber os princípios que tornam possível a compilação de informação codificada em DNA/RNA para um código polinucleotídico. Há dois níveis para se chegar a essa compreensão: a computabilidade ou forma de processamento da informação, e a disjunção entre informação e sistema operacional. Estes assuntos são tratados no meu livro já citado.

O fundamento da computabilidade é a teoria da Máquina de Turing, uma ferramenta lógica que compreende em si a teoria da computação, a teoria algorítmica e o fundamento da teoria da programação. Uma máquina de Turing é uma estrutura lógica não apenas abstrata, mas algumas vezes observada na natureza em seu nivel mais elementar, por exemplo, um ribossoma pode ser considerado uma máquina de Turing operando cobre uma fita externa que contém o input (mRNA) e um respectivo output (polipeptídio). 

Uma máquina de Turing é um computador idealizado com a estrutura mais rudimentar possível. Imaginemos uma fita infinita dividida em células quadradas, passando sob uma cabeça de leitura que pode estar em um número finito de estados internos. A cabeça pode ler o que está na fita, ou escrever símbolos 0 e 1 na mesma. Apenas 0 e 1 são necessários , uma vez que qualquer informação pode ser codificado usando apenas 0s e 1s. Por exemplo, podemos usar no código Morse, com 0 representando um ponto e 1 um traço (um código binário padrão seria mais provável na prática). O comportamento da máquina é controlada por uma espécie de programa de computador, chamado de programa Turing-Post . Este é composto por etapas numeradas, sendo cada passo um de sete comandos:

Imprimir 1 na célula atual.
Imprimir 0 na célula atual.
Mover uma célula para a direita .
Mover uma célula esquerda .
Vá para o passo programa k se a célula atual tem 1.
Vá para o passo programa k se a célula atual tem 0.
Pare

Assim como o programa, deve haver alguns dados de entrada sobre a fita para o programa poder operar. O aparelho processa os dados de acordo com o programa, e depois pára. Por exemplo, suponhamos que os dados iniciais é um bloco de 1s, terminada por 0s, tal como

…0111111110…

onde a seta aponta para a célula atual. Suponha que nós queremos que a máquina mude as terminações 0s por 1, e depois pare, alongando assim o bloco por mais dois. O seguinte programa faz isso:

1 . mover para a direita
2 . Se o dígito for 1, vá para o passo 1
3. imprimir 1
4 . mover para a esquerda
5. Se o dígito for 1, vá para o passo 4
6. imprimir 1
7. Pare

A cabeça se move para a direita até encontrar o primeiro 0, e o substitui por um 1, então se move para a esquerda até encontrar um 0, que substitui por um 1 e então para. Você pode imaginar que um dispositivo tão simples tem apenas um limitado repertório de truques. Não é assim, como Turing mostrou. Tudo o que um computador pode calcular, uma máquina de Turing pode assim fazer. Lentamente, é claro, mas o que importa é que isso é uma ferramenta lógica que permite ao teórico encontrar os insights necessarios ao entendimento da natureza da computabilidade.

Um programa de Turing-Post só pode ser codificado na fita, por exemplo, utilizando os seguintes códigos:

000 Imprimir 0
001 Imprimir 1
010 Mover para a direita
011 Mover para a esquerda
10100 ... 01 Vá para a etapa k se o dígito for 0
11011 ... 10 Vá para a etapa k se o dígito for 1
100 Pare

Aqui o ... Indica k repetições. O programa acima, em seguida, codifica como

0101101000101111011110001100

Podemos reconstruir qualquer máquina exclusivamente a partir do seu código (programa). Turing mostrou em 1936 como construir uma máquina de Turing universal - chamemo-la de U - capaz de simular a ação de qualquer programa em qualquer máquina de Turing. Ela tem um programa fixo. Seus dados de entrada são uma sequência de 0s e 1s do código do formulário (M) ∙ d para uma máquina com programa M e entrada de dados d. O programa para U faz uma varredura no código, decodifica as ações para M, e as executa sobre os dados d. Qualquer computador, com tempo e memória suficiente, pode ser programado para simular qualquer outro computador, embora isso possa se dar lentamente. O programa incluirá uma descrição codificada completa da máquina que está sendo simulada e da forma como ela funciona. Assim, para fins teóricos, podemos generalizar a noção de que qualquer cálculo que seja computável está representado em uma máquina de Turing (Tese de Church-Turing), um algoritmo definido em um programa de Turing-Post.

O problema da Parada e suas Implicações

(Continua)