Home
Publicar Site
Tutoriais - Áudio
WINZIP (dicas)
Imagens Para Internet
A Máquina de Post
Páginas Pessoais

A Máquina de Post

 

OBJECTIVO:

 1. Sensibilização para o conceito de algoritmo, um dos mais usados no nosso dia-a-dia, embora nem sempre de forma consciente e também um dos conceitos centrais da informática (programação), da cibernética e da lógica matemática (que usamos mais vezes do que realmente pensamos);

 2. Entrada no mundo da programação, através de um dos mecanismos mais adequados para essa iniciação.

 3. Esclarecimento do conceito de “máquina universal”

  

Introdução:

 Antes de mais, dizer que a presente página foi suscitada e baseada no livro “A Máquina de Post”, de V. Uspensky, editora Mir, 1979 e traduzida para Português por Eng. António João Ribeiro Prestes, com edição de 1985. Esse livro integra-se num colecção de fascículos com o título “Iniciação à Matemática”, do qual fazem parte vários outros volumes bastante interessantes e escritos de modo a introduzir, duma forma acessível, temas matemáticos importantes e que habitualmente só vemos tratados a nível superior.

 Para que os objectivos possam ser atingidos vamos basear-nos, ao longo de todo este artigo, na máquina abstracta de Post. Ela é abstracta pois é, como muitas outras, uma construção da mente e imaginação humana (embora nada impeça que seja materializada), mais propriamente do eminente matemático americano Emile L. Post, que a apresentou na década de 30 (ver artigo original).

O que torna esta “máquina” tão apetecível é o facto de que os princípios lógicos que a regem terem sido usados, posteriormente, pelos computadores digitais que domina, hoje em dia, a nossa vida quotidiana.

Torna-se pois, como é bom de ver, um instrumento adequado para a compreensão dos princípios básicos pelos quais se rege o funcionamento dos computadores.

Embora exista uma outra “máquina”, do mesmo tipo, mais famosa (a máquina de Turing), pensamos que a máquina criada por Post se adequa melhor aos nossos intentos devido à sua maior simplicidade. Isto é tanto mais verdade se pensarmos que um dos objectivos principais perseguidos por este artigo é que os conceitos de algoritmo e programação, omnipresentes na nossa vida presente e futura, seja apreendido em profundidade a partir de uma idade precoce. A nossa opinião, e a escrita do texto não deixará de ter isso mesmo em vista, é que devemos começar a formar as pessoas nesta área logo a partir do 1º ano do 1º Ciclo. É evidente que algumas simplificações terão de ser feitas nessa tenra idade , tal como acontece em todas as matérias, ir aprofundando o tema ao longo da vida escolar (ver notas didácticas).

Julgamos que esta seria uma medida que, quando inserida num quadro integrador mais vasto da educação para a ciência, contribuiria para uma formação dos nossos cidadãos mais adequada aos nossos tempos e com frutos a médio prazo. A pretensão deste artigo é ser um pequeno e modesto contributo para essa visão que esperemos, a curto prazo, se torne uma realidade.

 Agradecemos imenso que nos sejam enviadas críticas sobre o trabalho apresentado, se possível complementadas com sugestões para melhorar a qualidade do presente texto em todos os aspectos: técnico, linguístico, pedagógico, didáctico, etc. Esta página é uma página aberta que espera acolher as contribuições de todos os interessados.

 

Um outro objectivo que esperamos seja cumprido é o enriquecimento desta mesma página com outros programas especificamente concebidos para a máquina de Post. Caso estejam na disposição de colaborar, muito se agradece. Asseguramos a todos os programas enviados (o mesmo para qualquer outra contribuição) a devida identificação da sua autoria. Mãos à obra!

 

O que é a máquina de Post?

Tal como foi dito antes, trata-se duma máquina que é fruto da imaginação humana, pelo que o “trabalho” com ela requer, acima de tudo um esforço mental que, afinal, é o que nos caracteriza mais vincadamente como espécie diferente de todas as outras.

Essa máquina realiza um conjunto ínfimo de acções mas, a sua combinação adequada permite-nos resolver um vasto leque de problemas de nível superior, que usamos intensamente no nosso dia a dia, como por exemplo cálculos numéricos. A semelhança com os computadores começa a tornar-se evidente: também eles, com um conjunto limitado de acções, conseguem realizar as maravilhas que todos sabemos.

 

