TRABALHO ASPECTOS TE RICOS DA COMPUTA O

UNIP – UNIVERSIDADE PAULISTA
CAMPUS BRASÍLIA

CIÊNCIA DA COMPUTAÇÃO
ASPECTOS TEÓRICOS DA COMPUTAÇÃO
Professora Clotilde

TRABALHO PARA NP1

BRASÍLIA – DF
2015

Ciência da Computação
Aspectos Teóricos da Computação

Alunos:
Vanessa Sugimoto – B495BH-1
Leandro Matos Carvalho – B37HFF-9
Wanderpaulo Lázaro da Silva Santos – B4005G-8
Rafael Cerqueira dos Santos – B359GI-5
João Luiz de Souza Serafini – B7821I-5

BRASÍLIA – DF
2015

TRABALHO PARA NP1
1) Construa uma máquina de Turing para aceitar cada umas das seguintes linguagens:
a) L = { 0 n 1n 2n | n > 0 }

b) L = { wcy | w, y ∈ {0, 1}}

c) L = { x ∈ {0, 1}* | x contém o mesmo número de 0's e 1's }

d) L = { 0i 1 j 2k | i = j ou j = k, com i, j, k > 0 }

2) Máquina de Turing como calculadora de funções numéricas:
a) O que são:
Uma máquina de Turing pode ser vista como uma calculadora de funções parciais dos inteiros nos inteiros: f : ℕk → pℕ
b) Como funcionam:
Suponhamos que os inteiros estão codificados em unário. Então, um inteiro i ≥ 0 é representado por 1i . Se uma função tiver k argumentos i 1 , . . . , i k , a sequência de entrada pode ser
1i 0 . . . 01 1i . Se a máquina de Turing para com a sequência 1m na fita, então f (i 1 , . . . , i k ) = m .
1

k

Uma função parcial f diz-se recursiva se existir uma máquina de Turing que calcula a função para todos os valores em que está definida não terminando a execução caso contrário. Uma função total f diz-se recursiva total se existir uma máquina de Turing que calcula a função para todos os

valores do argumento, isto é, a máquina de Turing para para quaisquer argumentos.
c) Mostre dois exemplos:
Exemplo 1:

Exemplo 2: