Dsadsdas Dasdsadsa Dasdsad

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”.

...