Qual a constituição  E MODO DE FUNCIONAMENTO da máquina de Post

A (imaginada, mas pode ser materializada) máquina de Post não é mais que:

uma fita de papel pautada em células, tipo linha de papel quadriculado e clips ou botões como marcas (ver figura abaixo).

 

 

 

 

 

 

 

 

 

 

 

                                          n

fig.1

 

Vamos convencionar, por mera simplificação de raciocínio, que a fita se estende infinitamente à esquerda e à direita.

Existe ainda um carro ou cabeça móvel de leitura e registo que se posiciona sempre em frente de uma das células (também visível na figura).

A ordem das células é semelhante à dos números inteiros (...,-3, -2, -1, 0, 1,2,3,...) constituindo um sistema de coordenadas que nos ajudarão a situar na análise e projecto de programas.

O estado da fita pode ser vazio ou marcado. Ver exemplo de um segmento da fita, com algumas células vazias e outras marcadas, na figura 2.

 

 

 

V

 

 

V

 

 

 

 

 

                                          n  (o carro observa a célula que se encontra à sua frente)

 

fig.2

 

Nessa figura vemos duas células marcadas (usamos o V como marca) e as restantes vazias.

O estado da fita num dado instante é definido pela configuração de células marcadas e vazias nesse mesmo instante.

O estado da máquina é formado pelo estado da fita mais a posição do carro.

Numa unidade de tempo (passo) o carro pode deslocar-se uma célula para a direita ou para a esquerda. Para além disso pode também marcar/escrever ou apagar uma célula ou ainda indentificar se uma célula está vazia ou marcada (ler).

 

NOTAS DIDÁCTICAS

No caso de alunos do ensino secundário pensamos que o tradicional quadro e giz (para além do mais importante que é a imaginação) será suficiente para expor tudo o que se refere à constituição e princípios de funcionamento da máquina de Post, bem assim como para proceder à explanação de exemplos suficientes (análise e síntese) para a completa compreensão do seu funcionamento.

Para se desenvolverem programas novos realça-se a posterior necessidade de tempo e motivação. Se existe matéria em que a prática é imprescindível ela é, como se sabe, a programação. Só se pode aprender a programar, programando. Parece uma verdade de La Palisse mas a prática ensinou-nos que esta verdade básica nem sempre é respeitada, mesmo que, muitas vezes, por razões perfeitamente válidas, como por exemplo a falta de tempo. Fica aqui no entanto, para aqueles que querem poder dizer um dia que sabem programar: Sem o seu profundo investimento individual e solitário (isto não é um libelo contra o trabalho em grupo. Tratam-se de planos diferentes. Não se pode contribuir para o trabalho em grupo se não se dominar o objecto do trabalho – outra verdade básica mas que é muito praticada e que leva a que muitos grupos funcionem deficientemente).

No caso dos estudantes de idades mais baixas, aconselhamos vivamente uma construção mais concreta, com fita e outros objectos que permitam materializar na realidade a máquina de Post e o seu funcionamento.

Outro facto que consideramos importante, embora vá contra as novas pedagogias que cada vez mais nos asfixiam (até já li que o facto de algumas crianças sofrerem de discalculia é devido aos professores lhes tentarem ensinar coisas demasiado teóricas, sem que elas vejam qual a utilidade prática daquilo que se lhes quer ensinar. Por essa ordem de ideias, o melhor era a instrução primária começar lá para os 18 anos...) é que a capacidade para compreende qualquer sistema de conceitos ou qualquer operação antes de se conhecer qual a sua necessidade/aplicação é uma das qualidades mais importantes do ensino da matemática, de a máquina de Post é apenas um exemplo. O esclarecimento da necessidade/aplicação só contribui para a memorização, mas não para a compreensão. A capacidade de pensamento formal é uma capacidade que se desenvolve, tal como qualquer outra, através do treino. Será pois importante, neste e em todos os casos, proceder à realização do número de exemplos e exercícios revelado adequado.

 

PROGRAMAÇÃO NA MÁQUINA DE POST

O funcionamento da máquina de Post consiste apenas na deslocação do carro ao longo da fita e impressão ou eliminação de marcas, de acordo com um conjunto de instruções de determinado tipo e que constituem um programa.

 

