``It is later than you think'' could not be expressed in Martian - nor could ``Haste makes waste'', though for a different reason: the first notion was inconceivable while the latter was an unexpressed Martian basic, as unnecessary as telling a fish to bathe. But ``As it was in the Beginning, is now and ever shall be'' was so Martian in mood that it could be translated more easily than ``two plus two makes four'' - which was not a truism on Mars.
Robert A. Heinlein, Stranger in a Strange Land
1Ninguém
sabe como ou por que desapareceu a civilização marciana, mas
uma caverna no sopé do monte Olimpo guarda uma triste
recordação desta cultura antiga e fabulosa. No interior da
caverna existe uma placa, reminiscente da famosa pedra de Roseta,
coberta por um tecido empoeirado de composição desconhecida.
Afastando este tecido, surge o que parece ser uma espécie de
dicionário: uma lista de palavras na metade esquerda da placa
está associada a uma lista à direita. Duas frases aparecem
gravadas no fundo da placa. Essas frases estão relacionadas de
uma forma peculiar. A primeira pode ser transformada na segunda
por substitui ção repetida de palavras contidas no dicionário:
cada palavra da frase no lado esquerdo do dicionário pode ser
substituída pela correspondente palavra no lado direito. Os
sábios do Marte antigo defendiam que qualquer informação que
valesse a pena aprender, podia ser obtida começando com uma
frase básica e substituindo palavras de acordo com o dicionário
da sabedoria, cujo único fragmento se encontra na caverna. Em
geral, um computador não poderá verificar se uma dada frase
pode ser derivada da frase básica. Por outras palavras, não
existe qualquer possibilidade de escrever um programa de
computador (não importa quão extenso ou rápido) que seja capaz
de decidir correctamente, para cada dicionário e duas palavras
(ou frases) de entrada, se é possível a tradução da primeira
para a segunda palavra. A demonstração decorre da
insolubilidade do chamado problema de paragem e do facto de que o
problema da paragem pode ser convertido no problema da tradução
marciana. O problema da tradução marciana é um exemplo
de uma família de puzzles que requerem a transformação de
palavras, frases e até parágrafos inteiros em outras palavras,
frases e parágrafos. Entre muitos passatempos matemáticos e
simbólicos destaca-se uma transformação chamada ``escada de
palavras''. Numa escada de palavras começamos com duas palavras
específicas. A primeira palavra chama-se origem e a segunda
destino. Poderemos transformar a palavra origem na palavra
destino alterando uma letra de cada vez? Se as duas palavras têm
o mesmo número de letras, a tarefa é trivial. Mas poderemos
garantir que todas as cadeias de caracteres intermédias são
também palavras? Podemos, de facto, partir de ``gato'' para
ilustrar o processo. Num passo, a palavra pode ser alterada para
``pato''; noutro passo, para ``rato''. Com esta alquimia até
parece possível que ``gato'' pode ser facilmente modificado para
qualquer nome com quatro letras. Será isto possível?
Algumas ideias para o trabalho - ``achas para a fogueira''