Por que as máquinas de Turing sem prefixo não têm a complexidade?

Question

Reivindicou em vários textos sobre complexidade algorítmica que as máquinas de Turing sem prefixo são melhores para entender a aleatoriedade, pelo menos em sequências infinitas. Nos nies ' Computabilidade e aleatoriedade , a razão é dada por teoremas 2.2.1 e 2.2.2 em p. 83. Eu vou me concentrar no primeiro, que afirma que para alguma máquina simples (não prefixo) há uma constante $ c $ tal que para cada número natural $ D $ e string $ W $ de comprimento $ \> $ \ GEQ 2 ^ {D + 1} + D $ , há um prefixo $ x $ de $ W $ tal que a complexidade simples $ c (x) \ leq | x | -d + c $ . (Aqui $ | x | $ é o comprimento da $ x $ .)

Ou seja, se a complexidade for definida em termos de máquinas de Turing que aceitam cadeias arbitrárias como entradas, qualquer string suficientemente longa, não importa quão complexa, possa ter substrings iniciais com "mergulhos" mais ou menos arbitrários. A prova do teorema usa uma máquina que usa o comprimento de uma cadeia de entrada para construir sua saída. Este é aparentemente um ponto importante (veja abaixo).

minha pergunta: Por que uma máquina sem prefixo não pode fazer isso também? Por que a complexidade livre de prefixo também permite que os mergulhos na complexidade das subseqüências iniciais? Eu ainda não encontrei uma explicação deste ponto que eu entendo nos livros didáticos de complexidade algorítmica por nies, Downey e Hirschfeldt (veja abaixo), Li e Vitanyi (embora possa estar lá em algum lugar), ou Calude ( Computabilidade e aleatoriedade ). Eu acho que nies e d & h só acho que é óbvio, mas eu não vejo por quê.

Algumas máquinas prefixs: Downey e Hirschfeldt's aleatoriedade e complexidade algorítmicos , p. 122, refere-se a um teorema semelhante provado no início do livro, e observações que uma máquina livre de prefixo pode ser considerada uma queira uma entrada até que esteja terminado, sem se mover na direção oposta na fita e sem qualquer teste para um caractere ou padrão de rescisão de entrada. O texto diz que "isso destaca como usar máquinas livres de prefixo contorna o uso do comprimento de uma string para obter mais informações do que está presente nos bits de uma string". Eu acho que se houver uma única fita que é somente leitura e se move em apenas uma direção, então não há como manter um contador para medir os comprimentos arbitrários; Ninguém precisaria armazenar um contador em outras partes da fita ou pelo menos sobrescrever algo na fita como se lê. Mas por que uma máquina de prefixo de prefixo funcionar como esta? Li e Vitanyi's uma introdução à complexidade de Kolmogorov e suas aplicações , 3ª ed, seita. 3.1, Exemplo 3.1.1, p. 201 descreve uma máquina livre de prefixo que tem três fitas. Há uma fita unidirecional somente leitura como no Downey e Hirschfeldt, e uma fita de saída somente de gravação unidirecional. A terceira fita é uma fita de trabalho de leitura bidirecional. A fita de trabalho não pode ser usada para calcular o comprimento da entrada? Nesse caso, por que haveria uma diferença entre máquinas sem prefixo e máquinas simples de Turing? No entanto, no início do capítulo 3 (pp. 197ff), Li e Vitanyi também tratam as máquinas livres de prefixo como forma de evitar conseqüências relacionadas àquelas implícitas pelo Teorema de Nies 2.2.1.

---

Para quem acharia útil, o Teorema de Nies 2.2.1 está abaixo. (Eu decidi reproduzi-lo quase verbatim em vez de usar minha própria notação para evitar a introdução acidentalmente uma distorção.) A prova funciona mostrando que há uma máquina simples que pode usar (uma codificação de) o comprimento de uma string de entrada como parte de a seqüência de saída. Isso permite que a máquina gere uma cadeia relativamente longa usando uma entrada relativamente curta - porque a máquina usa o conteúdo da entrada e seu comprimento como fontes para construir a string de saída. Como eu vejo, tudo o que é necessário para este truque funcionar é que permitimos que as máquinas calculem comprimentos de cordas de entrada. Como parece-me que uma máquina livre de prefixo (com algum tipo de área de fita de trabalho) pode calcular o comprimento de uma entrada, isso tão facilmente quanto uma máquina simples, eu não vejo por que esse teorema não segura complexidade livre de prefixo também.