As acções permitidas à máquina de Post são:

1. Movimento para a direita                                       i. => j

2. Movimento para a esquerda                                  i. <= j

3. Imprimir marca                                                       i. V j

4. Apagar marca                                                          i. x j

 

 

                                                                                                        j1

5. Transmissão de comando                                       i. ?

                                                                                                       j2

 6. Instrução de paragem                                             i. stop

 

i e j (com ou sem indíce) são números. i é o número da instrução; j é o salto, isto é, o número da instrução que será executada a seguir à instrução i dessa linha.

No caso da transmissão de comando há duas hipóteses de salto: Salto superior (j1) caso o carro esteja frente a uma célula vazia, e salto inferior caso o carro esteja defronte de uma célula marcada.

 

É verdade. Com apenas estes 6 tipos simples de instruções diferentes é possível realizar operações complexas só ao alcance de seres superiores como nós, humanos.

É evidente que com um leque tão limitado de instruções possíveis, qualquer operação mais sofisticada fará, em geral, crescer bastante o tamanho do programa (número de instruções necessárias), criando grandes dificuldades práticas se quisermos materializar a máquina e “correr” o programa. Mas mesmo assim, será possível criar e materializar muitos programas com interesse, se não nos esquecermos que o objectivo principal é a compreensão e interiorização dos conceitos básicos presentes e não a resolução de problemas complicados.

Para isso temos os nossos “irmãos” computadores. Que, aliás, trabalham segundo o mesmo princípio da máquina de Post: um leque reduzido (bem, não tão reduzido) de instruções que conseguem fazer maravilhas. O segredo está no número dessas instruções básicas que o computador/processador consegue fazer por segundo (e que nós nem em sonhos conseguimos). Quando falamos em processadores de 2GHz e sabendo que 2GHz são 2 mil milhões de ciclos, por pouco que ele faça em cada ciclo (uma instrução demora alguns, poucos, ciclos), ao fim de um segundo (!!!) muita coisa está feita.

 Vamos pois começar com um exemplo simplicíssimo, dos tais que “não serve para nada” e que pode ser ministrado aos alunos do 1º ano do ensino básico. Os exemplos para este nível etário devem ser deste grau de dificuldade.

Por outro lado este exemplo servirá também para explicitar melhor a terminologia que se usa e esclarecer a respectiva simbologia.

importante: Para todos os problemas, há que especificar não só o programa mas também o estado inicial da máquina. É evidente que quanto mais geral for o enunciado de um problema, mais difícil ele é de resolver e, em geral, maior é o seu número de instruções.

 

Exemplo 1:

A máquina começa do estado inicial vazio (todas as células vazias)

 

 

 

 

 

 

 

 

 

 

 

 

                                 n

1. V 2

2. => 3

3. => 1;

 

O que acontecerá com a fita?

De acordo com o que foi escrito antes, a primeira instrução marca a primeira célula (a que está a ser observada pelo carro no estado inicial) e de seguida salta-se para a 2ª instrução do programa;

esta diz-nos que devemos deslocar o carro para a direita e saltar para a instrução 3;

Por sua vez, a 3ª instrução manda-nos deslocar o carro para a direita e saltar para a instrução 1. Temos aqui um loop infinito. a primeira instrução manda-nos marcar a célula observada pelo carro e assim sucessivamente.

Naturalmente já sabemos a resposta à pergunta inicial e as crianças (mesmo as da primária) já teriam tido contacto com um dos instrumentos mais poderosos da programação (looping ou laço).

A resposta é: O programa origina uma marcação da fita em células alternadas, a partir da primeira, sendo que esta também é marcada.

 

 

V

 

V

 

V

 

V

 

 

                                                            n ...

 

Exemplo 2:

Estado inicial da figura

 

 

 

 

 

 

V

 

 

 

 

                                          n

 

1. V 4

2. x 3

3. <= 2

4. => 5

                4

5. ?

                3

 

Tente o leitor aplicar instrução a instrução e seguir os vários estados da máquina até ao final do programa.

No primeiro passo será marcada a célula observada pelo carro e o programa saltará para a instrução 4;

A instrução 4 manda deslocar o carro à direita e saltar para a instrução 5;

