The halting problem

Trip Start Nov 14, 2007
1
16
20
Trip End Ongoing


Loading Map
Map your own trip!
Map Options
Show trip route
Hide lines
shadow

Flag of Brazil  ,
Saturday, January 12, 2008

The meaning of existence can't be supplied by religion or ideology.

Aviso: texto recheado de devaneios matemáticos e pior, pseudo-matemáticos.

Quando eu era criança e via o programa do Chaves, havia uma cena que se repetia que envolvia as 'crianças', na verdade adultos vestidos assim, numa disputa para ver quem dizia o número mais alto. Elas tomavam turnos e, surpreendentemente, a criança mais esperta era sempre a última a dizer e sempre ganhava. Uns tempos depois, topei com um artigo de um  matemático (acho, perdi a referência) que discutia o que aconteceria se numa competição desse tipo todos escolhessem seus números ao mesmo tempo. Por exemplo, se as pessoas tivessem um minuto para escrever num pedaço de papel o número que quisessem. A conclusão era que venceria quem conhecesse o processo mais poderoso para geração de números enormes. Até fiz uma vez esse experimento na faculdade, mas infelizmente notei que entre os psicólogos nenhum conhecia ou foi capaz de inventar um algoritmo razoavelmente interessante.
De qualquer forma, o interessante não era a conclusão própria do artigo, mas sim uma passagem sobre o 'halting problem', que dizia mais ou menos assim, se bem me lembro: os processos padrão de geração de números enormes todos geram seqüências computáveis, ou seja, um computador com tempo suficiente pode calcular qualquer valor da seqüência. Aí é que entra o problema, porque no que chamam de máquina de Turing (que é, digamos, o esqueleto teórico de um computador) qualquer programa ou vai executar um número finito de passos e parar ou vai continuar funcionando para sempre. Isso é óbvio por lógica simples, a parte interessante é que existe um limite superior de passos finitos que um programa de 'x' linhas pode dar - se ele passar desse limite é certo que vai continuar para sempre. O problema de calcular o limite superior para qualquer número de linhas se mostrou não computável, e foi a explicação desse fato que me fez gostar mais do artigo.
O 'halting problem' consiste em encontrar um programa que seja capaz de determinar se qualquer outro programa pára ou não. Infelizmente esse problema é insolúvel, porque se houvesse um programa A capaz de desempenhar essa tarefa, poderia ser construído um programa B que executasse o programa A em relação a ele e a partir dessa informação fizesse exatamente o contrário do que o programa disse. Essa conclusão implica a não-computabilidade da seqüência descrita, porque se fosse computável o programa A poderia executar o programa B pou um número de passos igual ao limite superior para ele e então determinar se ele pararia ou não.
Conclusão trocada em miúdos: um programa de computador não pode prever o comportamento de programas de computador em geral, porque pode surgir um programa do contra que use o conhecimento sobre o primeiro só para contrariá-lo. Tenho a impressão de que as palavras 'programa de computador' possam ser substituídas por várias outras sem prejudicar a conclusão. E se essa expressão fosse trocada por 'pessoa'? 'Consciência'? Há vários corolários interessantes. Uma pessoa não pode prever o que fará no futuro, porque se pudesse, ela também poderia, de posse dessa informação, decidir contrariá-la. Deus pode até prever as pessoas, mas não a si mesmo. O sentido da vida não pode ser explicado por religião ou ideologia, porque essas existem no pensamento da pessoa, e o pensamento é posterior à vida. O halting problem é o problema fundamental do auto-conhecimento, e foi provado insolúvel.

Pois é, Arapiraca é a segunda maior cidade das Alagoas e não encontrei nada para fazer aqui a não ser ficar divagando. Aproveitei para inventar uma ligação louca entre um artigo de que gostei muito e estava na minha cabeça e uma música de que gosto muito e estava na minha cabeça, não pretendo na verdade ter encontrado a resposta definitiva para nenhum dilema existencial fundamental, a não ser o que afeta apenas a mim: eu preciso estudar matemática. Faz um ano inteiro que parei e minha vontade de voltar vem se aproximando assintoticamente do insuportável. O primeiro resultado da sopa está pronto, embora seja apenas um resultado preliminar.

P.S.: Essa mensagem provavelmente definiu o limite superior da separação entre texto e cidade.
Ainda mais P.S.: Crédito a Érika pela consultoria técnica. :)
Report as Spam

Comments

marja
marja on

Nó cego ou dilema de personagem Shakespeareano?
Uau! Tive que sacudir a minha cabeça para voltar ao normal (se é que existe o normal). Mas, gostei, como gostei também do relato anterior. Suas considerações sobre o tempo são interessantes, e, justamente, eu achei interessante numa entrada anterior, quando você falava sobre seus amigos quererem aproveitar o tempo de uma maneira que eu tive a impressão que para você seria desperdiçá-lo e em seguida você falou algo sobre passar o tempo para chegar uma hora em que o tempo realmente poderia ser aproveitado (por você, no caso)...

ganesha_v
ganesha_v on

Complexo?! (melhor que chato)
Um tanto complexo esse pensamento... pode até ser que não tenha entendido nadica de nada, ou tenha entendido tudico de tudo e não tenha surtido maiores descobertas. Elas foram as suas e fiquei feliz por isso!!! Muito bom! O distanciamento do mundo real, rotineiro, pode ser um deslocamento inerte e ativo.
Beijo

elthon on

interessantes sua ótica sobre o problema da parada.

mas arapiraca tem coisas a fazer sim. por exemplo: pensar na computabilidade dos números tomando uma cerveja no "bar da baxa" ou no "mistura fina" :-)

Add Comment

Use this image in your site

Copy and paste this html: