Resolva parcialmente o problema de parada do brainf ***

Para resolver o problema da parada, você recebe uma descrição de um programa e deve determinar se ele terminará ou não. Você nunca pode fazer isso em todos os programas. No entanto, para programas como (no brainf *** ):

>

Obviamente, ele será interrompido e para programas como:

+[]

Obviamente não. Seu desafio é "resolver" o problema da interrupção para o maior número possível de programas. Esses programas não usarão .ou ,não terão entrada ou saída. Você receberá uma descrição do programa e deve gerar "Paradas", "Não pára" ou "Desconhecido". Quando o seu programa gera "Paradas" ou "Não pára", você resolveu o programa de entrada. Aqui estão alguns requisitos.

1. Ele deve resolver pelo menos uma quantidade infinita de programas.
2. Para cada programa que resolve, sua solução deve estar correta.
3. Você só pode enviar 1 das 3 opções acima.
4. Você pode assumir que o computador em execução possui tempo e memória infinitos, portanto o XKCD 1266 não funcionaria (a fita é ilimitada).
5. Nenhum recurso externo.
6. Você não pode usar uma linguagem de programação que possa realmente resolver o problema de parada .

Você pode ter um programa paralelo sem código que pega uma string que é um programa e gera algum tipo de árvore de sintaxe abstrata, se desejar. Observe que isso não é realmente uma pontuação propriamente dita, mas como determinar se um programa supera outro.

1. Se o programa A resolve um número infinito de programas que B não faz, mas B resolve apenas programas finitos ou inexistentes que A resolve, A vence automaticamente.
2. Caso contrário, o programa com o menor número de caracteres vence. Não conte espaços em branco ou comentários; portanto, não ofusque seu código.

Dica: os temporizadores não funcionam. Você vê, para qualquer momento T e para uma determinada máquina, existe um N, de modo que todos os programas mais longos que esse precisam levar mais que T tempo. Isso significa que um timer só pode alcançar a solução de um número finito de programas e, como você pode ver acima, resolver um número finito de programas não ajuda.

Python, código de espaguete ungolfed

Oh céus.

def will_it_halt(instructions):
    tape_length = 1
    LOOP_BOUND = 1000
    registry = [0] * tape_length
    pos = 0

    jumpbacks = []
    reached_states = set()

    pos_instructions = 0
    while True:
        letter = instructions[pos_instructions]
        if letter == "+":
            registry[pos] = (registry[pos] + 1) % 256
        elif letter == "-":
            registry[pos] = (registry[pos] - 1) % 256
        elif letter == ">":
            pos += 1
            if pos >= tape_length:
                registry += [0]*tape_length
                tape_length = len(registry)
        elif letter == "<":
            pos -= 1
            if pos <= 0:
                registry = [0]*tape_length+registry
                tape_length = len(registry)
                pos += tape_length
        elif letter == "[":
            if registry[pos] == 0:
                nests = 1
                while nests:
                    pos_instructions += 1
                    if instructions[pos_instructions] == "[": nests += 1
                    elif instructions[pos_instructions] == "]": nests -= 1

                if jumpbacks == []:
                    reached_states.clear()

            else:
                jumpbacks.append(pos_instructions-1)

        elif letter == "]":
            stripped_registry = [str(x) for x in registry if x != 0]
            translated_pos = pos - (len(registry) - len(stripped_registry))
            state = (translated_pos, pos_instructions, ".".join(stripped_registry))
            if state in reached_states: return "Does not halt"
            elif len(reached_states) > LOOP_BOUND: return "Unknown"
            else:
                reached_states.add(state)
                pos_instructions = jumpbacks.pop()
        pos_instructions += 1
        if pos_instructions >= len(instructions): break
    return "Halts"

Solução bastante forte para o problema: basta executar o código bf. Assumimos que o comprimento da fita é arbitrariamente longo e que células individuais são agrupadas em 256. No final de cada loop, armazenamos o estado da fita com um conjunto. Os estados têm a forma (nossa posição na fita, nossa posição nas instruções, como a fita se parece com os zero retirados).

