Transdutor de espaço logarítmico (LST)
 | Este artigo ou secção contém uma lista de referências no fim do texto, mas as suas fontes não são claras porque não são citadas no corpo do artigo, o que compromete a confiabilidade das informações. (Agosto de 2021) |
Um Trandutor de espaço logarítmico (LST) é um tipo de Máquina de Turing usada para reduções de espaço logarítmico.
Um LST tem três fitas:
- Uma fita apenas para leitura, de entrada.
- Uma fita para ler/escrever, de trabalho.
- Uma fita apenas para escrita, de saida.
Uma linguagem A é dita espaço logarítmo redutível para uma linguagem B se existe uma LST que converte um problema A para um problema B, usando espaço logarítmico em sua fita, de tal modo que a entrada está em A sse a saída está em B.
Esta parece ser uma idéia bastante complicada, mas existem duas propriedades úteis que ajudam a entender a redução:
- A propriedade de transitividade. (A reduz a B e B reduz a C, então A reduz a C).
- Se A reduz a B, e B é espaço logarítmico, então A é espaço logarítmico.
Referências[editar | editar código-fonte]
- Szepietowski, Andrzej (1994), Turing Machines with Sublogarithmic Space , Springer Press, ISBN 3-540-58355-6. Retrieved on 2008-12-03.