.

proposição. Há uma constante $ c $ com a seguinte propriedade. Para cada $ d \ in \ mathbb {n} $ e cada string $ W $ de comprimento pelo menos $ 2 ^ {D + 1} + D $ Há uma $ x \ preceq w $ tal que < span class="contêiner matemática"> $ c (x) \ leq | x | -d + c $ .

prova. [Elidident: referência à notação anterior de Def.] a máquina $ n $ é dado por

ner "> $ n (\ sigma)=mathsf {string} (| \ sigma |) \ sigma $ . É suficiente para obter um prefixo $ x $ de $ W $ com um recipiente de matemática $ N $ -description de Comprimento $ | x | -d $ . Deixe $ k=mathsf {number} (w \! \ Upharpoonright_d) $ (assim que $ k \ leq 2 ^ {d + 1} $ ), e deixe $ x= w \! \ upharpoonright_ { d + k} $ ser o prefixo de $ W $ com o comprimento dado por $ D + K $ onde $ k $ é o Número representado pela primeira $ D $ bits de $ W $ . Deixe $ \ sigma $ ser o string de comprimento $ k $ tal que $ x= x \! \ upharpoonright_d \ sigma $ , então $ n (\ sigma)= x $ . Assim, $ c_n (x) \ leq | x | -d $ .
(NIES 2009, p. 83)

notação: $ c $ : complexidade simples. $ | x | $ : Comprimento da string de bits $ x $ . $ x \ preceq w $ : $ x $ é um prefixo de recipiente de matemática $ W $ . $ \ mathsf {string} (n) $ : codificação do número natural $ n $ como uma seqüência de caracteres . $ \ mathsf {number} () $ : inversa de $ \ mathsf {string} () $ . (A alegação de que $ k \ leq 2 ^ {d + 1} $ segue a partir da definição de $ \ mathsf {número } $ .) $ \ mathsf {string} (| \ sigma |) \ sigma $ é a concatenação da $ \ mathsf {string} (| \ sigma |) $ e $ \ sigma $ . $ w \! \ upharpoonright_d $ : prefixo de $ w $ consistindo de sua primeira $ D $ bits. (Eu sou muito certo que é o que $ \ upharpoonright $ significa, mas a definição no pp. 12 e 16 é apenas 95% clara para mim. Minha interpretação de $ \ upharpoonright $ faz sentido nesta prova, e não consigo ver como qualquer outra interpretação faria sentido dado como é usado.)

Nota: "Dado por $ D + K $ onde $ k $ " na frase média da prova foi "dada por $ D + M $ onde $ m $ " no original; no original; Eu acredito " $ m $ " é um erro de digitação. ( $ m $ aparece em nenhum outro lugar nesta página, nem perto desta página.)

Answer 1

Responder a questão titular, a prova da proposição quebra para codificações livres de prefixo, já que $ \ sigma $ não pertence necessariamente ao prefixo-livre código.

Existem outras maneiras de ver que os programas livres de prefixo são mais bem comportados do que programas simples. Suponha que queremos concatenar a saída de dois programas $ p, Q $ . Com programas sem prefixo, podemos fazer um programa universal que executa dois programas de entrada e concatena suas saídas, por um comprimento total de $ | P | + | Q | + O (1) $ . Com programas simples, isso é impossível, uma vez que precisamos separar os dois programas $ p, q $ de alguma forma, digamos, codificando-os como recipiente de matemática $ \ mathit {len} (p) PQ $ , onde $ \ mathit {len} (p) $ é codificado usando uma auto-terminação codificação. Assim, temos que perder um termo aditivo de $ o (\ log \ min (| p |, | q |)) $ .