Teoria da Computação - Segunda prova - Pedro Rezende - UnB

Prévia do material em texto

Teoria da Computação – UnB – 1º/2012
Segunda Prova – 31.07.12
Primeira questão
Dê a definição matemática dos seguintes conceitos:
1. Máquina de Turing (TM clássica), Descrição Instantânea (configuração) e Computação 
(sequência de transições) nesse modelo. (20 pontos)
2. As semânticas (possíveis interpretações do funcionamento) para Máquinas de Turing vistas 
no curso. (15 pontos)
3. Problema ou linguagem decidível; problema ou linguagem Turing-reconhecível (ou Turing-
computável); problema ou linguagem não-compatível. (15 pontos)
Segunda questão
Descreva, inclusive qualquer sigla ou símbolo utilizado na resposta:
1. Hierarquia de Comski, incluindo exemplos que distinguem classes (20 pontos)
2. A Tese (ou hipótese) de Church (ou Church-Turing) e motivos para crer nela (15 pontos)
3. Problema ou linguagem NP, problema ou linguagem NP-completo, exemplo (descrição do 
problema), e do que trata uma das seguintes questões “Problema da Parada”, ou “PvNJ”. (15 
pontos)
	Teoria da Computação – UnB – 1º/2012
	Segunda Prova – 31.07.12
	Primeira questão
	Segunda questão