Se armazenarmos o mesmo estado duas vezes, estaremos em algum lugar de um loop infinito, para que o programa não pare. Se armazenarmos mais de 1.000 estados, reduzimos as perdas e retornamos desconhecidos. Quando deixamos um loop, verificamos se não estamos em loops maiores. Caso contrário, nunca mais veremos nenhum dos estados anteriores (no mínimo, a posição da instrução será sempre diferente!) Para que possamos limpar o conjunto de estados.

Isso deve determinar com precisão qualquer programa BF cujo loop não exceda 1.000 iterações, bem como muitos programas que repetem um estado antes de 1.000 iterações em um loop. Porém, nem todos: algo como "{1 milhão + está aqui} [-]> + [+ -]" eventualmente repete um estado, mas o loop [-] passa 1.000 iterações primeiro.

Alguns exemplos:

>+>->+>-

Sem loops, então chega ao fim e pára.

+[+]

O loop termina após 256 iterações, então atinge o final e pára.

+[+-]

Eventualmente, repete o estado (0,5, "1"), para que ele não pare.

+[->+]

Isso não repete nenhum estado, mas o loop nunca termina e, portanto, deve ser impresso "desconhecido". Mas o tipo de programa engana aqui. Em vez de armazenar a posição na fita, ela adiciona um deslocamento entre o registro original e o removido. Se tudo o que um loop faz é converter a fita em alguns espaços, ela continuará a traduzi-la indefinidamente (como um planador vitalício), para que possamos dizer que não pára.

+[>+]

Não traduz, não repete nenhum estado, imprime desconhecido.

+++++++++++[-]

Isso é interrompido, mas seria impresso "desconhecido" se LOOP_BOUND fosse 10.

Existem algumas maneiras de tornar isso mais inteligente. Obviamente, você pode aumentar LOOP_BOUND para reduzir o número de incógnitas. Você poderia ter uma manipulação mais inteligente de loops aninhados. Você provavelmente poderia fazer algo sofisticado com números BB e o tamanho de loops para detectar melhor se algo deveria parar, mas eu não sou bom o suficiente no CS nem no Python para poder fazer isso ainda.

GolfScript (23 caracteres, infinitas respostas corretas)

'[]'&!
# 0 if there are brackets, so Unknown
# 1 if there are no brackets, so no looping, so definitely halts
'UnknownHalts'7/=

Awk

Uma pequena extensão de poder dos dois exemplos. Se um programa não contém loops, portanto não há decisões, ele ainda está obviamente determinado a interromper. Como estamos assumindo a validade do programa, também assumimos que os colchetes estão equilibrados e, portanto, precisamos procurar apenas um ou outro dos colchetes.

BEGIN{RS=""}
!/\[/{print "Halts"; exit}
END{print "Unknown"}

No segundo, ele deve verificar primeiro se o loop é executado, portanto devemos simular o código linear que precede o loop. Então, se o loop retornar à mesma célula (ou seja, número de >s é igual ao número de <s dentro do loop) e ele não executar incs ou decs nessa célula (ou seja, para qualquer prefixo balanceado em posição do balanceado) corpo do loop, não há instâncias do +ou -antes do próximo <ou >, então, a célula não é modificada). A implementação desta parte pode levar mais tempo. Ooh, espere, para a primeira parte de verificar se o loop é executado, podemos ter essa mesma idéia e pesquisar no programa pré-loop por sufixos balanceados e insistir para que exista um +ou -(desequilibrado).

Haskell

Aqui está um exemplo de resposta realmente simples. Sinta-se à vontade para incluí-lo em suas respostas (uma vez que você inclui vários testes em uma resposta).

main=do
    p<-getLine
    if take 3 p == "+[]"
        then putStr "Does not halt"
        else putStr "Unknown"

Basicamente, ele vê se existe um loop no começo. Se esse loop exato não ocorrer no início, ele simplesmente desiste. Nem funciona ++[]. Porém, ele resolve um número infinito de programas e sempre está correto quando o resolve.