Exercicios2

Prévia do material em texto

Universidade Federal de Lavras 
Departamento de Ciência da Computação 
2
o
 semestre de 2011 
 
 
GCC108 – Teoria da Computação 
Professor Responsável: Leonardo Andrade Ribeiro 
 
 
Avaliação: Exercícios 2 
Data: 20.10.2011 
Aluno:_________________________________Matrícula:_____________ Nota:____ 
Aluno:_________________________________Matrícula:_____________ Nota:____ 
Aluno:_________________________________Matrícula:_____________ Nota:____ 
Aluno:_________________________________Matrícula:_____________ Nota:____ 
 
 
 
 
1) Construa uma Máquina de Turing Numérica (MTN) que compute a função 
 ( ) ⌊ ⌋, onde ⌊ ⌋ é o menor inteiro menor ou igual a ? 
 
 
 
2) Considere o seguinte repertório de macros : 
MDk – move a cabeça le k números naturais à direita. A macro termina com a 
cabeça le posicionada sobre o símbolo branco imediatamente posterior ao kth 
número natural à direita da posição atual. 
MEk – move a cabeça le k números naturais à esquerda. A macro termina com a 
cabeça le posicionada sobre o símbolo branco imediatamente anterior ao kth 
número natural à esquerda da posição atual. 
ED – Posiciona a cabeça le sobre símbolo branco imediatamente anterior ao 
primeiro natural à direita da posição atual. 
EE – Posiciona a cabeça le sobre símbolo branco imediatamente anterior ao 
primeiro natural à esquerda da posição atual. 
Ak – Apaga k números naturas à direita da posição atual cabeça le. A macro 
termina com a cabeça le na posição original. 
CPk – Copia k números naturais para as posições iniciando-se imediatamente à 
direita do último número a ser copiado e termina com a cabeça le na posição 
original. 
CPk,i – Copia k números naturais para as posições iniciando-se i números naturais à 
direita do último número a ser copiado e termina com a cabeça le na posição 
original. 
T – Move o primeiro número natural à direita da cabeça le para a posição 
imediatamente à direita da mesma; termina com a cabeça le na posição original. 
ADD – Soma os dois números naturais à direita da cabeça le. A macro termina 
com a cabeça le na posição original e o resultado da soma escrito na posição 
imediatamente à direita da mesma. 
 
Usando R, construa máquinas para computar: 
a) ( ) 
b) ( ) 
 
 
 
 
3) Considere a macro MULT acima que computa a multiplicação de dois números 
naturais. Baseando-se em MULT, mas sem usar a mesma, construa uma macro que 
compute ( ) . 
 
 
4) Considere uma função definida pela seguinte composição funcional: 
 ( 
( ) ( 
( ) 
( ))) 
Calcule o valor de ( ) apresentando as etapas intermediárias da calculação. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
5) Seja ( ) e ( ) e seja ( ) a função definida por e 
via recursão primitiva. Calcule o valor de ( ) apresentando as etapas 
intermediárias da calculação. 
 
 
 
 
 
 
 
 
 
 
6) Seja ( ) uma função recursiva primitiva. Mostre que a função também é 
recusiva primitiva: 
 ( ) ( ) 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
7) Usando apenas as funções básicas, composição e recursão primitiva (para recursão 
primitiva, apresente as funções e ), mostre que ( ) é recursiva 
primitiva. 
 
Tabela 1 
Descrição Função Definição 
adição ( ) 
x+y 
 ( ) 
 ( ) ( ) 
multiplicação mult( ) 
x*y 
mult( ) 
 ( ) ( ) 
predecessor pred(y) pred(0) 
pred(y+1) = y 
sub sub(x,y) sub(x,0)=0 
sub(x,y+1)=pred(sub(x,y)) 
sinal sg(y) (0) = 0 
 (y+1) = 1 
sinal comp. cosg(y) (0) = 1 
 (y+1) = 0 
par par(y) 
 
par(0) = 1 
par(y+1) = cosg(par(y)) 
less than lt(x,y) sg(sub(y,x)) 
greater than gt(x,y) sg(sub(x,y)) 
equal to eq(x,y) ( ( ) ( )) 
 
 
 
 
 
 
8) Seja e funções recursivas primitivas. Mostre que função abaixo é recursiva 
primitiva (Voce pode usar qualquer função da Tabela1 e também qualquer 
operador limitado): 
 ( ) {
 ( ) ( ) 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
9) Descreva a seguinte função primitiva recursiva (pode usar uma descrição informal, 
desde que precisa): 
 ( ) 
 
 
[ ( ) ( 
 
 
[ ( )])]