Projeto de máquina de Turing com múltiplas

fitas reconhecedora de número primo CCO 410 – Aspectos Formais da Computação | Prof.º Wanderley Lopes de Souza

Universidade Federal de São Carlos | Diego Luiz Cavalca – RA 11414693

INTRODUÇÃO

Este trabalho visa construir um projeto de máquina de Turing (MT) que, dado um número

inteiro maior que 2 em representação binária, delimitado pelos símbolos ¢ e $, reconheça se este

pertence à classe de números primos.

Segundo Peruzzo (2012), número primo é todo número maior do que 1 é divisível somente

por si mesmo e por 1. Alguns exemplos são os números 2, que tem apenas os divisores 1 e 2, e 17

que possui apenas os divisores 1 e 17, portanto sendo estes números primos.

Conforme demonstrado por Stewart (), existem diversas provas Um dos processos de

reconhecimento de um número ser primo consiste em dividir esse número pelos números primos 2,

3, 5, 7, 11 etc. até que se obtenha ou uma divisão com resto zero – e neste caso o número não é

primo – ou uma divisão com quociente menor que o divisor e o resto diferente de zero; neste caso o

número é primo.

Assim, fica fácil identificar o comportamento de computação contínua até atingir um

resultado pré-determinado. Portanto, tal processo pode ser simulado através da máquina de Turing.

A máquina de Turing (MT) é um poderoso - porém simples - modelo matemático que possui

capacidade de solucionar determinados problemas de reconhecimento de palavras de uma

linguagem e também computação de funções de inteiros.

Hopcroft et. al (2002), ao definir MT, afirma que este dispositivo matemático é, em sua

essência, um autômato finito que utiliza uma estrutura de fita de comprimento infinito com

capacidade de leitura e gravação de dados.

Formalmente, essa máquina consiste em um controle finito, que pode se encontrar em um

estado qualquer de um conjunto finito de estados. Como citado, a memória auxiliar se baseia em

uma fita dividida em quadrados, ou células, nos quais podem conter qualquer símbolo de um

alfabeto pré-definido contendo um número finito de símbolos.

Pode-se visualizar uma máquina de Turing como na figura abaixo:

Figura 1: Uma máquina de Turing

. . . . . .

DESENVOLVIMENTO

Para resolver o problema proposto neste trabalho, o seguinte algoritmo é projetado, definindo o

comportamento da MT nesta tarefa:

1. Inicialmente a MT lê na 1ª fita um número (N)2 > (2)10, delimitado pelos símbolos ¢ e $.

2. Escrever o divisor (2)10 = (10)2 na 2ª fita;

3. Repetir o número da 1ª fita na 3ª fita;

4. Subtrair tantas vezes quanto possível o número da 2ª fita do número da 3ª fita, guardando os

resultados intermediários nesta última;

a. Se o resultado na 3ª fita for igual a 0:

i. Se o número da 1ª fita = número da 2ª fita, então a entrada representa um

número primo;

ii. Senão, o número original não é primo;

b. Senão:

i. Incrementar o divisor e retornar para o processo (2).

Logo, com base no algoritmo definido e nas regras fundamentais da máquina de Turing com

múltiplas fitas, o projeto em questão pode ser desenvolvido, modelando os seguintes componentes:

1. Inicialmente a fita 1 contém ¢N$, onde N é a representação binária do número no qual a MT

irá verificar se é primo ou não.

Exemplos de entradas válidas: ¢10$, ¢101$, ¢110$, ¢111$, etc.

2. O passo base para a verificação se um número é primo - ou não - consiste em dividi-lo por 2,

uma vez que apenas um número par é primo (no caso, o número 2).

a. Uma vez que estamos trabalhando com sistema binário, inicialmente iremos

representar o divisor (2)10, sendo (10)2, na segunda fita.

Como o controle está posicionado na extremidade esquerda das fitas, é necessário

movê-lo para o último dígito de N, a fim de que o divisor fique alinhado a este,

permitindo manipular as operações posteriores. Sendo assim, esse comportamento

inicial pode ser definido através das movimentações.

(q0, (a, B, B)) = (q0, (a, B, B), D), onde a = {¢, 0, 1}

(q0, ($, B, B)) = (q1, ($,B,B), $)

b. Com o controle posicionado, a MT escreve o divisor (10)2 na segunda fita, através das

movimentações:

(q1, (a, B, B)) = (q2, (a, 0, B), E), onde a = {0, 1};

(q2, (a, B, B)) = (q3, (a, 1, B), E), onde a = {0, 1};

Neste momento, após gravar o divisor na segunda fita, a MT move o controle para o

início do número N, a fim de iniciar o próximo processo:

(q3, (a, B, B)) = (q3, (a, B, B), E), onde a = {0, 1}

(q3, (¢, B, B)) = (qCopyN, (¢, B, B), D), onde a = {¢, 0, 1}

3. Como anteriormente mencionado, a ideia central da validação de um número N ser primo

consiste em realizar a verificação do divisor deste, já que para se classificar como tal, este

