Existe uma prova de que a emulação de uma máquina de Turing em uma máquina de Turing inconsciente não pode ser feita em menos de que é o número de etapas que a máquina de Turing usa ? Ou isso é apenas um limite superior?
No artigo de Paul Vitányi sobre máquinas de Turing relativizadas e inconscientes, Vitányi afirma
"Eles [ Pippenger e Fischer, 1979 ] mostraram que esse resultado não pode ser melhorado em geral, uma vez que existe uma linguagem L que é reconhecida por uma máquina de Turing tempo real de 1 fita e qualquer máquina de Turing inconsciente que reconhece deve use pelo menos uma ordem etapas ".
Isso deve indicar como um limite absoluto. No entanto, não encontro nenhuma prova disso em
Pippenger, Nicholas; Fischer, Michael J. , Relações entre medidas de complexidade , J. Assoc. Comput. Mach. 26, 361-381 (1979). ZBL0405.68041 .
Alguma ideia? Além disso, qual é a complexidade espacial dessa emulação? Tanto quanto sei, a conversão para uma máquina de Turing universal apenas dobra o comprimento da fita. Posso assumir que a complexidade do espaço é com a complexidade do espaço da máquina de Turing original?
fonte
Respostas:
Como mencionado acima, não se sabe em geral se existe uma simulação inconsciente mais rápida.
Mas limites inferiores interessantes para esse problema são conhecidos, sob condições mais restritas. Por exemplo, e se você quiser uma simulação inconsciente que preserve não apenas o tempo mas também o uso de espaço ? Beame e Machmouchi provaram recentemente uma troca interessante de espaço-tempo interessante para este problema: ou o espaço deve aumentar por um fator de ou o tempo deve aumentar por um fator de .s n 1 - o ( 1 ) Ω ( log n ⋅ log log n )t s n1 - o ( 1 ) Ω ( logn ⋅ logregistron )
O artigo está aqui: http://eccc.hpi-web.de/report/2010/104/
fonte
Apenas um comentário extenso: acho que ainda é um problema em aberto; veja o blog de Lipton e Regan para algumas boas discussões sobre como melhorar o resultado do teorema de Fischer-Pippenger .
Por exemplo, veja as postagens: Máquinas de Turing inconscientes e um limite "Crock" ou circuitos para cálculos de máquinas de Turing (ambos datados de 2009).
fonte