Funções Recursivas Bird

1 Objetivos

Mostrar que a importância teórica dos conceitos de definições recursivas de Bird e

linguística é fundamental, pois eles forçam os alunos a exercitar uma forma de raciocínio,

por exemplo como resolver um problema dividindo as soluções em instâncias menores do

mesmo problema.

2 Introdução

O ser humano, segundo Chomsky, nasce com a capacidade de criar linguagem, que

não se restringe a um conjunto de frases, mas sim o propósito nelas contido. Chomsky afirma

que a gramática de uma língua é formada segundo regras, cujas aplicações produzem frases

com sentido. Com a Gramática Gerativa, pode-se, a partir de um conjunto limitado de

regras, gerar um número infinito de frases. Chomsky define a recursividade, a capacidade

de gerar uma variedade ilimitada de sentenças de qualquer comprimento,combinando

poucas regras da língua.

Como uma das coisas fundamentais que separam os homens dos animais, pode-se

citar a linguagem e a complexa capacidade de comunicação. Daniel Everett vai contra

a teoria supracitada, pois ele afirma que a tripo Pirarrã, encontrada na Amazônia, não

possui em sua linguística nada, a recursividade. O pesquisador diz que sua língua possui 8

consoantes, 3 vogais, diferentes tons e tamanhos de sílabas diferentes. Ele também fala que

os índios não são recursivos porque os pirarrãs só vivem e falam no tempo presente. Fazem

sentenças relacionadas ao momento em que estão falando e fatos vistos por eles. Em suas

sentenças, só contam situações vividas pelo narrador ou testemunhadas por alguém vivo

durante a vida do do mesmo.

A definição das Recursivas de Bird pode ser vista através de alguns exemplos que

mostram o seu potencial. Inicialmente, sabe-se que a Classe das funções com Definição

Recursiva é a mesma Classe das Funções Computáveis.

Considera-se a expressão:

(p ! e1, e2) (1)

onde informalmente e1 é a expressão, se p é verdadeiro e e2 é caso contrário.

Exemplo 1 - fatorial

Considerando a seguinte definição recursiva para uma função fatorial:

fatorial = x(x = 0 ! 1, x · fatorial(x − 1))

se considerarmos fatorial(0) = 1, teremos:

fatorial(0) = (0 = 0 ! 1, 0 · fatorial(0 − 1))

2

Pode-se observar que 0 · fatorial(0−1) não tem valor definido, pois fatorial(0−1)

é indefinido. Como x = 0, a função tem valor definido e é igual a 1.

Exemplo 2 - adição, multiplicação e potencialização

Considerando a seguinte definição recursiva para uma função de adição, multiplicação

e potencialização:

adicao = (x, y) · (x = 0 ! y, adicao(x − 1, y) + 1)

mult = (x, y) · (x = 0 ! 0, adicao(mult(x − 1, y), y))

pot = (x, y) · (x = 0 ! 1, mult(pot(x, y − 1), x))

Observa-se que:

• A adição é definida através da função sucessor

• A multiplicação é definida em termos de adições de y

• A potencialização é definida em termos de multiplicações de x

Exemplo 3 - divisão e multiplicação

Considerando a seguinte definição recursiva para uma função de divisão e de

multiplicação, como dada acima:

div = (x, y).(x < y ! 0, div(x − y, y) + 1)

m = (x, y)mult(y, div(x, y))

para y = 0, m(x, 0) tem-se:

• m(x, 0) = mult(0, div(x, 0)) = 0, é definido.

• m(x, 0) = mult(0, div(x, 0)) é indefinido, pois div(x, 0) é indefinido.

Exemplo 4 - minimização

Seja a função h definida pela minimização de f = (x, y).f (x, y) obtem-se:

h = x · min{y|f(x, y) = 0 e, 8z tal que z < y, f(x, y) é definida}

Para definir h é preciso uma função k:

k = (x, y) · (f(x, y) = 0 ! z, k(x, z + 1))

então h pode ser definida como:

h = x · k(x, 0)

Para o valor x, h é definida como o menor natural y tal que f(x, y) = 0.

3

3 Classe das Funções Definidas Recursivamente

A seguir serão mostrados alguns tipos de Classes das Funções Definidas Recursivamente.

E posteriormente, serão mostradas suas definições e expressões numéricas.

3.1 Tipo de Definição Recursiva

Um tipo de definição recursiva pode ser dada abaixo, sendo n  1

N, B,Nn ! N e Nn ! B (2)

As constantes e variáveis dos tipos, assume-se:

• Tipo N

As constantes são os números: 0, 1, 2...

As variáveis são: x, y, z...

• Tipo B

Denota-se apenas como verdadeiro ou falso