número deve ser divisível apenas por 1 e pelo próprio valor de N. Assim, a MT utilizará uma

terceira fita, que será responsável por realizar essa verificação a partir do número N.

a. Primeiro, a MT irá repetir o número da primeira trilha (N) na terceira trilha. Este

processo será modelado através das movimentações a seguir:

(qCopyN, (0, a, b)) = (qCopyN, (0, a, 0), D), onde a = {0, 1, B}

(qCopyN, (1, a, b)) = (qCopyN, (1, a, 1), D), onde a = {0, 1, B}

(qCopyN, ($, B, B)) = (qSub, ($, B, B), E);

4. O resultado da operação de divisão de um número M (dividendo) por um outro número N

(divisor) consiste na quantidade de vezes que N cabe em M. Com base neste princípio, a MT

irá simular esta operação, onde irá subtrair tantas vezes quanto possível o número presente na

segunda trilha (divisor) do número na terceira trilha (dividendo). Tal operação na MT se faz

através das movimentações:

Assumindo a e b = {0, 1 },

a. Seguindo as regras da subtração de números binários,

b – vazio = b, b – 0 = b e 1 – 1 = 0:

(qSub, (a, B, b)) = (qSub, (a, B, b), E);

(qSub, (a, 0, b)) = (qSub, (a, 0, b), E);

(qSub, (a, 1, 1)) = (qSub, (a, 1, 0), E);

b. 0 – 1 = 1, emprestando 1 do dígito à esquerda:

(qSub, (a, 1, 0)) = (qSubEx, (a, 1, 1), E);

i. Uma vez que houve esse “empréstimo”, é necessário compensar no dígito à

esquerda, acrescendo o dígito 1 (quando dígito da 3ª fita = 2ª fita) ou o dígito

0 (quando dígito da 3ª fita > ou < que o dígito da 2º fita):

(qSubEx, (a, 0, 0)) = (qSubEx, (a, 0, 1), E);

(qSubEx, (a, B, 0)) = (qSubEx, (a, B, 1), E);

(qSubEx, (a, 1, 1)) = (qSubEx, (a, 1, 1), E);

(qSubEx, (a, 1, 0)) = (qSubEx, (a, 1, 0), E);

(qSubEx, (a, 0, 1)) = (qSub, (a, 0, 0), E);

(qSubEx, (a, B, 1)) = (qSub, (a, B, 0), E);

c. Ao subtrair o último dígito à esquerda da 3ª trilha, MT posiciona o controle no início

de N para iniciar o próximo processo:

(qSub, (¢, B, B)) = (qCompare, (¢, B, B), D);

Em tempo, vale salientar que esta é uma operação fundamental no processo de

validação de um número primo, condicionado ao resto resultante do dividendo, como

abordaremos em um comportamento adiante.

5. Após realizar uma subtração entre o dígito da 2ª fita e o da 3ª fita, é necessário verificar se há

mais uma subtração possível, ou seja, é necessário verificar se o dígito da 3ª é maior ou igual

ao da 2ª:

Assumindo a = {0, 1},

(qCompare, (a, b, 0)) = (qCompare, (a, b, 0), D), onde b = {0, B}

(qCompare, (a, 1, 1)) = (qCompare, (a, 1, 1), D), onde b = {0, B}

(qCompare, (a, b, 1)) = (q3greater, (a, b, 1), D), onde b = {0, B}

(q3greater, (a, b, c)) = (q3greater, (a, b, c), D), onde b = {0, 1, B} e c = {0, 1}

Ao se atingir o final das fitas, a MT posiciona o controle no dígito mais à direita (último) das

3ª e 2ª fita e realiza a subtração entre ambas novamente (processo 4):

(qCompare, ($, B, B)) = (qSub, (a, b, c), E);

(q3greater, ($, B, B)) = (qSub, (a, b, c), E);

6. Em outro caso, outra validação importante é verificar se o dígito presente na 2ª fita é maior

que o presente na 3ª, pois neste caso, não há mais subtração possível e a MT pode avançar

para outro processo:

Assumindo a = {0, 1},

(qCompare, (a, B, 0)) = (qCompare, (a, B, 0), D);

(qCompare, (a, 1, 0)) = (q2greater, (a, 1, 0), D);

Caso a MT verifique esta hipótese, o controle retorna para o dígito mais à esquerda destas

fitas para realizar outra validação (processo 7):

(q2greater, (a, b, c)) = (q2greater, (a, b, c), E), onde a = c = {0, 1} e b = {0, 1, B}

(q2greater, (¢, B, B)) = (qEqual0, (¢, B, B), D);

7. Um processo importante desta MT é verificar, após a sucessiva aplicação de subtrações do

dígito da 2ª fita na 3ª fita, se o este último é igual ou diferente de 0, pois este resultado indica

como a máquina deve evoluir no processo de validação de N:

a. Validando se o dígito da 3ª fita é igual a 0:

