Gedankenexperiment solução do problema do caixeiro-viajante por interferometria da luz branca

9 de Agosto de 2007, por Desconhecido - 33 comentários

O problema do caixeiro-viajante é NP-completo, e dois pesquisadores da universidade de Stuttgart inventaram um experimento mental para resolver o problema não por meio de computação propriamente dita, mas por meio de um experimento ótico.

O problema do caixeiro-viajante pode ser encontrado em muitos livros de compuração, especialmente os que lidam com inteligência artificial. Grosso modo, é o problema de um viajante visitar várias cidades numa certa região visitando cada cidade exatamente uma única vez e percorrendo o menor caminho possível.

O artigo descrevendo a solução anunciada está aqui. A idéia básica por trás do experimento é a de ligar um conjunto de dispositivos de "retardo" da luz ("delays") por meio de fibras óticas de tamanho proporcional às distâncias entre as cidades. Cada "retardo" faz com que a luz "demore" um tempo pré-definido e muito maior que o tempo para percorrer todas as fibras óticas. De modo que cronometrando o tempo que leva para a luz entrar e sair pelo mesmo dispositivo de "retardo" obtém-se o tempo que leva para a luz percorrer as fibras. Como cada "retardo" tem um tempo grande e pré-definido, pode-se ir eliminando as soluções que não visitam certas cidades (por exemplo, se um "retardo" é de 5 segundos e a luz demorou 3 segundos para entrar e sair, ela certamente não visitou aquele dispositivo de "retardo").  Obtém-se dessa maneira o menor tempo necessário para percorrer todas as cidades. O artigo descreve como determinar o caminho percorrido desligando fibras sistematicamente, até que sobre apenas o caminho percorrido.

O resultado final é que o problema NP fica reduzido a uma solução quadrática. 



Simulação: sincronia e diacronia

19 de Julho de 2007, por Desconhecido - 0sem comentários ainda

Uma teoria hipotética de simulação pode partir dos conceitos de sincronia e diacronia. A sincronia corresponde a cada determinado "estado do mundo" e a diacronia corresponde à função sucessora de um certo "estado do mundo" para o "estado do mundo" imediatamente posterior.

Isto, é claro, quanto a simulações determinísticas. Uma simulação não-sequencial (estou pensando aqui especialmente numa simulação do tipo Monte Carlo) manteria a relação sincronia/"estado do mundo", mas e quanto à diacronia?

Obviamente que as funções geradoras de estados não-sucessivos não podem ser relacionadas com um conceito de diacronia de maneira razoavelmente similar (isto é, análoga) à maneira com que relacionamos a diacronia com as funções sucessoras das simulações determinísticas.

 Creio que a diacronia pode ser relacionada com as funções que selecionam estados possíveis e descartam estados impossíveis, na simulação montecarlina. Para afirmar que isto é análogo à relação diacronia/função sucessora, é necessário abstrair da implementação (afinal, no caso das simulações determinísticas tratam-se de funções sucessoras, enquanto que nas simulações montecarlinas tratam-se de funções comparativas).

 Enfim, os "estados do mundo" são sincrônicos pois correspondem a uma disposição estática de elementos, a um conjunto ordenado de elementos, a um 'espaço'.

 Enfim, a diferença entre cada "estado do mundo" é diacrônica pois corresponde a mudanças dos elementos sincronicamente enumerados, a movimento interno ao conjunto, a um 'tempo'.

 E portanto os conceitos de sincronia (espaço) e diacronia (tempo) permitem definir um esquema teórico para a simulação, desde que essa simulação seja uma simulação espaço-temporal.

 Um tipo de simulação que não é espaço-temporal é, por exemplo, a simulação linguística. Outro exemplo é a simulação psíquica. Nesses casos, e em casos simliares, a simulação espaço-temporal pode ser no máximo uma auxiliar: por exemplo, pode-se simular espaço-temporalmente o corpo que pensa ou fala, mas não a própria ação de pensar ou falar, pois estas ações são computacionalmente intratáveis espaço-temporalmente. Em outras palavras, simular o pensamento ou a língua "átomo por átomo" exigira computadores muito mais rápidos do que os computadores que nós, hoje, pensamos que será possível construir no futuro. Portanto, para fazer simulações desse tipo (que eu denomino "simulações semânticas"), hoje, devemos nos ater a abstrações, como por exemplo a psicanálise e a linguística.

 Concluindo, nem toda simulação é simulação "concreta" ou espaço-temporal, mas as que o são podem ser conceituadas como sincronias diacronicamente encadeadas.