Transdutor de espaço logarítmico (LST)
Aspeto
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 logaritmo 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 se a saída está em B.
Esta parece ser uma ideia 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.