(qEqual0, (a, b, 0)) = (qEqual0, (a, b, c), D), onde a = {0, 1} e b = {0, 1, B}

(qEqual0, ($, B, B)) = (qValidatePrime, ($, B, B), E);

b. Validando se este dígito é diferente de 0:

(qEqual0, (a, b, 1)) = (qDiff0, (a, b, 1), D), onde a = {0, 1} e b = {0, 1, B}

(qDiff0, (a, b, c)) = (qDiff0, (a, b, c), D), onde a = c = {0, 1} e b = {0, 1, B}

(qDiff0, ($, B, B)) = (qInc, ($, B, B), E);

8. Uma vez que o valor expresso na 3ª fita for diferente de 0, a MT incrementa o divisor na 2ª

fita e volta para o processo 3 (cópia do dígito da 1ª trilha, representada por N, na terceira fita),

a fim de tentar obter um divisor que resulte em resto 0 para a divisão, assim habilitando a MT

a validar se N é primo ou não (próximo processo):

Assumindo a = c = {0, 1},

(qInc, (a, 0, b)) = (qIncAux, (a, 1, b), E), onde b = {0, 1};

(qInc, (a, 1, b)) = (qIncEx, (a, 0, b), E), onde b = {0, 1};

(qIncEx, (a, 0, b)) = (qIncAux, (a, 1, b), E), onde b = {0, 1};

(qIncEx, (a, 1, b)) = (qIncEx, (a, 0, b), E), onde b = {0, 1};

(qIncEx, (a, B, b)) = (qIncAux, (a, 1, b), E), onde b = {0, 1};

(qIncAux, (a, b, c)) = (qIncAux, (a, 0, b), E), onde b = {0, 1, B};

(qIncAux, (¢, B, B)) = (qCopyN, (¢, B, B), D);

9. A ideia central desta MT é responder a pergunta “O número N é primo?”. Para isto, a MT

para em um estado aceitável (ϵ F) caso valide que o número N é primo, onde esta validação

consiste em comparar o dígito N da primeira trilha com o dígito presente na 2ª trilha,

evidenciando assim que existe apenas 1 divisor, além do número um, para N. Esse processo

pode ser modelado na MT através das seguintes movimentações:

Assumindo a = {0, 1},

(qValidatePrime, (0, 0, a)) = (qValidatePrime, (0, 0, a), E);

(qValidatePrime, (1, 1, a)) = (qValidatePrime, (1, 1, a), E);

(qValidatePrime, (¢, B, B)) = (qIsPrime, (¢, B, B), D);

Desta maneira, com base neste projeto e suas componentes movimentações matematicamente

definidas, a MT resultante pode ser definida formalmente da seguinte maneira:

MT = (Q, Σ, Γ, δ, q0, B, F), onde

Q = {q0, q1, q2, q3, q4, qCopyN, qSub, qSubEx, qCompare, q2greater, q3greater, qEqual0, qDiff0,

qInc, qIncEx, qIncAux, qValidatePrime, qIsPrime}

Σ = {0, 1}

Γ = {0, 1, B}

δ conforme definido no projeto

q0 ϵ Q é o estado inicial

B ϵ Γ é o símbolo branco

F = {qIsPrime}

RESULTADO

O projeto de MT deste trabalho foi implementado no simulador online Turing Machine

Simulator1 a fim de validar a corretude do algoritmo proposto e o comportamento resultante da

máquina em questão.

Uma vez desenvolvida e compilada, seguindo as orientações do simulador, a MT foi

submetida para reconhecer o número (3)10 (entrada C11$), afirmando que o número é primo após 39

passos (movimentações do controle sobre as fitas). Já para o número (5)10 (C101$), a MT confirmou

que este é primo após 103 passos, e 439 passos para reconhecer o número (13)10 (C1101$) como

primo, atingindo o estado qIsPrime. Em contrapartida, após 39 passos a máquina não evolui sua

execução durante o reconhecimento do número (4)10 (C100$) e também para após 85 passos quando

recebe o número (12)10 (C1100$), não validando estes números como primos.

Portanto, o projeto da MT com múltiplas fitas se mostra eficiente para o objetivo de

reconhecimento de um número primo em representação binária, validando com precisão quando este

pertence a esta classe numérica, atingindo um estado final, ou não, parando sua execução

repentinamente.

1 Disponível para acesso em www.turingmachinesimulator.com/shared/mdmzhdavdq

REFERÊNCIAS

PERUZZO, Jucimar. O Fascínio dos Números Primos. Irani (SC): Jucimar Peruzzo, 2012.

STEWART, Ian. Os Maiores Problemas Matemáticos Em Todos Os Tempos; tradução da 1.ed.

original de George Schlesinger. Rio de Janeiro: Editora Zahar, 2014.

HOPCROFT, John E.; ULLMAN, Jeffrey D.; MOTWANI, Rajeev. Introdução à Teoria de

Autômatos, Linguages e Computação; tradução da 2.ed. original de Vandenberg D. de Souza. Rio

de Janeiro: Elsevier, 2002.