Máquinas de Turing Simétricas

Uma maquina de Turing simétrica é uma máquina de Turing que possui um grafo de configuração sem direção. Isso é, uma configuração i produz a configuração j se somente se j produz i.

O conjunto de linguagens que possui uma maquina de Turing simétrica decide em espaço log é chamada de SL. Essa máquina foi definida em 1982 por Lewis e Papadimitriou, que procurando por uma classe de espaço para USTCON, que até aquele momento, na melhor hipótese, era classificado somente como NL, apesar de não exigir não determinismo, eles definiram a máquina de Turing simétrica, usando-a para definir SL. As máquinas de Turing simétricas são um tipo de máquina de Turing com poder computacional não determinístico limitado.

Informalmente, computações simétricas são reversíveis, de modo aproximado. Uma computação simétrica é dividida em sub computações localizadas entre configurações especiais nas quais, nessas configurações especiais é o não determinismo que assume, de tal forma que a única configuração especial alcançada a partir de uma configuração anterior é a configuração especial que iniciou o segmento (sub computação). Assim os segmentos se comportam de forma determinística quando se movimentam para frente e de modo não determinístico limitado quando se movimentam para trás. Além disso, se há uma configuração especial A1 para A2, deve haver um caminho de volta a partir de A2 para A1.

Exemplo de uma MT Simétrica

Complexidade de espaço logarítmica simétrica

• SSPACE(S(n)) é uma classe das linguagens que uma máquina de Turing simétrica aceita rodando em espaço O(S(n)).
• SL é a classe de problemas resolvidos por uma maquina de Turing não determinística em espaço logarítmico, de tal modo que
  1. Se a resposta for ‘sim’, um ou mais ramos computacionais são aceitos.
  2. Se a resposta for ‘não’, todos os ramos são rejeitados.
  3. Se a máquina consegue fazer uma transição não determinística da configuração A para a configuração B, então também consegue executar a transição de B para A.(Isto é o que ‘simétrico’ significa).
  4. Isso prova que SL=CoSL.

Ideia sobre o porque que USTCON é SL-completo

O problema mais importante dos Problemas Completos é o USTCON, Lewis e Papadimitriou por definição mostraram que USTCON é um problema completo para a classe SL.Eles construíram uma máquina não determinística para USTCON e elaboraram um lema para converter essa máquina em uma Máquina de Turing Simétrica. Após isso, o teorema diz que qualquer linguagem aceita por uma máquina de Turing simétrica é redutível em espaço logarítmico a USTCON a partir das propriedades do cálculo simétrico onde vemos que uma configuração especial possui arestas não dirigidas.

Bibliografia

• Reingold, Undirected STConnectivity in LogSpace, STOC 2005.
• Lecture Notes :CS369E: Expanders in Computer Science By Cynthia Dwork & Prahladh Harsha
• Lecture Notes
• Symmetric LogSpace is closed undercomplement Noam Nissa
• Sharon Bruckner Lecture Notes
• Deterministic Space Bounded Graph connectivity Algorithms Jesper Janson