Esta diz para, caso a célula observada pelo carro esteja vazia, executar a instrução 4, caso esteja marcada, executar a instrução 3;

Como, nesta altura, a célula está vazia, saltamos para a instrução 4;

Esta manda-nos deslocar o carro mais uma casa para a direita e saltar novamente para a instrução 5;

A mesma análise tem de ser feita, mas agora, como o carro já está diante de uma célula marcada, o programa salta para a instrução 3;

Nesta instrução somos convidados a deslocar o carro uma casa para a esquerda e saltar para a instrução 2;

A instrução 2 manda apagar a célula que está diante do carro, mas como esta não está marcada, a operação não pode ser realizada e, sempre que isso acontece, dizemos que ocorreu uma paragem sem resultado.

 

Exemplo 3:

Como já exemplificámos um programa em que a máquina transcorre infinitamente (ex:1) e outro em que chegámos a uma paragem sem resultado (ex:2) vamos agora ver um caso em que se verifica o outro tipo de resultado possível para um programa a correr numa máquina de Post: a paragem com resultado.

Para isso vamos ao clássico problema da adição de uma unidade a um número.

 

 

Programas para a máquina de Post:

 

1. Soma de uma unidade a um número

 

Neste, tal como em qualquer programa destinado a resolver um problema, existem várias soluções.

Desde logo, caso as condições iniciais sejam diferentes. Neste aspecto há que sublinhar o facto que “quanto mais geral é uma solução mais difícil se torna a elaboração do programa respectivo e, em geral, maior é o número de instruções necessário.

Para ilustrar tal facto, sabendo-se que existem uma série de condições iniciais e, mais genericamente, de enunciados para o problema, vamos ater-nos, no presente artigo, entre 2 desses enunciados: um muito específico e um muito geral. Entre os dois existem uma variedade deles, alguns dos quais podem ser consultados no livro que serviu de base ao presente artigo.

 

Versão 1 – Caso mais simples - enunciado:

Escrever programa para, qualquer que seja o número n, registado na Máquina de Post (tendo esta o resto da fita vazia), a execução do programa conduz a uma paragem com resultado, resultado esse que é o número n+1 (o resto da fita deve ficar vazio) numa zona arbitrária da máquina, podendo o carro ficar numa zona qualquer. O estado inicial da máquina é, precisamente, ter apenas o número n registado e o carro está em frente da célula mais à esquerda do registo desse número.

 

Resolução:

Pelo enunciado vemos que existem vários estados iniciais possíveis, embora a diferença entre todos eles seja apenas uma questão de deslocamento em relação ao sistema de coordenadas. Temos então, graficamente, por exemplo, o seguinte estado inicial:

De referir que, caso o estado inicial não esteja dentro daqueles indicados pelo enunciado, nada é dito sobre o funcionamento pretendido para a máquina.

 

 

 

-5

-4

-3

-2

-1

0

1

2

3

4

5

6

7

8

9

10

 

 

 

 

 

 

 

 

 

 

 

 

 

V

V

V

 

 

 

 

                                                              n

 

 

Uma solução possível é:

1. <= 2

2. V 3

3. stop.

 

Como, geralmente, em todos os problemas de programação, existem muitos mais programas que são solução do problema. No entanto, também em geral, a maioria dessas soluções utilizam mais (ou muito mais) instruções. Uma das preocupações de todos os programadores é, para além de encontrar a solução do problema, essa solução seja eficiente em termos de utilização de recursos (nomeadamente utilização de memória, que convém ser o menor possível, e de rapidez de execução, o que diminui o tempo de processador necessário). Normalmente, quanto mais curto for o programa maior é a sua eficiência.

Como vemos, pela solução apresentada, o problema, posto do modo que foi, é de resolução muito simples. Isso tem muito a ver com as condições iniciais, muito limitativas, dadas. Afinal, se o carro está na extremidade esquerda do registo do número, basta deslocá-lo uma casa para a esquerda, marcar essa célula e parar.

 

Vamos ver agora que se não pusermos tantas condições, isto é, se o enunciado não for tão limitativo, a dificuldade aumente. Como dissemos antes, vamos passar de um enunciado muito específico para um enunciado muito geral. Entre os dois casos existem diversos outros.

 

