Letícia dos Santos - lsantos@inf.ufrgs.br
O trabalho prático consiste em um código capaz de converter ‘Máquinas de Turing de fita duplamente infinita’ em ‘Máquinas de Turing com Stay’.
Trabalho implementado em python3 e com nota final 10.
Para executar:
$ python3 converter.py <file_with_original_TM_transitions.csv>O resultado será exibido no terminal e impresso no arquivo file_with_original_TM_transitions_converted.csv
Segue um pseudo-código onde Converte_MT recebe um csv com as transições da máquina e Sub_maquina_escreve_no_inicio_e_empurra faz as transições para escrever um símbolo e empurrar o restante da fita. A divisão entre as colunas da tabela é representada por "|".
Converte_MT(csv):
Lê csv, obtem x estados e y símbolos;
Troca estado 1 para x+1, tanto no estado inicial quanto no estado final das transições;
sentinela = y;
Sub_maquina_escreve_no_inicio_e_empurra(sentinela, x+1, estado_inicial = verdadeiro);
Para cada estado com transição "L" na maquina original:
estado_volta = estado inicial da transição;
novo_estado = ultimo estado + 1;
Escreve (estado_volta | sentinela | novo_estado | sentinela | R);
Sub_maquina_escreve_no_inicio_e_empurra(0, estado_volta);
Imprime as transições em arquivo.
Sub_maquina_escreve_no_inicio_e_empurra(simb_escreve, estado_volta, estado_inicial = falso):
Se estado_inicial:
estado_para_escrever = 1;
novo_estado = ultimo estado + 1;
Senão:
estado_para_escrever = ultimo estado + 1;
novo_estado = ultimo estado + 2;
estado_rebobina = novo_estado + y, volta para o início da fita;
Para cada símbolo i:
Escreve (estado_para_escrever | i | novo_estado + i | simb_escreve | R), leu i;
Para cada símbolo j:
Se j é 0: continua, pois 0 possui uma transição para o rebobina;
Escreve (novo_estado + i | j | novo_estado + i | i | R), escreve i;
Escreve (novo_estado + i | 0 | estado_rebobina | i | R);
Para cada símbolo i:
Escreve (estado_rebobina | i | estado_rebobina | i | L), volta na fita independente do símbolo;
Escreve (estado_rebobina | sentinela | estado_volta | sentinela | R);