Ciência da Computação

Lista de Linguagens de Programa¸ao – 1 c˜ Matr´ ıcula: Nome:

1. Uma linguagem ´ chamada Turing Completa se ela permite simular, em software, um e computador t˜o poderoso quanto a M´quina de Turing. Neste curso estudaremos a a linguagens que s˜o Turing completas. Por´m vocˆs j´ viram alguns exemplos de lina e e a guagens que n˜o s˜o Turing Completas. a a
(a) O que uma linguagem precisa ter, para que ela seja considerada Turing Completa?

(b) Descreva uma linguagem que n˜o seja Turing Completa. Dica: vocˆs j´ estudaram a e a linguagens assim no curso Fundamentos da Teoria da Computa¸˜o (FTC). ca (c) Descreva um problema que a linguagem acima n˜o conseguiria resolver. a (d) HTML ´ uma linguagem Turing Completa? E SQL? e 1

2. Brain Fuc*, projetada por Urban M¨ller em 1993, ´ talvez a menor linguagem de u e programa¸ao considerada Turing Completa. Brain Fuc* cont´m oito comandos diferc˜ e entes, que manipulam o estado de uma fita. A fita, que simula a mem´ria, consiste o de uma sequˆncia de c´lulas contendo n´meros inteiros. Neste exerc´ vocˆ vai fazer e e u ıcio e um pouco de Brain Fuc*ing. Embora n˜o seja parte do exerc´ a ıcio, um interpretador de
Brain Fuc* n˜o usa em torno de uns 200 caracteres. Talvez vocˆ queira escrever um. a e
(a) Liste os oito comandos (s´ ımbolo mais descri¸ao curta) usados em Brain Fuc*. c˜ (b) Escreva um programa em Brain Fuc* que zere o conte´do da c´lula corrente. u e

(c) Escreva um programa em Brain Fuc* que copie o conte´do da c´lula corrente para u e a c´lula a esquerda. e `

(d) Escreva um programa que inicialize a c´lula corrente com o n´mero trˆs, mova o e u e cursor para a pr´xima c´lula, inicialize esta posi¸˜o com o n´mero quatro, e ent˜o o e ca u a some o conte´do das duas c´lulas, colocando o resultado na segunda c´lula. u e e (e) Escreva um programa que leia a entrada, copiando os caracteres lidos para a fita, e ent˜o percorra a fita,