Versão 2 – Caso Mais Geral (e mais difícil)

Agora não vamos impor qualquer limitação à disposição mútua do carro e do registo na máquina do número n no estado inicial. Devem ter notado que o programa anterior só funciona caso o carro, no estado inicial, esteja em frente da célula mais à esquerda do registo do número inicial.

Agora não vamos exigir que isso aconteça, isto é, o carro, no estado inicial, pode estar em qualquer lado e, no final pode, também ficar em frente de qualquer célula.

Enunciado:

Escrever um programa para a Máquina de Post que para qualquer n, sendo aplicado a um estado arbitrário En, leve a uma paragem com resultado num dos estados com a classe En+1.

A classe En corresponde a todos os estados em que o número n está registado na fita.

 

Resolução:

Não esquecer que o carro, no estado inicial, pode estar em frente de uma das células marcadas que formam o número inicial, em frente a uma célula vazia, à esquerda ou à direita desse registo.

Uma solução será a apresentada abaixo

 

Vemos bem a complexidade que a resolução do problema, e o respectivo programa, tomou.

Aconselha-se o leitor a implementar este programa para ver que funciona. Chama-se a isso análise de um programa, primeira parte necessária para a formação de um programador. Quando todos os mecanismos de análise de programas estiver bem consolidado poder-se-à então abalançar para a parte mais difícil mas, ao fim e ao cabo, a razão de ser de um programador: a síntese de programas, isto é, a elaboração de programas que resolvam problemas concretos, melhor ou pior enunciados.


 

                2

1. ?

                3

 

2. <= 4

 

3. => 4

 

                5

4. ?

                3

 

5. V 6

 

6. <= 7

 

                8

7. ?

                15

 

8. => 9

 

 

                10

9. ?

                8

 

10. V 11

 

11. => 12

 

                13

12. ?

                19

 

13. <= 14

 

                15

14. ?

                13

 

15. => 16

 

16. => 17

 

                23

17. ?

                18

 

18. x 16

 

19. <= 20

 

20. <= 21

 

                23

21. ?

                22

 

22. x 20

 

23. stop.

 


 

Aconselhamos o leitor a implementar a sua máquina de Post e experimentar o seu funcionamento com este programa, com várias condições iniciais.

Verificará da “bondade” do programa e interiorizará muitos dos aspectos do funcionamento da Máquina de Post, bem assim com da análise de programas.

 

A UNIVERSALIDADE DA MÁQUINA DE POST

 

O Programa Universal não pode ser confundido com o programa particular que visa a resolução de um ou outro problema concreto e se modifica segundo os dados iniciais. O programa particular depende do problema a ser resolvido, enquanto o Programa Universal é um só para todos os problemas.

 

Nos computadores modernos ele é uma parte integrante da própria estrutura da máquina. Daí essas máquinas serem frequentemente chamadas de Universais. 

 

Esclarecendo: nos computadores os dados iniciais ( e aqui, ao contrário do que acontece na máquina de Post, dados e programa só podem ser distinguidos no início, sendo que o próprio programa pode ser alterado no decorrer do funcionamento do computador ao correr esse programa, precisamente pelo Programa Universal) são armazenados na memória do computador. Posteriormente, o funcionamento segue o Programa Universal materializado na estrutura da máquina.

 

A Máquina de Post pode ser classificada como uma Máquina Universal simplificada, pois também é possível elaborar um Programa Universal para a Máquina de Post, mais precisamente, é possível codificar cada programa para a Máquina de Post em símbolos de Post e, posteriormente, instalar o registo deste programa (ou seja, o registo dos símbolos respectivos) na fita, ao lado do registo do dado inicial, ao qual o programa deve ser aplicado. É possível, depois, elaborar um programa - o Programa Universal – que, ao ser aplicado ao registo composto pelo registo de um certo programa P e pelo registo de um certo dado inicial x, conduza ao mesmo resultado que a aplicação directa de P ao registo de x. Neste caso, porém, o Programa Universal é apenas um dos programas possíveis da Máquina de Post; já no caso dos computadores o Programa Universal não é de modo algum um dos programas particulares aceitáveis para o computador, mas sim um programa materializado pela própria estrutura do computador.

 

DESAFIOS AO LEITOR

 

