O que são programas muito curtos com status de interrupção desconhecido?

32

Este programa de 579 bits no Cálculo lambda binário possui um status de parada desconhecido:

01001001000100010001000101100111101111001110010101000001110011101000000111001110
10010000011100111010000001110011101000000111001110100000000111000011100111110100
00101011000000000010111011100101011111000000111001011111101101011010000000100000
10000001011100000000001110010101010101010111100000011100101010110000000001110000
00000111100000000011110000000001100001010101100000001110000000110000000100000001
00000000010010111110111100000010101111110000001100000011100111110000101101101110
00110000101100010111001011111011110000001110010111111000011110011110011110101000
0010110101000011010

Ou seja, não se sabe se este programa termina ou não. Para determiná-lo, você deve resolver a conjectura de Collatz - ou, pelo menos, para todos os números de até 2 ^ 256. Neste repositório, há uma explicação completa de como este programa foi obtido.

Existem programas BLC (muito) mais curtos que também têm status de interrupção desconhecido?

MaiaVictor
fonte
6
Pergunta muito relacionada . Votos da comunidade, por favor: duplicado?
Raphael
9
A tarefa de expressar esse programa no menor número possível de bits parece ser uma questão do Code Golf , menos da ciência da computação .
Raphael
2
Acho que a resposta de Ricky sobre as TMs de 5 estados é melhor do que a da pergunta original. Se este estiver fechado como um idiota, a resposta pode ser movida?
precisa saber é o seguinte
6
Está faltando um detalhe importante: você não especificou em qual idioma o programa deve ser escrito. Seu exemplo usa cálculo lambda binário - esse é o único idioma em que você está interessado? Podemos ver que é trivial desenvolver um programa de 1 bit com status de interrupção desconhecido, simplesmente incorporando o corpo do algoritmo diretamente à própria linguagem. É uma brecha, mas é preciso prestar atenção ao pedir soluções de golfe. Eles amam suas brechas! A complexidade de Kolmogov pode ser um tópico importante a ser explorado aqui.
Cort Ammon - Restabelece Monica

Respostas:

30

Sim. Esta página diz que há 98 5-state máquinas de Turing cujo status de parada são desconhecidos. Irritantemente, ele não fornece exemplos de tais máquinas, mas esta página de 26 anos fornece 2 máquinas de Turing de 5 estados cujos status de parada eram aparentemente desconhecidos na época. (A pesquisa de "contador simples" levará você entre os 2.). Eu os copiei aqui, caso o link seja desativado:

Input Bit   Transition on State     Steps            Comment
             A   B   C   D   E

    0       B1L C1R D0R A1L H1L   > 2*(10^9)       ``chaotic''
    1       B1R E0L A0L D0R C0L

    0       B1L A0R C0R E1L B0L       ?        complex ``counter''
    1       A1R C0L D1L A0R H1L

fonte
A parte inferior da página diz: $ Date: 2007/11/03, então como ele tem 26 anos?
Falaque 8/06/16
1
@Falaque O topo da página indica "Esta página é a reescrita em HTML do autor de ... fevereiro de 1990". O texto tem 26 anos, a renderização em HTML é de (ou foi atualizada pela última vez) em 2007.
IMSoP
5

Conjectura de Collatz:

O seguinte programa sempre pára:

void function( ArbitraryInteger input){
     while( input > 1){
            if(input % 2 == 0)
                input /= 2;
            else
                input = (input*3) + 1;
     }

     // Halt here
}

Pequena variação (ainda uma conjectura, porque se baseia em um resultado da de Collatz):

Para algumas entradas, o programa a seguir nunca entrará no mesmo estado duas vezes (onde o estado é determinado pelo valor mantido por "entrada"):

void function( ArbitraryInteger input){
     while( input >= 1){ // notice the "="
            if(input % 2 == 0)
                input /= 2;
            else
                input = (input*3) + 1;
     }
}

Observe que o segundo programa nunca pára, independentemente de o primeiro programa parar ou não.

Acredita-se que o primeiro programa sempre termine para qualquer entrada, no entanto, não temos a prova disso, e ainda pode existir algum número inteiro para o qual o programa não seja interrompido (também há um prêmio de US $ 100 por prová-lo) .

O segundo programa também é interessante: afirma que o programa nunca entrará no mesmo estado duas vezes para alguma entrada, o que basicamente exige que o primeiro programa tenha uma sequência conhecida por divergir sem repetir. Não requer apenas que a conjectura de Collatz seja falsa, mas exige que ela seja falsa e sem loops , além do óbvio loop 1,4,2,1.

  • Se Collatz tiver apenas contra-exemplos em loop, a variação na conjectura é falsa

  • Se Collatz é falso sem loops, a variação na conjectura é verdadeira

  • Se Collatz for verdadeiro, a variação é falsa

  • Se Collatz é falso, porque possui loops e porque possui um número para o qual diverge, a variação na conjectura é verdadeira (apenas requer um número para o qual diverge sem inserir um loop)

Acho que a variação é mais interessante (não apenas porque a encontrei por acidente e a notei graças a @LieuweVinkhuijzen), mas porque na verdade exige uma prova real. Por força bruta, podemos encontrar um loop um dia ou outro (e esse será um loop com mais de 70 números: o estado da arte atual é que não pode haver loops infinitos menores que 68 ou mais) e brute forçar não é interessante: é apenas trituração de números. No entanto, não podemos forçar brutalmente uma sequência divergente infinita, não sabemos se realmente terminará sem uma prova real.

Edição: Eu pulei a parte sobre Collatz Conjecture desculpe, eu realmente respondi de cor com um algoritmo que li sobre alguns anos atrás, eu não esperava que isso já fosse mencionado.

EDIT2: Um comentário me fez notar que eu escrevi o algoritmo com um erro, no entanto, esse erro realmente torna minha resposta diferente da conjectura de Collatz (mas uma variação direta dele).

Desenvolvedor de jogos
fonte
1
input > 1input >= 11421
Você está certo, eu queria colocar um >, no entanto, desde que não tenhamos uma prova de interrupção >, não podemos ter certeza de que alcançaremos o 1 -> 4 -> 2 -> 1loop (por exemplo, se ele não terminar por >isso, t alcançar >=)
GameDeveloper 7/16
1
> =14211421> =>
2
n<1n=1n4n>1n11
1
Isso é verdade :) Você está certo, eu deveria ter acrescentado 'se a conjectura de Collatz for verdadeira' ao meu primeiro comentário. Eu vejo sua edição, muito boa. Você não precisa do segundo programa, porque a conjectura 'este programa nunca entra no mesmo estado duas vezes' também não foi resolvida no primeiro programa: é possível que exista um número que não desvia para o infinito, mas fica preso em um loop grande em algum lugar em números muito altos.
Lieuwe Vinkhuijzen