P2_Teocomp

Prévia do material em texto

Marco Antônio Oliari e Victor Aguiar Marques
O problema é semi-decidível. Apesar do algoritmo EA enumerar todos os elementos do conjunto A, quando n não pertencer ao conjunto e A for um conjunto infinito, o algoritmo será incapaz de dar a resposta negativa. Entretanto, quando o conjunto for finito ou n pertencer ao conjunto A (independente do seu tamanho), temos a resposta positiva pois é possível comparar n com cada elemento gerado por EA no final de cada iteração. Dessa forma, considerando a proposição de que um problema L é decidível se e somente se existe uma NTM M com L(M) = L aonde todas as computações de M terminam, podemos afirmar que o problema é semi-decidível.
A ideia principal do algoritmo é que a segunda fita funcione como um contador. A cada iteração da máquina, subtrai-se 1 do valor da fita principal e escreve-se 1 na fita auxiliar, contando o número por completo até que a fita principal tenha valor 0.
A primeira fita utilizada no algoritmo guardará o número de entrada, enquanto a saída será desenvolvida na segunda fita.
1. Primeiramente verifica-se a entrada: caso seja lido um segundo branco consecutivo a execução é encerrada, no contrário percorre-se toda a entrada da fita 1 para a direita até que encontre-se um branco;
2. Encontrando um branco, é escrito 1 na fita 2;
3. Percorre-se a fita 1 para a esquerda em busca de um 1, invertendo todos os 0’s para 1’s;
a. Caso o 1 seja encontrado, é invertido para 0 e percorre-se a fita para a direita até que se encontre branco, quando é escrito 1 na fita 2;
b. Caso não seja encontrado, a máquina encerra e o resultado está na fita 2. 
4. Repetir o passo 3.
Para determinar a complexidade de tempo da máquina, considera-se o pior caso de computação para uma entrada de tamanho n. No caso dessa máquina, o pior caso ocorre quando todos os caracteres da string de entrada são 1’s (o número de subtrações é maior porque o número binário terá o maior valor possível). O primeiro passo só ocorre uma vez e são feitas n+1 transições, o segundo é feito apenas uma vez também e tem uma transição. Já o passo 3 é repetido a mesma quantidade de vezes que o valor representado pela string de entrada, dessa forma, se converter o número para a representação decimal, serão feitas 2n repetições desse passo. Esse passo varia a quantidade de transições por iteração, o maior número de transições é 2n+1 e o menor é 2. Porque o passo 3 repete 2n vezes o comportamento assintótico é dado por O(2n).