Nesta secção proporemos alguns problemas ao leitor, que deverá encontrar o (ou os) algoritmo que encontre a solução, consubstanciado numa série de instruções para a Máquina de Post, constituindo um programa.

As vossas respostas serão aqui publicadas, devidamente identificadas, se assim o entenderem.

 

Para além disso solicitamos também que nos enviem os vossos desafios que, igualmente, serão aqui publicados, à procura de resposta.

 

Sendo esta uma página virada para a didáctica e dirigida mais para um público com formação secundária, a maioria dos problemas aqui propostos serão específicos. Isso não impede, no entanto, que, que o pretender, coloque problemas gerais.

 

Esta diferença entre problemas gerais e específicos não foi aprofundada no presente artigo, por motivos de não sobrecarga do mesmo, mas penso que todos perceberão a diferença a partir dos exemplos apresentados anteriormente para o caso da soma de uma unidade a um número n : o 1º exemplo era um problema específico e o segundo, um geral.

 

1. Pretende-se encontrar um programa que multiplique o número 2 (previamente marcado na fita, em 2 células seguidas, como habitual) por 2, sendo que o carro, no estado inicial deve estar situado frente à célula mais à esquerda das que constituem o número original.

 

2. Igual ao 1. mas em que o carro, no estado inicial, encontra-se numa posição aleatória.

 

3. Programa que multiplique qualquer número n (previamente marcado na fita, em n células seguidas, como habitual) por 2, sendo que o carro, no estado inicial deve estar situado frente à célula mais à esquerda das que constituem o número original.

 

 

BIBLIOGRAFIA PARA APROFUNDAMENTO DO TEMA (em Português)

 

·         “A Máquina de Post”, V. Uspensky, Editora Mir Moscovo, 1979. Edição Portuguesa de 1985.

 

·         O site da Universidade Federal do Rio Grande do Sul - Brasil possui um livro on-line adoptado na cadeira de “Teoria de Computação” daquela escola, no qual é desenvolvida teoria referente à Máquina de Post (e também à Máquina de Turing), num capítulo intitulado “Máquinas Universais”. Esse capítulo pode ser acedido em http://www.inf.ufrgs.br/~hgmcpad/disciplinas/teoriadacomputacao/capitulo3/cap3_51.doc  , sendo que todo o resto do livro também pode ser acedido e descarregado.

 

O site proporciona ainda uma colecção de exercícios sobres as várias partes da cadeira.

 

Existe também um conjunto de simuladores em software, um dos quais simula o funcionamento da Máquina de Post através da execução de programas que o utilizador pode desenvolver (tem 3 exemplos de programa já elaborados). Vale a pena o download em http://www.inf.ufrgs.br/~hgmc/site/programa/tc/tcsim.html

 

Para aqueles que pretenderem conhecer a Máquina de Turing existem também simuladores e programas disponíveis para download.

 

PROCESSOS COMBINATÓRIOS FINITOS – Formulação 1

 

Emil L. Post

 

A presente formulação pode ser significativa para o desenvolvimento da lógica simbólica no sentido fixado pelo teorema de Gödel sobre incompleteza das lógicas simbólicas e pelo resultado de Church a respeito dos problemas absolutamente insolúveis.

Referimo-nos ao problema geral constituído por uma classe de problemas específicos. A solução do problema geral será aquela que forneça resposta a cada problema específico.

Na formulação que se segue de tal solução, dois conceitos são envolvidos: o conceito de espaço de símbolos em que se deve realizar um trabalho que conduza do problema para a resposta, e o de série de instruções, inalterável e fixa, que deverá tanto dirigir as operações no espaço dos símbolos como determinar a ordem de aplicação das instruções.

Na presente formulação o espaço de símbolos consta de duas sequências infinitas, em ambos os lados, de lugares ou caixas, ou seja, semelhante a uma série de inteiros... –3, -2, -1, 0, 1, 2, 3, ... A pessoa que vai resolver este problema, ou trabalhar com este espaço de símbolos, pode operar a cada instante numa só caixa. Quer esteja ou não presente o trabalhador, a caixa pode estar somente em duas condições possíveis: estar vazia, não marcada, ou ter uma simples marca, podendo ser, digamos, um traço vertical.

