O que significa espaço sublinear para máquinas de Turing?

10

O problema de decidir se uma entrada é um palíndromo ou não tenha sido provado para exigir de espaço em uma máquina de Turing. No entanto, mesmo armazenar a entrada ocupa espaço  n, então isso não significa que todas as máquinas de Turing requerem espaço Ω ( n ) ?Ω(registron)nΩ(n)

Obviamente, não há contradição aqui, pois qualquer função que use pelo menos espaço linear também usa pelo menos espaço logarítmico. Mas escrever sugere que é possível para uma máquina de Turing usar menos do que o espaço linear - afinal, por que as pessoas gastariam todo esse tempo provando Ω ( log n ) se isso era exatamente a mesma coisa que parece ser um triv ( n ) trivial ligado? Então, o que significa para uma máquina de Turing usar menos que o espaço linear?Ω(registron)Ω(registron)Ω(n)

jsguy
fonte
3
Além disso , a complexidade do espaço geralmente considera memória adicional exatamente por esse motivo. (Observe que sua pergunta está incorreta; você deve perguntar "como obter O (log n) ...".))
Raphael

Respostas:

15

O(registron)O(registron)

Yuval Filmus
fonte
Obrigado pela resposta. Por que precisamos converter o índice em um formato binário? Eu pensei que as máquinas de Turing eram modelos abstratos de computação; então, por que elas deveriam converter números decimais em suas representações binárias?
Jsguy
4
O(registron)
@DavidRicherby, uma célula de fita não pode conter um número com mais de um dígito?
Jsguy
4
@jsguy Atualize a definição de máquinas de Turing. Uma célula de fita contém um único símbolo do alfabeto.
David Richerby
@DavidRicherby, obrigado Eu acho que faz sentido para mim agora!
Jsguy