Em conexão com essa pergunta , me ocorreu pensar: qual é a complexidade de tempo para uma máquina de Turing de uma única cabeça e uma fita calcular a duração de sua entrada? Para ser específico, digamos que o alfabeto da fita seja , a entrada seja uma string em cercada por espaços em branco, a máquina inicia no símbolo de entrada mais à esquerda e deve termina no símbolo mais à esquerda de uma sequência em (novamente cercada por espaços em branco) que fornece a representação binária do comprimento da entrada. Isso também pode ser pensado como o problema de converter um número de unário para binário.( 0 + 1 ) ∗ ( 0 + 1 ) ∗
É fácil resolver isso em uma máquina de duas fitas ou duas cabeças em tempo linear (basta escanear a entrada com uma cabeça enquanto usa a outra cabeça para aumentar repetidamente um contador; incrementar é uma operação de tempo amortizado constante). Mas as soluções de cabeçote único que posso encontrar são apenas (por exemplo, incrementa repetidamente um contador e depois o desloca em uma posição ao longo da fita). Existe um limite inferior correspondente?
Tentei algumas pesquisas, mas frases como "uma cabeça" e "tamanho da entrada" são tão comuns que dificultam a pesquisa na literatura por resultados conhecidos sobre esse problema.
fonte
Respostas:
Não pode ser calculado no tempo .o ( nlgn )
Seja uma máquina que, dada uma sequência de entrada pare com o tamanho de escrito em binário na fita.x xM x x
Podemos adicionar um DFA simples (tempo linear de espaço zero) a para verificar se o tamanho da entrada é uma potência de dois: basta verificar se o primeiro bit é 1 e o restante é zero.M
Vamos supor que execute tempo . Então podemos decidir a tempo que o tamanho da entrada é uma potência de dois. Em outras palavras, o idioma a seguir é decidível em . Segue-se de que deve ser regular. Mas é fácil verificar se o idioma não é regular. Portanto, não pode ser executado no tempo .M o ( n lgn ) o ( nlgn ) D T i m e (n lgn )
fonte