Transdutor de espaço logarítmico (LST)

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 Szepietowski, Andrzej (1994), Turing Machines with Sublogarithmic Space , Springer Press, ISBN 3-540-58355-6. Retrieved on 2008-12-03.

Categoria:Máquina de Turing