Construa uma DTM multi-fita que lê um número de entrada x em representação binária e escreve (converte) este mesmo número x em representaçã...

Para construir uma DTM multi-fita que converte um número em representação binária para representação unária, podemos seguir os seguintes passos: 1. Inicialmente, a cabeça de leitura da primeira fita estará posicionada no primeiro bit do número binário de entrada e a cabeça de escrita da segunda fita estará posicionada no primeiro espaço em branco da fita de saída. 2. A máquina irá ler o bit atual da primeira fita e escrever um símbolo "1" na segunda fita. Em seguida, a cabeça de escrita da segunda fita irá se mover para a direita até encontrar o próximo espaço em branco. 3. A cabeça de leitura da primeira fita irá se mover para a direita para ler o próximo bit do número binário de entrada. Se o bit lido for um "0", a máquina irá escrever um símbolo "0" na segunda fita e mover a cabeça de escrita da segunda fita para a direita até encontrar o próximo espaço em branco. 4. Se o bit lido for um "1", a máquina irá escrever um símbolo "1" na segunda fita e mover a cabeça de escrita da segunda fita para a direita até encontrar o próximo espaço em branco. 5. A máquina irá repetir os passos 3 e 4 até que todos os bits do número binário de entrada tenham sido lidos. 6. Quando a máquina encontrar o último bit do número binário de entrada, ela irá escrever um símbolo "B" na segunda fita para indicar o fim da representação unária. A complexidade assintótica de tempo da máquina é O(n), onde n é o número de bits do número binário de entrada, pois a máquina precisa ler cada bit do número de entrada uma vez e escrever um número correspondente de símbolos "1" na fita de saída.