Por que usamos máquinas de Turing de fita única para complexidade do tempo?

Como você sabe, existem muitas anomolias para as máquinas de Turing de fita única quando o tempo é : simulação de fita múltipla TM, simulação de alfabeto de fita maior com apenas , construtibilidade de tempo, não estanqueidade teorema da hierarquia temporal, ... $o(n^2)$ $\{0,1,b\}$

Além disso, como resultado , e muito específico do modelo lowerbounds horários de problemas simples (que não se traduzem a lowerbounds mesmo superlineares em dois TMs da fita). $\mathsf{DTime}(o(n\lg n)=\mathsf{Reg}$ $O(n^2)$

Para a complexidade do espaço, usamos um modelo em que temos uma fita de entrada somente leitura separada, que é mais natural e robusta.

Um modelo de TM com várias fitas (ou pelo menos 2 fitas de trabalho) seria muito mais robusto e não levaria a anomalias como as listadas acima. Certa vez, perguntei a um proeminente teórico da complexidade que provou resultados de simulação nos primeiros anos da teoria da complexidade se ele conhece alguma melhoria em um desses resultados antigos e a resposta foi que ele não acha que "as perguntas sobre o modelo de fita única são: importante".

Se alterarmos o modelo padrão para a complexidade do tempo para TMs de duas fitas, resultados razoáveis na teoria da complexidade não serão alterados e evitaremos essas anomalias causadas por um modelo específico. Então, minha pergunta é:

existe alguma razão para a complexidade do tempo ainda ser definida em termos de TMs de fita única? (exceto motivos históricos)

cc.complexity-theory turing-machines Kaveh
fonte

Nunca vi complexidade de tempo definida por TMs de fita única.

$\:$ Vi apenas as classes robustas de complexidade de tempo definidas pelas TMs de fita única.

$\;\;$

@ Ricky, eu quis dizer que a complexidade do tempo de um problema é definida em termos da complexidade do tempo das TMs de fita única que podem resolvê-lo.

Kaveh

e quero dizer que nunca vi isso feito.

$\:$ Eu sempre vi, no mínimo, acesso aleatório.

$\;\;$

mas essa é realmente a definição usual? o que eu vi nos livros didáticos é: 1) defina a máquina de Turing com fita única (porque é mais simples); 2) mostrar como estender a outras variantes, em particular o acesso múltiplo e aleatório; 3) mostrar que tudo isso pode simular um ao outro com, no máximo, desaceleração polinomial; 4) esqueça prontamente o modelo em sua maior parte, pelo menos até precisarmos de coisas mais sutis, como máquinas oracle e reduções no espaço de log; então, como @RickyDemer, eu contestaria a afirmação de que essa é realmente a definição usual.

Sasho Nikolov

Não tenho uma resposta para isso, mas quero apenas apontar este trabalho para você por Yamakami ( springerlink.com/content/u844854721p83870 ). Este artigo discute o que acontece quando você adiciona conselhos a uma máquina pequena (isto é, TM linear de fita única). Ele prova várias separações de classe, mas o faz usando essas TMs de uma fita. Essas separações não funcionariam se você tivesse outro tipo de MT. Eu acho que este é um bom exemplo em que você pode provar coisas legais com uma fita e provavelmente não pode com um modelo diferente. A moral é "uma fita importa quando você lida com coisas sutis".

Marcos Villagra

Respostas:

As outras respostas parecem muito legais. Eu gostaria de compartilhar um comentário que Russell Impagliazzo fez anos atrás em uma palestra, que ficou comigo desde então.

Eu acho que Turing pode ter preferido uma única fita TM devido à plausibilidade física.

Apontei Russell para esse tópico dias atrás, mas, como ele não está aqui, gostaria que seu comentário fosse conhecido e farei o possível para interpretá-lo.

Para uma única fita TM, supondo uma fita de comprimento infinito (por favor, cole comigo), você pode criar uma TM que apenas precise de uma quantidade limitada de energia por iteração. Imagine a fita como uma haste longa e a cabeça, que contém toda a lógica da MT, simplesmente se move ao longo dessa haste. (Penso nisso como uma engenhoca engrenada e bonitinha, usando tecnologia muito primitiva. A haste pode ter entalhes para ajudá-la, e o conteúdo da célula de fita pode ser apenas um bloco deslizado ortogonalmente ao eixo da haste.)

Por outro lado, como você faz isso para um -tape TM? Se você tem $k$ $k$ das engenhocas acima, eles devem comunicar seu status de leitura às outras cabeças potencialmente extremamente distantes, que consomem quantidades ilimitadas de energia (digamos que você use fios, que necessariamente vazam calor) e, além disso, não são instantâneas, complicando o mecanismo. Se, em vez disso, você mantivesse as cabeças juntas e movesse as fitas por baixo delas, estaria usando energia suficiente para mover fitas de comprimento infinito. Não vejo como obter energia limitada em ambos os casos. Truques como diminuir os incrementos da fita (para obter um comprimento finito) supõem um universo infinitamente divisível e violam coisas como a constante de Planck e o princípio holográfico. Mesmo ignorando-os, os mecanismos na cabeça devem ser arbitrariamente precisos, o que novamente causa problemas de energia e é prodigiosamente complicado.