Uma das caixas deve estar evidenciada, e é chamada ponto inicial (de partida). Daqui para a frente consideraremos que um problema específico é dado sob forma simbólica por um número finito de caixas marcadas com uma linha. assim, também a resposta deve ser dada em forma simbólica por uma qualquer configuração de caixas marcadas. Duma forma mais específica, a resposta deve ser a configuração de caixas marcadas que fica depois de concluída a solução do problema.

Supões-se que o trabalhador é capaz de efectuar as seguintes operações primitivas:

a) Marcar a caixa em que está (se esta estiver vazia);

b) Apagar a marca na caixa em que está (estando ela marcada);

c) Deslocar-se para a caixa da direita;

d) Deslocar-se para a caixa da esquerda;

e) Determinar se está marcada ou não a caixa em que se encontra.

 

A série de instruções que, deve notar-se, é a mesma para todos os problemas específicos, e portanto corresponde ao problema geral, deve ter a seguinte forma. Começa assim:

Parta do ponto inicial e siga a instrução 1.

Em seguida vem um número finito de instruções numeradas por 1, 2, 3, ..., n. A i-ésima instrução então deverá ter uma das seguintes formas:

(A) efectue a operação Oi [Oi = (a), (b), (c), ou (d)] e depois siga para a instrução ji ,

(B) efectue a operação (e) e, consoante a resposta for sim ou não, siga para a instrução ji´  ou  ji´´ , respectivamente,

(C) pare.

 

Obviamente, é necessária apenas uma instrução do tipo C. Note-se também que o estado do espaço de símbolos só afecta directamente o processo através das instruções do tipo B.

Consideraremos aplicável uma série de instruções a um dado problema geral desde que na sua aplicação a cada problema específico nunca seja necessária a operação (a) quando a caixa em que se encontrar o operador estiver marcada, ou a operação (b) se esta não estiver marcada. A série de instruções aplicável ao problema geral estabelece um processo determinado quando aplicado a cada problema específico. Este processo quando e somente quando chegar à instrução do tipo (C). Diz-se então que a série de instruções estabelece um processo-l finito em conexão com o problema geral, se ela for aplicável ao problema e se o processo que ela define terminar para cada problema. Um processo-l finito associado ao problema geral será designado por uma l-solução do problema se a resposta por ele dada a cada problema específico for sempre correcta.

Não queremos saber aqui como é que a configuração de caixas marcadas corresponde a um problema específico e à sua resposta simbolizam o problema e a resposta idealizados. De facto, acima supõe-se que o problema específico é dado sob a forma simbólica por um agente externo e, presume-se, que a resposta simbólica é recebida do mesmo modo. Um desenvolvimento mais autónomo é feito da seguinte maneira. O problema geral consiste evidentemente não menos que um conjunto enumerável infinito de problemas específicos. Não precisamos de considerar o caso finito. Imaginemos então que uma correspondência biunívoca foi estabelecida entre a classe dos inteiros positivos e a classe dos problemas específicos. Podemos, com grande arbitrariedade, representar o inteiro positivo n marcando as primeiras n caixas à direita do ponto de partida. O problema geral dir-se-à l-dado, se for estabelecido um l-processo finito tal que, quando aplicado à classe dos inteiros positivos representados simbolicamente, permita obter de forma biunívoca a classe dos problemas específicos que constituem o problema geral. É conveniente convencionar também que quando o problema geral é l-dado como foi indicado, no fim de cada proceso específico o trabalhador encontra-se no ponto de partida. Se um problema geral for agora l-dado e l-resolvido, podemos, com algumas mudanças óbvias, combinar as duas séries de instruções e obter um l-processo finito que dá a resposta a cada problema específico, quando o último for dado simplesmente pelo seu número em forma simbólica.

Com algumas modificações a formulação exposta é também aplicável às lógicas simbólicas. Neste caso não temos uma classe de problemas específicos; mas sim uma marcação singular inicial finita do espaço de símbolos para simbolizar as asserções formais primitivas da lógica. Por outro lado, neste caso não teremos instruções do tipo (C). Consequentemente, pressupondo a aplicabilidade, estabelece-se um processo determinado o qual é infinito. Em seguida, convencionaremos que no decorrer do processo certos grupos de símbolos reconhecíveis, ou seja, sequências finitas de caixas marcadas e não marcadas, aparecerão e não se alterarão mais durante o processo. Eles serão asserções derivadas da lógica. Naturalmente, a série de instruções corresponde aos processos dedutivos da lógica. Neste caso a lógica pode ser chamada l-gerada.

