Continuação da resolução dos exercícios do terceiro capítulo do livro Computability, Complexity, and Languages. Fundamentals of Theoretical Computer Science.

Consultar a parte 1 da resulução

Pág 54, questão 4. Let SQSM(x) be true if x is the sum of two perfect squares; false otherwise. Show that SQSM is primitive recursive.

Resposta:

SQSM(x)=(∃a)x(∃b)x(a·a+b·b = x)

Pág 58, questão 6. Let RP(x,y) be true if x and y are relatively prime (i.e., their greatest common divisor is 1). Show that RP(x,y) is prmitive recursive.

Resposta:

RP(x,y) = ~∃wx+y((w+2)|x)&((w+2)|y)

Ou seja, RP(xmy) é verdadeiro se não existe um certo w menor que x+y que seja divisor de x e de y. No predicado de existência nos restringimos w a ser menor que a soma de x e y. Isso nos garante que w é tanto menor que x quanto é menor que y.

Nós somamos w à 2 para que o predicado de existência não teste se 0 ou 1 é divisor de x e y.

Pág 58, questão 1. Let h(x) be the integer n such that n ≤ √2x < n+1. Show h(x) is primitive recursive.

Resposta: Desenvolvendo o lado direito da inequação n ≤ √2x < n+1:

√2x < n+1

(√2x)² < (n+1)²

(2·x²)² < (n+1)²

(n+1)² > (2·x²)²

O que queremos é encontrar o menor n que satisfaça esse predicado então:

h(x) = minn [(n+1)·(n+1) > 2·x·x]

Pág 58, questão 2. Do the same when h(x) is the integer n such that

n ≤ (1+√2)x < n+1

Resposta: Desenvolvendo (1+√2)x < n+1:

x+√2x < n+1

√2x<n+1-x

2x² < (n+1-x),

com n+1 ≥ x Escrevendo isso em forma de uma função primitiva recursiva:

h(x) = minn [(2·x·x<(n+1-x)·(n+1-x)) & (n+1>x)]

Pág 58, questão 3. p is called a larger twin prime if p and p-2 are both primes. (5, 7, 13, 19 are larger twin primes). Let T(0) = 0, T(n)= the nth larger twin prime. It is widely believed, but has not been proved, that there are infinitely many larger twin primes. assuming that this is true prove that T(n) is computable.

Resposta:

Seja ltp uma função que diz se um número é o primo gêmeo maior, podemos definir ela como uma função primitiva recursiva: ltp(x) = prime(x)′(x-2) A função primitiva recursiva que nos dá o n-ésimo numero primo é:

T(0) = 0

T(n) = mink [Σki=0ltp(i)=n]

Pág 58, questão 4. Let u(n) be the nth number in order of size which is the sum of two squares. Show that u(n) is primitive recursive.

Resposta:

Aproveitando a função primitiva recursiva SQSM(x) da página 54 questão 4, podemos escrever u(n) da seguinte forma primitiva recursiva:

u(n) = mink [Σki=0SQSM(i)=n]

Pág 58, questão 5. Let R(x,t) be a primitive recursive predicate. Let

g(x,y) = maxt≤y R(x,t),

i.e. g(x,y) is the largest value of t ≤ y which R(x,t) is true; if there is none, g(x,y)=0. Prove that g(x,y) is primitive recursive.

Resposta:

g(x,y) = mink≤y R(x,y-k)

Pág 58, questão 6. Let gcd(x,y) be thegreatest common divisor of x and y. Show that gcd(x,y) is primitive recursive.

Resposta:

Seja cd(x,y,z) a função primitiva recursiva que retorna 1 se z é múltiplo de x e y simultaneamente, e 0 caso contrário:

cd(x,y,z) = (z|x)&(z|y)

Podemos escrever agora gcd compondo cd e o predicado max da questão anterior:

gcd(x,y) = maxt≤x+y cd(x,y,t)

Pág 58, questão 7. Let lcm(x,y) be the least common multiple of x and y. Show that lcm(x,y) is primitive recursive.

Resposta:

lcm(x,y) = mink≤y (x|t)&(y|t)

Pág 58, questão 8. Give a computable predicate P(x1, …, xn, y) such that the function miny P(x1, …, xn, y) is not computable.