Existe uma máquina de Turing que roda no tempo , mas não ?

Sabe-se que qualquer máquina de Turing (determinística, com uma única fita) que executa no tempo decide um idioma regular (por exemplo, consulte este link ). Assim, existe uma máquina de Turing equivalente que roda no tempo . Em outras palavras, se então $o(n\log n)$ $O(n)$ $t(n)=o(n\log n)$

D T I M E (t (n)) ∖ D T I M E (n) = \emptyset .

$\mathsf{DTIME}\left(t\left(n\right)\right)\backslash\mathsf{DTIME}\left(n\right)=\emptyset.$

Fiquei imaginando se existe um exemplo em que a máquina de Turing original ainda não estivesse funcionando no tempo . $O(n)$

Resumindo: Existe uma máquina de Turing que funciona no tempo , mas não ? $o(n\log n)$ $O(n)$

complexity-theory turing-machines time-complexity Eu faço
fonte

Você pode executar uma máquina de Turing em se desejar. No entanto, você precisa decidir um idioma comum?

O (n \log \log n)

$O(n \log \log n)$

Pål GD

@ PålGD Claro, isso é trivial. Você quer dizer ? E é uma máquina de fita única?

Θ (n \log \log n)

$\Theta(n\log\log n)$

David Richerby

Respostas:

A resposta parece ser negativa, de acordo com o Corolário 4.12 de Verificando a complexidade do tempo de máquinas de Turing determinísticas por David Gajser ( ArXiv ).

Eu faço
fonte