Computação Quântica/Capítulo 3/Exercícios
Exercícios Cap.3 - Introdução à Ciência da Computação
Volte para a página principal do livro clicando aqui: Computação_Quântica
Exercicio 3.3 (Máquina de Turing para inverter um string de bits) Descreva uma máquina de turing que, dado um número binário X como entrada, sua saída seja os bits do número X em ordem inversa.
Considere os seguintes caracteres especiais do alfabeto da máquina: % (inicio da fita), B (espaço em branco), i (caracter invertido), * (indica fim da entrada).
A estratégia é marcar o fim da entrada com um caracter especial e fazer o cabeçote da máquina buscar um a um, em ordem invertida, os símbolos da entrada e escrevê-los após a marcação. Por fim, a marcação de fim de entrada é substituída por ínicio da fita.
- Acha o fim do número X e marca com caracter especial *
- < Q1 , % , Q1 , % , +1 >
- < Q1 , 1 , Q1 , 1 , +1 >
- < Q1 , 0 , Q1 , 0 , +1 >
- < Q1 , B , Q2 , * , -1 >
- Caminha para a esquerda encontrando os valores para inversão
- < Q2 , 0 , Q3 , i , +1 >
- < Q2 , 1 , Q4 , i , +1 >
- < Q2 , i , Q2 , i , -1 >
- < Q2 , % , Q6 , B , +1 >
- Inverte o símbolo 0
- < Q3 , i , Q3 , i , +1 >
- < Q3 , * , Q3 , * , +1 >
- < Q3 , 0 , Q3 , 0 , +1 >
- < Q3 , 1 , Q3 , 1 , +1 >
- < Q3 , B , Q5 , 0 , -1 >
- Inverte o símbolo 1
- < Q4 , i , Q4 , i , +1 >
- < Q4 , * , Q4 , * , +1 >
- < Q4 , 0 , Q4 , 0 , +1 >
- < Q4 , 1 , Q4 , 1 , +1 >
- < Q4 , B , Q5 , 1 , -1 >
- Anda para a esquerda até encontrar o marcador de fim de entrada *
- < Q5 , 0 , Q5 , 0 , -1 >
- < Q5 , 1 , Q5 , 1 , -1 >
- < Q5 , * , Q2 , * , -1 >
- Remarca o começo da fita, sinalizando que o algoritmo terminou
- < Q6 , i , Q6 , B , +1 >
- < Q6 , * , Q6 , % , 0 >
Exercicío 3.8 (Universalidade de NAND) Mostre que a porta NAND pode ser usada para simular as portas AND, XOR e NOT, utilizando também fios, bits de trabalho (ancilla) e FANOUT.
- A porta NOT pode ser simulada através dos circuitos apresentados na figura abaixo, onde também podemos ver a tabela verdade destes.
- A porta AND pode ser simulada através dos circuitos apresentados na figura abaixo, onde também podemos ver a tabela verdade destes.
- A porta XOR pode ser simulada através do circuito apresentado na figura abaixo, onde também podemos ver a tabela verdade deste.
Exercicío 3.21 Mostre que se uma linguagem L1 é redutível para a linguagem L2 e a linguagem L2 é redutível para a linguagem L3, então L1 é redutível para a linguagem L3.
- Por hipótese existem reduções polinomiais R1 e R2 tal que,
-> se somente se
-> se somente se
- Considerando o seguinte algoritmo:
R(x)
y1 <- R2(x)
y <- R1(y1)
return y
- Pela propriedade do algoritomo que usa R1 e R2 sabemos que se então e consequentemente , por outro lado se então e consequentemente .
Portanto, pelo algoritmo acima vale a propriedade se e somente se . Logo o algoritmo é polinomial e consequentemente L1 é redutível para L3.
Volte para a página principal do livro clicando aqui: Computação_Quântica