Obviamente, o primeiro esquema apresenta problemas: a construção da fita infinita com infinitos entalhes, infinitos sóis para alimentar coletores solares na cabeça móvel, um suprimento infinito de produtos de limpeza e manutenção, etc. Talvez um grande avanço na mecânica quântica pode permitir que as cabeças da fita se comuniquem bem, mas agora veja como nossa engenhoca é complicada. De qualquer forma, acho que o comentário de Russell é muito, muito interessante. $k$

matus
fonte

eu pensei que Turing estava tentando abstrair o conceito de "computação" e não abstraindo um modelo para um dispositivo físico. nesse caso, uma única fita de Turing capturas máquina limpa a intuição filosófica que a computação envolve o acesso local a grande (infinito) de memória

Sasho Nikolov

Eu estava esperando razões teóricas (não realizabilidade dos modelos), mas acho essa resposta muito interessante, por isso estou aceitando. Obrigado novamente.

Kaveh

Mantendo as cabeças das fitas no lugar, parece que podemos tornar a energia total linear ou, esperançosamente, não pior que a quase linear no tempo, projetando uma forma da construção da Hennie-Stearns. Estou imaginando as fitas enroladas em loops cada vez maiores à medida que se estendem em qualquer direção ... Ou, mais imaginativamente, em carretéis de fitas, 100 fitas em um carretel, 100 carretéis em um rack, 100 racks em um armazém e em. Obviamente, para energia limitada por iteração, precisaríamos de energia total linear no tempo. Mas quaseilinear é melhor que o ingênuo quadrático, então pensei em mencioná-lo.

22417 Dan Brumleve

$f(n)$

Há uma clara razão pedagógica clara pela qual Sipser faz isso, ou seja, o curso flui naturalmente dessa maneira porque:

Você deve apresentar a máquina de fita única antes da máquina com várias fitas, caso contrário, aumenta a curva de aprendizado.
$\cdot$ $\cdot$
Idealmente, você deve comparar a máquina de fita múltipla com a máquina de fita única no momento em que introduzir a máquina de fita múltipla; caso contrário, a ignorância prolongada causará confusão adicional.
Você pode omitir a introdução de classes TIME análogas para máquinas com várias fitas, simplificando a notação geral.

Não há razão para discutir sobre a limpeza conceitual quando a pedagogia dita claramente o caminho mais fácil, e todo graduado em ciência da computação deve seguir este curso elementar, incluindo todos aqueles que ainda não entendem as provas.

Jeff Burdges
fonte

Não, IIRC, meu primeiro encontro com as TMs foi a primeira edição de Hopcroft e Ullman. Mas a razão pela qual estou fazendo essa pergunta está realmente relacionada ao bom livro de Sipser, ensinei teoria da complexidade com base na Sipser e achei que seria mais simples e mais limpa (sem nenhum material essencial perdido) para mim e para os alunos se fosse baseada em um -tape TMs. Todos esses pequenos detalhes técnicos sobre o acesso restrito às TMs de fita única seriam evitados e eu poderia cobrir material mais interessante no tempo limitado que tinha. Sipser é relaxada sobre o uso de tese de Church-Turing,

Kaveh

então eu pensei que estar relaxado sobre essa parte também poderia ser bom. Na parte do teorema da hierarquia de tempo, ele menciona que o fator extra de log não é necessário se tivéssemos várias fitas e seria bastante apertado. Isso me levou a perguntar se há algum motivo não histórico para o uso de TMs de fita única para complexidade de tempo. Não é pior do que usar uma fita somente leitura separada para a complexidade do espaço (e, novamente, isso ocorre principalmente porque uma única fita TM não captura a intuição sobre as pequenas classes de complexidade do espaço).

Kaveh

Não vejo como alguém entenderia limites de espaço sub-lineares sem uma fita de entrada separada.

$\;$

Sim, eu diria que o SPACE é feito de maneira diferente, em parte porque você estará fazendo limites sublineares, o que provavelmente não fará por TIME. Eu defenderia a assinatura do TIME ou o que a Sipser faz pelo SPACE, se você quiser fazer dessa maneira, certamente gostaria de falar sobre o TIME ou TIME_1 ou o que quer que seja antes das máquinas de fita múltipla.

Jeff Burdges

Curiosamente, Sipser diz apenas "Máquina de Turing" ao definir ESPAÇO (f (n)), mas depois muda a definição ao discutir funções sublineares f, atribuindo um exercício sobre a equivalência do superliner f. Já ensinei esse material da Sipser antes. Eu não tinha pensado muito sobre isso na época, mas estou satisfeito com isso agora.

Jeff Burdges

A máquina de Turing original foi descrita usando uma única fita:

www.cs.ox.ac.uk/activities/ieg/e-library/sources/tp2-ie.pdf

Portanto, como você afirma em sua pergunta, isso ocorre principalmente por razões históricas. Além disso, sempre há a tendência de perguntar qual é o modelo mais simples que pode fazer algo ...

Além disso, como esse tópico geralmente é ensinado de maneira muito formal, é tecnicamente mais fácil descrever uma única máquina de fita do que uma usinagem de duas fitas.

Veja também:

http://www.cs.utah.edu/~draperg/cartoons/2005/turing.html

Sariel Har-Peled
fonte