Quantos pares de suportes são suficientes para completar o Brainfuck Turing?
Brainfuck é uma linguagem de programação completa de Turing que usa apenas 8 símbolos (6 se você ignorar a E / S).
Os dois mais notáveis ​​que o empurram para a perfeição de Turing são [e ], essencialmente, o rótulo de Brainfuck.
Normalmente, os programas no Brainfuck usam vários conjuntos de [], mas eu queria saber exatamente quantos pares desses colchetes precisam ser usados ​​para completar o Brainfuck Turing?
Mais simplesmente, qual a menor quantidade de suportes que você precisaria para simular uma máquina de Turing de estado n (forneça o número de suportes para máquinas de Turing de 1, 2 e 3 estados)?
Estamos assumindo uma fita infinita e sem limites computacionais.
É uma máquina de Turing com 2 símbolos
"quantos pares desses colchetes precisam ser usados?" Você pode esclarecer "tem que ser usado". Por exemplo, e se eu pedir ao BrainF que conte até 2100000021000000 ?
@ Apass.Jack o número mínimo de colchetes
Oh, você quis dizer o número mínimo de suportes para simular um nn máquina de Turing -state em função do nn ? De qualquer forma, você pode dar um exemplo não trivial o mais simples possível?
@ Apass.Jack Ok, eu estou chegando com um programa de buggy BF, que trabalha para um de um estado Máquina de Turing
@ Apass.Jack Nevermind, é muito difícil para mim. Basicamente fazer um intérprete BF para minha linguagem de programação, Máquina de Turing Mas muito pior , quando se usa apenas dois símbolos possíveis (0 e 1) e remova o I / O e aspecto travar completamente
Este é um desenvolvimento adicional da resposta do @ ais523 , reduzindo-o para apenas dois conjuntos de colchetes e também usando uma colocação de célula mais compacta, baseada na teoria das réguas de Golomb. o ais523 criou um compilador para essa construção , bem como esta sessão TIO mostrando um exemplo de programa BF resultante em execução com rastreamento de depuração dos contadores TWM.
Como o original, isso começa com um programa em The Waterfall Model , com algumas restrições que não perdem generalidade:
Todos os contadores têm o mesmo valor de redefinição automática RR ; isto é, o mapa de gatilho TWMff tem a propriedade quef(x,x)=Rf(x,x)=R para todos osxx .
Há um único contador de parada hh .
O número cc dos contadores é (p−1)/2(p−1)/2 para algum número primo pp .
Régua de Golomb
Combinamos a construção Erdős – Turán com a função de permutação de um conjunto Welch – Costas para obter uma régua de Golomb com as propriedades necessárias.
(Tenho certeza de que essa construção combinada não pode ser uma idéia nova, mas acabamos de encontrar e encaixar essas duas peças da Wikipedia.)
Deixei rr uma raiz primitiva dep=2c+1p=2c+1 . Defina a função
gg é umaréguadeGolombda ordem2c2c . Ou seja, a diferençag(i)−g(j)g(i)−g(j) é única para cada par de números distintosi,j∈{0,…,2c−1}i,j∈{0,…,2c−1} .
g(k)mod(2c)g(k)mod(2c) assume todos os valores0,…,2c−10,…,2c−1 exatamente uma vez.
Para cada contador TWM x∈{0,…,c−1}x∈{0,…,c−1} , atribuímos duas posições de célula de fita BF, uma célula de fallback u(x)u(x) e umacélula de valor v(x)v(x) :
Pela segunda propriedade de gg existem exatamente dois valores distintos de k1,k2k1,k2 para você escolher.
O conteúdo de uma célula de fallback na maioria das vezes é mantido em 00 , exceto quando seu contador acaba de ser visitado, quando fica em 2R2R , duas vezes o valor de redefinição automática do contador. Uma célula de valor será mantida com o dobro do valor do contador TWM ​​correspondente.
Todas as outras células que podem ser alcançadas pela execução do programa BF (um número finito) serão mantidas em valores ímpares, para que sempre testem como diferente de zero. Após a inicialização, isso é automático, porque todos os ajustes das células são iguais.
Se desejado, todas as posições da célula podem ser deslocadas para a direita por uma constante, a fim de evitar mover para a esquerda da posição inicial da fita BF.
Estrutura do programa BF
Seja H=v(h)−u(h)H=v(h)−u(h) a distância entre o valor do contador de parada e as células de fallback, e seja NN um número grande o suficiente para que cN+1≥v((x+1)modc)−u(x)cN+1≥v((x+1)modc)−u(x) para todos os contadores xx . Então a estrutura básica do programa BF é
inicialização [ >×(H+cN+1)×(H+cN+1) [ <×c×c ] ajustes de <×H×H ]
A fase de inicialização define todas as células alcançáveis ​​pelo programa com seus valores iniciais, em um estado como se o último contador tivesse acabado de ser visitado e a célula apenas ativa fosse sua célula de fallback u(c−1)u(c−1) :
As células de valor são inicializadas com o dobro do conteúdo inicial do contador TWM ​​correspondente, exceto que o contador 00 é pré-decrementado.
As células de fallback são definidas como 00 , exceto a célula u(c−1)u(c−1) , que é definida como 2R2R .
Todas as outras células alcançáveis ​​pelo programa (um número finito) são definidas como 11 .
Em seguida, o ponteiro da fita é movido para a posição u(c−1)−Hu(c−1)−H (uma célula sempre diferente de zero) antes de chegarmos à primeira[ .
Início do loop externo
No início de uma iteração do loop externo, o ponteiro da fita estará em u(x)−Hu(x)−H ou v(x)−Hv(x)−H para um contador xx .
Seja y=((x+1)modc)y=((x+1)modc) o próximo contador a visitar.
O movimento >×(H+cN+1)×(H+cN+1) coloca o ponteiro fita numa posição que é ≡y(modc)≡y(modc) e não à esquerda dev(y)v(y) .
O loop interno [ <×c×c ] agora pesquisa para a esquerda nas etapas de cc uma célula zero. Se o contador yy for zero, ele irá parar na célula de valor (zero) v(y)v(y) ; caso contrário, encontrará a célula de fallback u(y)u(y) .
Qualquer célula encontrada se torna a nova célula ativa .
A fase de ajuste ajusta várias células da fita com base em sua posição em relação à célula ativa. Esta seção contém apenas+->< comandos e, portanto, esses ajustes ocorrem incondicionalmente. No entanto, como todas as células relacionadas ao contador estão em um padrão de régua de Golomb, qualquer ajuste que não seja apropriado para a célula ativa atual perderá todas as células importantes e ajustará alguma célula irrelevante (mantendo-a ímpar).
Assim, um código separado deve ser incluído no programa para cada possível par necessário de célula ativa e ajustada, exceto o auto-ajuste de uma célula ativa, que, porque o ajuste é baseado apenas na posição relativa, deve ser compartilhada entre todos eles.
Os ajustes necessários são:
Ajuste a célula de fallback do contador anterior u(x)u(x) em −2R−2R .
Ajuste a célula de fallback do contador atual u(y)u(y) em 2R2R , exceto se a célula ativa atual for v(h)v(h) e, portanto, devemos parar.
Ajuste a célula de valor do contador seguinte v((y+1)modc)v((y+1)modc) por −2−2 (diminuindo o contador).
Quando a célula ativa for uma célula de valor v(y)v(y) (para que o contador yy tenha atingido zero), ajuste todas as células de valor v(z)v(z) por 2f(y,z)2f(y,z) no mapa de acionamento do TWM. v(y)v(y) é ajustado em 2R2R .
O primeiro e o segundo ajustes acima são necessários porque todas as células ativas devem se ajustar pelo mesmo valor, que é 2R2R para células de valor e, portanto, também para células de fallback. Isso requer a preparação e a limpeza das células de fallback para garantir que elas voltem a 00 nas ramificações de valor e de fallback.
Fim do loop externo
O movimento <×H×H representa que, no final da fase de ajuste, o ponteiro da fita é movido HH para a esquerda da célula ativa.
Para todas as células activas outras que não as células valor do contador suspensão v(h)v(h) , esta é uma célula irrelevante, e por isso estranho e diferente de zero, e a espira externa continua para outra iteração.
Para v(h)v(h) , o ponteiro é colocado em sua célula de fallback correspondente u(h)u(h) , para a qual fizemos uma exceção acima para mantê-la zero e, portanto, o programa sai pela final ]e pára.
Não tenho 100% de certeza de que é impossível fazer isso com dois conjuntos de colchetes. No entanto, se as células da fita BF permitirem valores ilimitados, três conjuntos de colchetes serão suficientes. (Por uma questão de simplicidade, também assumirei que podemos mover a cabeça da fita para além do ponto de partida, embora, como essa construção use apenas uma região finita da fita, possamos levantar essa restrição adicionando muitos >comandos no início do processo. programa.) A construção abaixo requer assumir a conjectura de Artin a capacidade de compilar programas arbitrariamente grandes; no entanto, mesmo que a conjectura de Artin seja falsa, ainda será possível mostrar a completude de Turing indiretamente através da tradução de um intérprete para um idioma completo de Turing em BF usando a construção abaixo,
A linguagem Turing-completa que estamos compilando no BF ilimitado é The Waterfall Model , que é um dos modelos computacionais mais simples conhecidos. Para pessoas que ainda não o conhecem, consiste em vários contadores (e valores iniciais para eles) e uma função ff de pares de contadores a números inteiros; a execução do programa consiste em subtrair repetidamente 1 de cada contador e, se qualquer contador xx for 0, adicionar f(x,y)f(x,y) a cada contador yy(o programa é escrito de tal maneira que isso nunca acontece com vários contadores simultaneamente). Há uma prova de completude de Turing para esse idioma por trás do meu link. Sem perda de generalidade, assumiremos que todos os contadores têm o mesmo valor de redefinição automática (ou seja, f(x,x)f(x,x) é o mesmo para todos os xx ); essa é uma suposição segura, pois para qualquer xx específico , adicionar a mesma constante a cada f(x,y)f(x,y) não mudará o comportamento do programa.
Seja pp o número de contadores; sem perda de generalidade (assumindo que a conjectura de Artin), supor que pp tem um primitivo raiz 2. Seja qq ser p(1+s+s2)p(1+s+s2) , onde ss é o nível mínimo de potência de 2 maior do que pp . Sem perda de generalidade, 2q2q será menor que 2p2p ( 2q2q é delimitado polinomialmente, 2p2p cresce exponencialmente, portanto, qualquer pp suficientemente grande funcionará).
O arranjo da fita é o seguinte: numeramos cada contador com um número inteiro 0≤i<p0≤i<p (e sem perda de generalidade, assumimos que existe um único contador de parada e o número 22 ). O valor da maioria dos contadores é armazenado na célula de fita 2i2i , com exceção do contador 0, que é armazenado na célula de fita 2q2q . Para cada célula de fita de número ímpar da célula -1 até 2 p + 1 + 2 p + 1 inclusive2p+1+2p+12p+1+2p+1, essa célula de fita sempre mantém 1, a menos que esteja imediatamente à esquerda de um contador; nesse caso, sempre mantém 0. As células de fita com números pares que não estão sendo usadas como contadores têm valores irrelevantes (que podem ou não ser 0 ); e as células de fita de número ímpar fora do intervalo indicado também têm valores irrelevantes. Observe que configurar a fita em um estado inicial apropriado requer a inicialização de apenas finitos elementos da fita em valores constantes, o que significa que podemos fazê-lo com uma sequência de <>+-instruções (na verdade, >+são necessárias apenas ), portanto, sem colchetes. No final desta inicialização, movemos o ponteiro da fita para a célula -1.
A forma geral do nosso programa terá a seguinte aparência:
inicialização [>>>[ >× ( 2p- 1 )×(2p-1) [ <×(2p)×(2p) ]>-] adjustment <<<]
The initialisation puts the tape into the expected shape and the pointer on cell -1. This is not the cell to the left of a counter (0 is not a power of 2), so it has value 1, and we enter the loop. The loop invariant for this outermost loop is that the tape pointer is (at the start and end of each loop iteration) three cells to the left of a counter; it can be seen that the loop will thus only exit if we're three cells to the left of counter 2 (each other counter has a 1 three cells to its left, as to have a 0 there would imply that two counters' tape positions were 2 cells apart; the only two powers of 2 that differ by 2 are 2121 and 2222, and qq's binary representation changes from strings of 00s to strings of 11s or vice versa at least four times and thus cannot be 1 away from a power of 2).
The second loop repeatedly loops over the counters, decrementing them. The loop invariant is that the tape pointer is always pointing to a counter; thus the loop will exit when some counter becomes 0. The decrement is just -; the way we get from one counter to the next is more complex. The basic idea is that moving 2p−12p−1 spaces to the right from 2x2x will place us on an odd-numbered cell 2p+2x−12p+2x−1, which is to the right of any counter (2p2p is the last counter, 2x−12x−1 is positive because xx is positive); modulo 2p2p, this value is congruent to (by Fermat's Little Theorem) 2x+12x+1. The innermost loop repeatedly moves left by 2p2p spaces, also not changing the index of the tape cell modulo 2p2p, and must eventually find the cell congruent to 2x+12x+1 modulo 2p2p that has the value (which will be the cell to the left of some counter); because of our primitive root requirement there's exactly one such cell (2q−12q−1 is congruent to −1−1 modulo 2p2p, and 2log2,p(r)+1−12log2,p⁡(r)+1−1 is congruent to 2r−12r−1 for any other rr, where log2,plog2,p is the discrete logarithm to base 2 modulo pp). Additionally, it can be seen that the position of the tape pointer modulo 2p2p increases by 22 each time round the middle loop. Thus, the tape pointer must cycle between all pp counters (in order of their values modulo 2p2p). Thus, every pp iterations, we decrease every counter (as required). If the loop breaks partway through an iteration, we'll resume the decrease when we re-enter the loop (because the rest of the outermost loop makes no net change to the tape pointer position).
When a counter does hit 0, the middle loop breaks, taking us to the "adjustment" code. This is basically just an encoding of ff; for every pair (x,y)(x,y), it adds f(x,y)f(x,y) to the tape element which is the same distance left/right of the current tape pointer as counter yy's tape location is left/right of counter xx's tape location (and then removes the tape pointer back to where it started). Whenever x≠yx≠y, this distance turns out to be unique:
The difference between two powers of 2 is a binary number consisting of a string of 1 or more 11s followed by a string of 0 or more 00s (with the place values of the start of the number, and the start of the 00 string, depending on the larger and smaller respectively of xx and yy); thus all those differences are distinct. * As for the difference of a power of 2 and qq, it must contain at least two transitions between strings of 11s and 00s (qq contains at least four such transitions, the subtraction can only remove 2), thus is distinct from all differences of two powers of two, and these differences are obviously also distinct from each other.
For x=yx=y, we obviously find that the distance moved is 0. But because all f(x,y)f(x,y) are equal, we can just use this as the adjustment for the current cell. And it can be seen that the adjustment code thus implements the "when a counter hits 0" effect for every counter; all the cells that actually represent counters will be adjusted by the correct amount, and all the other adjustments will affect non-counter even-numbered cells (the difference between two even numbers is even), which have no effect on the program's behaviour.
Nice job! I see you worked on this in TNB!
I think you need s to be at least p+2. When s=p+1, q is 1 less than a power of 2.
I think I found a much simpler (as in requiring no prime number theory) counter placement: 2p*2^i+2i.
@ØrjanJohansen: Right, I think I mentioned that construction in #esoteric (some time after I wrote this post)? All you actually need is a Golomb ruler for which each element is distinct modulo the number of elements, and there are various ways to construct those (although finding optimal ones is hard; the longest I've found (via brute force) is [0, 1, 3, 7, 20, 32, 42, 53, 58] for p=9).
Oh so you did (just before I said my brain refused to be in math mode, so there's my excuse :P). I guess I found out k=0 was sufficient, then. I think Wikipedia's Erdős–Turan_construction gives a polynomially growing (and presumably O()-optimal?) one if you use just the first half of the elements (the other half repeats (mod p)).