• Disciplina: Teoria da Computação
• Período: 2019.1

Aviso!

As questões apresentadas a seguir são descrições baseadas em relatos de um ou mais alunos que fizeram tal avaliação. Logo, não há garantia de que os enunciados sejam iguais aos originais, tampouco que estejam livres de erros. Esteja ciente dessas considerações ao utilizar esse material!

Questões

Questão 1

Implemente uma máquina de Turing que reconheça palavras que seguem o seguinte formato: (0^i)(1^j)(2^k), onde i = j e k = 2^(i+1).

Questão 2

Implemente uma máquina de Turing para transformar as cadeias de entrada em cadeias com uma marcação no início de seu último terço. Por exemplo, para a palavra 010010010, o resultado seria 010010(0^#)10.

Questão 3

Qual o papel de cada uma das 3 fitas da versão determinística de uma máquina não-determínistica de 1 fita?

Questão 4

Qual a intuição do uso de um enumerador para simular uma máquina de Turing e vice-versa? Que cuidados precisam ser tomados?