TuringNS2 é uma implementação de Máquina de Turing[1] no simulador de redes NS-2 [2].
A prova da corretude da implementação da máquina é ilustrada no próprio vídeo com quatro estudos de caso: soma, subtração, verificação de palíndromos e ordenação com o método Bubblesort. Para cada um desses casos, uma sentença de entrada é submetida à Máquina de Turing que, por sua vez, realiza as operações sobre essa sentença de acordo com as regras definidas na tabela de transições. Para cada um dos estudos de caso existe uma tabela de transições com o "programa" a ser executado sobre a sentença de entrada.
Por outro lado, NS-2 é um simulador de eventos discretos voltado para a simulação de redes, e é muito utilizado em trabalhos acadêmicos para simular o comportamento de protocolos de rede e o roteamento em redes cabeadas e wireless.
A programação em NS-2 é feita na linguagem Object TCL. A visualização da topologia da rede e do tráfego de pacotes que flui na rede é feita com o software NAM. No desenvolvimento da Máquina de Turing no NS-2 foi desenvolvido um programa em linguagem Java para traduzir as transições das tuplas em linguagem inteligível pelo NS-2. O simulador de redes é responsável por manter o tráfego de pacotes entre os links que ainda não foram processados. Cada link na rede tem uma largura de banda para uma vazão de até 1Mb/s. Cada nó gera tráfego a uma taxa de 0.5Mb/s para o próximo nó, ou seja, a rede possui múltiplas duplas de nós geradores e consumidores de tráfego. Cada dupla é uma subrede da rede que representa a fita.
Quando uma transição nas tuplas implica em substituir o símbolo do estado atual pelo símbolo vazio (representado por um ponto), o link entre os nós imediatamente antes e após o nó atual são desabilitados. Esse é um comportamento semelhante a um fluxo de água: cada nó da rede é uma "torneira" que permite ou não a passagem de fluxo por ela. Quando a "torneira" é fechada, o fluxo não flui mais para os seus nós vizinhos, e ocorre o descarte dos pacotes.
Sentenças de entrada inválidas para operações de subtração que geram resultado negativo implicam em sobra de símbolos diferentes de 1, como mostra o exemplo no vídeo para a sentença de entrada 11-111=. No caso da verificação de palíndromos o algoritmo das tuplas determina a escrita na fita das palavras SIM e NAO caso as sentenças de entrada sejam válidas ou não, respectivamente.
Todo o código-fonte do projeto, incluindo os exemplos comentados dos programas de Turing mostrados no vídeo estão disponíveis gratuitamente [3].
Referências:
[1] Turing, A. M. "On computable numbers, with an application to the Entscheidungsproblem", Proceedings of the London Mathematical Society, Series 2, 42 (1936), pp 230 - 265.
[2] The network simulator NS-2. Disponível em: http://www.isi.edu/nsnam/ns/.
[3] Rocha, L. A. "TuringNS2. Uma Máquina de Turing no Simulador de Redes NS2". Disponivel em: http://sourceforge.net/p/turingns2.
Dúvidas, críticas ou sugestões por ser enviadas por e-mail para: outrosdiasvirao [at] gmail [dot] com