Um procedimento alternativo, menos em harmonia, contudo, com o espírito da lógica simbólica, poderia consistir na indicação de um l-processo finito que daria o –n-ésimo teorema ou a n-ésima asserção formal da lógica dada n, também simbolizado como acima.

O nosso conceito inicial de problema específico envolve uma dificuldade que deve ser mencionada. A saber, se um agente exterior dá a distribuição inicial de marcas no espaço de símbolos, não temos como determinar, por exemplo, qual é a primeira caixa marcada e qual a última. Esta dificuldade é completamente eliminada quando o problema geral é l-dado. Ela é também eliminada com êxito sempre que o l-processo finito for indicado. Na prática os problemas específicos estudados poderia ser simbolizados de tal forma que os limites de tal simbolização se tornassem reconhecíveis por meio dos grupos característicos de caixas marcadas e não marcadas.

Talvez a raiz da nossa dificuldade esteja, contudo, na nossa concepção dum espaço de símbolos infinito. Na presente formulação as caixas são, conceptualmente, pelo menos, entidades físicas, como por exemplo, casas contíguas. O nosso agente externo tanto poderia dar-nos um número infinito de caixas, como marcar um número infinito daquelas que se supõe dadas. Se, porém, ele nos apresentar um problema específico sob a forma de uma porção finita de tal espaço de símbolos, a dificuldade desaparece. Naturalmente, isto exigiria uma extensão das operações primitivas de modo a permitir a ampliação necessária do espaço de símbolos inicial à medida que o processo se desenvolvesse. A versão final de uma formulação do presente tipo deveria também indicar as instruções de geração do espaço de símbolos.

O autor espera que a presente formulação venha a ser logicamente equivalente à recorrência (recursiveness) no sentido do desenvolvimento de Gödel-Church. Ele propõe, contudo, não somente apresentar um sistema de uma certa potência lógica, mas também, no seu campo restrito, de fidelidade psicológica. Neste último sentido são contempladas formulações cada vez mais amplas. Por outro lado, o nosso intuito é o de mostrar que todas elas são logicamente redutíveis à formulação 1. Nós propomos esta conclusão no presente momento como uma hipótese de trabalho. Ao nosso ver tal é a identificação que Church estabelece entre a calculabilidade efectiva e a recorrência (recursiveness). A partir desta hipótese, e devido à sua aparente contradição com todo o desenvolvimento matemático, a começar pela demonstração de Cantor da não-enumerabilidade dos pontos duma linha, independentemente decorre um desenvolvimento de Gödel-Church. O sucesso do programa acima exposto seria, para nós, uma transformação desta hipótese não num axioma ou numa definição, mas numa lei natural. Só assim, na opinião do autor, o teorema de Gödel sobre a não plenitude (incompleteza) das lógicas simbólicas de um certo tipo geral e os resultados de Church sobre a insolubilidade recursiva de certos problemas podem ser transformados em conclusões relativas às lógicas simbólicas e a todos os métodos de solução.

Colégio da cidade de Nova Iorque

 

NOTAS FINAIS:

 

1 – O conceito de algoritmo, a razão principal da escrita deste artigo, não chegou a ser definido. Pensamos que mais importante que essa definição (e existem inúmeras), será a sua compreensão e interiorização. Pensamos que com a leitura do artigo e execução dos seus exercícios e exemplos, o conceito de algoritmo fica mais do que claro na mente do leitor. Para os educandos, nas mesmas condições, será muito fácil de o entender logo que chamados à atenção para tal.

 

2- Muitos conceitos de programação, que também podem ser postos em evidência pelo trabalho com a Máquina de Post, não foram focados, alguns nem de forma implícita. Referimo-nos a Programação Sequencial, Saltos Condicionais, Loops, Chamadas a Rotinas, Recursividade, etc.

A sua explicitação ficará para uma segunda oportunidade, convidando-se, no entanto, o leitor, desde já, a dar a sua colaboração, se assim o desejar.

 

3 - Veja aqui e/ou descarregue a versão em Word (onde foi escrito originalmente este artigo)