Simulação de Máquina de Turing através de Redes Neurais
Links:
Neste estudo naturalmente foi estendendido as redes neurais de Aleksander e mostrado como esse modelo simula o comportamento de uma Máquina de Turing. É amplamente acreditado que a única verdadeira simulação neural de uma Máquina de Turing deveria ser interna. Como uma conseqüência autores têm proposto redes neurais ou com número infinito de neurônios ou com número finito de neurônios mas com pesos ilimitados.
Aqui discorda-se deste ponto de vista defendendo-se a posição que a fita infinita de uma Máquina de Turing é uma característica externa não intrínseca, que não precisa necessariamente ser internalizada.
Uma Rede neural lógica (RNL) é um arranjo de um número finito de nós em qualquer número de camadas, com ou sem conecções de retorno, onde os nós são k-RAMs (memórias de acesso aleatório com k terminais de entrada) guardando palavras de n bits. Cada palavra de n bits é considerada para guardar um número do intervalo de 0 a 1 que representa a “probabilidade de acerto” do nó. Neste estudo vai se adotar um modelo mas simples no qual tem-se palavras de 1 bit e a saída é 1/0, dependendo apenas do valor guardado. Há muitas vantagens nestes modelos em relação ao modelo com pesos e, talvez, o mais importante é que este modelo é direcionado para implementação em hardware.
Um dos autores havia previamente proposto um novo reconhecimento do algoritmo e estendido o nó lógico utilizado em RNL o qual faz o RNL equivalente ao autômato probabilístico como um mecanismo de reconhecimento da linguagem. A classe de linguagem aceita pelo autômato probabilístico é bastante poderosa e inclui todas as linguagens regulares, algumas linguagens livre de contexto, algumas sensíveis ao contexto e até algumas linguagens recursivamente enumeráveis. O inespecificado “algumas” é realmente desconhecido em geral, há exemplos em linguagens dentro e fora de cada classe, com a óbvia exceção das linguagens regulares.
Neste contexto estende-se a RNL adiante (delicadamente e naturalmente) para simular máquinas de Turing. Uma máquina de Turing é uma combinação de uma máquina de estados finita com um mecanismo de infinitas células de memória (fita) no qual pode-se escrever e ler símbolos de um conjunto finito. A fita é lida na direção direita ou esquerda, uma célula por vez. Uma RNL, e qualquer Rede Neural Artificial (RNA), é um autômato finito de estados. O único componente que falta é o acesso a uma fita similar a da máquina de Turing. Isto pode ser alcançado codificado-se instruções de uma saída de uma rede neural com retorno e imaginando-se que a entrada da rede é alimentada de uma fita. A mesma fita é também usada para armazenar a saída da rede. Chama-se esta extensão uma Rede Neural Lógica de Turing. Esta extensão não é totalmente irrealista como pode parecer de primeira vista. Uma visão mais ampla do sistema humano neural como uma caixa preta neural faz o mundo exterior executar o papel da fita da máquina de Turing. Se nós estamos, por exemplo, fazendo cálculos com lápis e papel, o papel faz ao mesmo tempo o papel do mecanismo de entrada e saída.
É importante notar que o “cérebro” de uma máquina de Turing é o seu controle: um autômato finito de estados. O acesso ao mecanismo de memória (fita) é apenas para ajudar a computação: armazenando resultados parciais. O que faz da máquina de Turing computacionalmente poderosa o suficiente para modelar computações efetivas (Tese Church-Turing) é o conjunto de operações permissíveis na fita. Os vários tipos clássicos de autômatos finitos na literatura da ciência da computação podem então grosseiramente classificadas de acordo com o conjunto de operações permitidas em suas fitas. Um autômato de estados finito (reconhecedor de linguagens regulares) tem uma fita de entrada e uma de saída, mas isto só é permitido para mover as cabeças para a direita e como conseqüência não é capaz de reusar computações passadas. Um autômato à pilha (reconhecedor de linguagens livre de contexto) tem seu acesso à fita restrito à operações com a pilha. Um autômato linear limitado (reconhecedor de linguagens sensíveis ao contexto) é uma máquina de Turing com as retrições que a cabeça não pode deixar aquelas células nas quais a entrada foi colocada. Enquanto uma máquina de Turing tem acesso irrestrito à fita. Valer a pena apontar que nos quatro casos as fitas são assumidas como infinitas e o “cérebro” de cada tipo de máquina é ainda um autômato finito de estados. Em alguns casos é importante destinguir entre máquinas determinísticas e não determinísticas, mas este é um ponto de vista fora deste trabalho e o leitor interessado deveria consultar a literatura.
O ponto é que o fato que esta memória é potencialmente infinita não deveria ser considerado como um mecanismo intrínseco da máquina de Turing como tem sido indicado em alguns livros de computação neural.
A memória está lá para uso, mas em qualquer momento a máquina de Turing não é permitida usar a fonte infinita toda. Apenas partes finitas da fita podem ser usadas em qualquer estágio da computação. É a execução finita, repetitiva e incessante de instruções que importa. E, como vimos acima, o conjunto de operações permitidas é de fundamental importância. E estes aspectos da máquina de Turing capturam razoavelmente bem a noção de computabilidade efetiva. O acesso a uma fita infinita tem também vantagens técnicas óbvias. Pode-se falar, por exemplo, de computações de funções teoréticas de números, f: N -> N, aonde N é o conjunto dos números naturais, mesmo que não seja possível para qualquer mecanismo ou qualquer ser humano realmente computar esta função. Tome como exemplo a adição de números naturais: todos nós sabemos como proceder com a adição de dois números dados , mas não seria possível para nós realmente computar a adição + : N² -> N para todo o domínio definido: apenas imagine números suficientemente grandes os quais a adição iria nos levar a, digamos, um bilhão de anos para realizar. Mas isto não é o que importa para o estudo das computações efetivas mas preferivelmente o fato de que há algo mecânico, repetitivo, efetivo, algorítmico sobre adição que nós podemos capturar. E uma vez que nós aprendemos como somar um conjunto finito de pares de pequenos números naturais dizemos que podemos (em princípio) somar quaisquer dois dados números naturais quando nós realmente sabemos como executar um algoritmo de soma.
Esta idéia de suprir uma rede artificial com uma cabeça e uma fita tinha sido levada adiante antes por McCulloch e Pitts no seu trabalho pelos sistemas dos pesos. Esta aproximação tem sido criticada como não sendo verdadeiramente uma simulação de rede neural. Nós discordamos fortemente disto e baseamos nossa simulação exatamente na idéia de adicionar uma fita à rede neural lógica.
Abaixo, foi formalizada a noção intuitiva de uma máquina de Turing descrita acima. Há várias formas equivalentes de definir uma máquina de Turing. O importante, tecnicamente, é o uso de um sistema binário de codificação.
Definição
1 Uma Máquina de Turing M sobre Z = {0, 1} consiste de:
1.um conjunto finito de estados Q = {q0, ..., qn}
com um estado (inicial) distinto, q0.
2.uma função s : Q X Z -> Q X Z X
{L, R, S}, s deve ser pensado como um conjunto finito de instruções
e
s(qi, o) = (qj, o', m)
siginifica que a máquina estando no estado "qi"
E Q e lendo o símbolo "o" E Z a partir da célula corrente
na fita, tomará as seguintes açoes:
- Apaga o e escreve o' em seu
lugar;
- Muda o estado interno de qi para qj, e
- Muda a posição do cabeçote uma
célula para a esquerda (m = L), uma para a direita (m = R) ou pára
(m = S)
Observação 1: Observe que ao requerer que o conjunto de instruções seja uma função, nossa definção exige que a máquina seja deterministica e que deva ser completamente especificada. Isto simplifica nossa prova.
A simulação pode ser facilmente entendida ao observar que computações numa maquina de Turing são controladas por tres automatos de estados finitos: um controla os movimentos do cabeçote, o segundo controla entrada/saída e o terceiro o próximo estado. Estes automatos correspondem a tres componentes na imagem da funcao de instruçao ? na Definição 1.
Nós podemos assim facilmente ver que nos podemos simular o comportamento de uma máquina de Turing com redes logicas neurais de uma única camada com feedback como na figura 1. Cada neuronio é uma k-RAM com k = log n + 1.. O j- ésimo bit do vetor de estado corrente qi está ligado ( não mostrado na figura) ao terminal de entrada xj, 1 <= j <= k – 1, de cada neuronio. Igualmente o simbolo corrente o é ligado (mas não mostrado) ao terminal de entrada xk de cada neuronio.
Os dois
primeiros neuronios RAM (de cima para baixo) produzem os movimentos com,
por exemplo, L 00, R = 01 e S = 10; o terceiro neuronio RAM produz simbolos
em Z .
Os log n neuronios restantes produzem o próximo
estado da máquina de Turing sendo simulada que é entao realimentada
à rede. A configuraçao na Figura 1 : representa equação:
s(qi, o) = ( qj, o’, m). Nós assim provamos esboçadamente o seguinte:
Teorema 1 Qualquer maquina de Turing sobre Sigma = (0, 1) com n estados pode ser simulada por uma rede neural logica de Turing (TLNN) com log n + 3 ( log n + 1) neurônios RAMs.
O resultado
obtido é extraordinariamente simples se comparada a provas similares
de equivalencia usando o modelo com pesos. Nesse método a fita infinita
é simulada “dentro” da rede via os pesos das conexões ou
por assumir uma infinita quantidade de nós. O modelo anterior requer
pesos ilimitados o que exige codificação muito intrincada.
Vale a pena apontar que, como o modelo apresentado aqui é sem pesos,
não há forma concebível de empregar técnicas
usadas em outras literaturas onde a fita é representada nos pesos
das conexões. Os métodos com com peso divergem entre si ao
usar
- número infinito de nós;
- número finito (em alta ordem) de nós
com pesos ilimitados;
- número finito de nós com interconecções-lineares
e de pesos ilimitados. Vale a pena mencionar que isto é realizado
ao usar pesos racionais .
Poderia ter
sido usada uma representação interna da fita da máquina
de Turing ao permitir um número infinito de neurônios.
O resultado
aqui estabelece, à nivel teórico, a relação
entre modelos neurais e convencionais de computação e permite
possibilidades (teórica) de usar ANN em tarefas cognitivas
de “alto nível” tal como processamento de linguagens naturais.