Quais são os exemplos mais simples de programas que não sabemos se eles terminam?

27

O problema de parada afirma que não há algoritmo que determine se um determinado programa é interrompido. Como conseqüência, deve haver programas sobre os quais não podemos dizer se eles terminam ou não. Quais são os exemplos mais simples (menores) conhecidos de tais programas?

MaiaVictor
fonte
Você está contradizendo suas respostas ..... Obrigado! Mas o programa de interrupção pressupõe conhecimento da fonte. ... Se isso for verdade, você respondeu sua pergunta. O programa de interrupção já saberia. Imagine um sistema controlando um sinal, sempre iluminado e intermitente, quando é desligado? Falha de energia, botão liga / desliga ou durante a sequência do flash. Ou com um backup e gerador de bateria, nunca.
Htm11h 30/07/2015
Eu acrescentaria que o problema de parada é apenas um problema se você não colocar um limite superior de tempo. Certamente, não há diferença na prática entre receber uma resposta tarde demais para ser útil e nunca obter uma resposta. Você pode perguntar se um programa retornará uma resposta em várias etapas, como uma definição de correção em tempo real. Se você não pode garantir uma resposta oportuna, simplesmente tem um programa que não possui garantia de correção.
30715 Rob
11
@ Rob Isso não é verdade. Se você não sabe se uma máquina irá parar, pode esperar indefinidamente para ver se ela pára; depois de um milênio, você ainda não saberá se ele vai parar ou não, digamos, no dia seguinte.
Kyle Strand
@KyleStrand Estou de acordo com você. Mas também estou dizendo que é uma questão totalmente exagerada na prática, porque todos os cálculos realistas estão sujeitos a prazos (milissegundos a meses). Se você precisar de uma resposta em 5 segundos para que seja útil, a única coisa importante é se você pode garantir uma resposta em 5 segundos. Suponha que você possa garantir uma resposta com uma quantidade indeterminada de tempo para calcular. Isso seria uma garantia inútil.
Rob

Respostas:

41

Um exemplo bastante simples pode ser um programa testando a conjectura de Collatz :

f(n)={HALT,if n is 1f(n/2),if n is evenf(3n+1),if n is odd

Sabe- se que para até pelo menos , mas em geral é um problema em aberto.n5×2605.764×1018

npostavs
fonte
9
Para enfatizar meu argumento a partir do comentário abaixo da pergunta: o problema " pára para todos os ?" é computável . nf(n)n
Raphael
6
@KyleStrand Veja aqui .
Raphael
10
@KyleStrand, Raphael está 100% correto. Este é um equívoco comum. Você deve seguir o que a definição diz com muito cuidado e descobrir que sua intuição não corresponde exatamente à definição. De acordo com a definição de computabilidade, basta que exista uma máquina de Turing para computá-la - não importa se sabemos o que é essa máquina de Turing. Ao ver isso pela primeira vez, muitos alunos pensam que é trapaça, mas não é - isso é apenas uma consequência da definição.
DW
2
@KyleStrand Você precisa se livrar da ideia de que o programa precisa resolver o problema . Isso não. Ele apenas precisa fornecer a resposta, que é uma tarefa trivial. Algoritmicamente, os problemas com conjuntos finitos de instâncias são todos chatos, pois podemos codificar as respostas. (E mesmo que não saibamos as respostas, ainda sabemos que existe um algoritmo correto.) Em geral, ao mostrar que não há algoritmo para algo, você não pode fazer nenhuma suposição sobre como isso vai acontecer. trabalhos. Nossa falta de imaginação não fornece uma prova.
Raphael
2
@KyleStrand Afaik, eu uso a definição padrão de computabilidade como é ensinada hoje (e, afaik, tem sido há décadas). Eu recomendo que você absorva as respostas e o material vinculado e descubra onde errou. Não faz sentido para mim e outras pessoas repetir as mesmas coisas repetidamente. Mais uma tentativa: a definição de computabilidade é inerentemente existencial, não construtiva. Desde que você pense dentro dos domínios da lógica clássica, não há necessidade de poder entregar um algoritmo de "solução" - apenas temos que mostrar que existe um que dê as respostas certas.
Raphael
31

O problema de parada afirma que não há algoritmo que determine se um determinado programa é interrompido. Como conseqüência, deve haver programas sobre os quais não podemos dizer se eles terminam ou não.

"Nós" não é um algoritmo =) Não existe um algoritmo geral que possa determinar se um determinado programa é interrompido para cada programa .

Quais são os exemplos mais simples (menores) conhecidos de tais programas?

Considere o seguinte programa:

n = 3
while true:
    if is_perfect(n):
            halt()
    n = n + 2

A função is_perfect verifica se n é um número perfeito . Não se sabe se existem números perfeitos ímpares, por isso não sabemos se este programa é interrompido ou não.

avsmal
fonte
7
Nós somos um algoritmo.
PyRulez
3
@PyRulez, não há provas de que o poder computacional da mente humana seja equivalente à Turing Machine. A prova não funciona, por exemplo, não se sabe como simular uma mente em outra.
avsmal
11
@ avsmal Ok, mas é extremamente improvável que sejamos capazes de hipercomputação.
PyRulez 01/08/2015
2
@PyRulez John Lucas e Roger Penrose sugeriram que a mente humana pode ser o resultado de algum tipo de computação "não-algorítmica" aprimorada mecanicamente. Essa é uma suposição forte. Mas pelo menos nossa mente pode ter alguma fonte de incerteza. E isso é suficiente para quebrar a prova: é impossível negar a Máquina de Turing "aleatória" (para alguma definição adequada do que significa aleatoriamente), se não se sabe se ela pára.
avsmal
5
A computação quântica é considerada hipercomputação? Presumi que computadores quânticos pudessem ser perfeitamente simulados por máquinas de turing - apenas um pouco mais devagar.
MaiaVictor
10

Você escreve:

O problema de parada afirma que não há algoritmo que determine se um determinado programa é interrompido. Como conseqüência, deve haver programas sobre os quais não podemos dizer se eles terminam ou não.

Este é um não sequitur, em ambas as direções. Você sucumbe a uma falácia comum que vale a pena abordar.

Dado qualquer programa fixo , seu problema de parada (" sempre pára?") É sempre decidível, porque a resposta é "sim" ou "não". Mesmo que você não saiba qual é, você sabe que um dos dois algoritmos triviais que respondem sempre "sim" resp. "no" resolve o problema de asfalto- .P PPPP

Somente se você exigir que o algoritmo resolva o problema de parada para todos os programas você poderá mostrar que esse algoritmo não pode existir.

Agora, saber que o problema da parada é indecidível não implica que existam programas dos quais ninguém possa provar o término ou o loop. Mesmo se você não for mais poderoso que uma máquina de Turing (que é apenas uma hipótese, não um fato comprovado), tudo o que sabemos é que nenhum algoritmo / pessoa pode fornecer essa prova para todos os programas. Pode haver uma pessoa diferente sendo capaz de decidir para cada programa.

Algumas leituras mais relacionadas:


Portanto, você vê que sua pergunta real (conforme repetida abaixo) não tem nada a ver com se o problema da parada é computável. Em absoluto.

Quais são os exemplos mais simples (menores) conhecidos de [programas que não sabemos interromper ou repetir]?

Isso por si só é uma pergunta válida; outros deram boas respostas. Basicamente, você pode transformar cada declaração com valor de verdade desconhecido em um exemplo, desde que ele tenha um valor de verdade:S

g(n)={1,S true,g(n+1),else.

Concedido, estes não são muito "naturais".


  1. Não necessariamente todos , mas "muitos" em algum sentido. Infinitamente muitos, pelo menos.
Rafael
fonte
Comentários não são para discussão prolongada; esta conversa foi movida para o bate-papo .
Raphael
Para tentar reformular isso para meu próprio entendimento, é correto dizer que, embora não haja um algoritmo exclusivo que possa determinar se algum programa arbitrário é interrompido, é possível que exista algum algoritmo específico para resolver o problema de interrupção de todos os programas possíveis?
Asad Saeeduddin
@AsadSaeeduddin É "pior": para cada conjunto finito de programas, o problema da parada é trivial . Todo conjunto finito é decidível.
Raphael
7

Qualquer problema em aberto referente à existência de um número com propriedades particulares dá origem a esse programa (aquele que procura por esse número). Por exemplo, considere a conjectura de Collatz; como não sabemos se é verdade, também não sabemos se o seguinte programa termina:

    n:=1;
    found:=false;
    while not found do
      s:={};
      i:=n;
      while i not in s do
        add i to s;
        if i even then i:=i/2 else i:=3i+1
      if 1 not in s then found:=true;
      n:=n+1  
Klaus Draeger
fonte
6

Dado que o problema do Busy Beaver não foi resolvido para uma máquina de Turing com 5 estados e 2 símbolos, deve haver uma máquina de Turing com apenas cinco estados e apenas dois símbolos que não foram mostrados para parar ou não quando iniciados para uma fita vazia . Esse é um programa muito curto, conciso e fechado.

não usuário
fonte
0

a pergunta é complicada porque a decidibilidade (a formalização / generalização equivalente ao CS do problema de interrupção) está associada aos idiomas; portanto, ela precisa ser reformulada nesse formato. isso parece não ser muito apontado, mas muitos problemas abertos em matemática / CS podem ser facilmente convertidos em problemas (idiomas) de decidibilidade desconhecida. isto é devido a uma correspondência estreita entre prova de teoremas e análise de (in) decidibilidade. por exemplo (um pouco como a outra resposta em números ímpares perfeitos), considere a conjectura de primos gêmeos que data dos gregos (mais de 2 milênios atrás) e está sujeita a importantes avanços recentes de pesquisa, por exemplo, de Zhang / Tao. converta-o em um problema algorítmico da seguinte maneira:

Entrada: n . Saída: S / N, existem pelo menos n primos gêmeos.

o algoritmo procura primos gêmeos e pára se encontrar n deles. não se sabe se esse idioma é decidível. a resolução do problema dos primos gêmeos (que pergunta se existe um número finito ou infinito) também resolveria a decidibilidade dessa linguagem (se também for comprovado / descoberto quantos existem, se finitos).

outro exemplo, pegue a hipótese de Riemann e considere esta linguagem:

Entrada: n . Saída: S / N existem pelo menos n zeros não triviais da função zie de Riemann.

o algoritmo procura por zeros não triviais (o código não é especialmente complexo, é semelhante à descoberta de raízes e existem outras formulações equivalentes que são relativamente simples, que basicamente calculam somas de "paridade" de todos os números primos menores que x etc) e param se encontra n deles e, novamente, não se sabe se essa linguagem é decidível e a resolução é "quase" equivalente a resolver a conjectura de Riemann.

agora, que tal um exemplo ainda mais espetacular? ( ressalva, provavelmente mais controversa também)

Entrada: c: Saída: S / N existe um algoritmo O (n c ) para SAT.

da mesma forma, a resolução da decidibilidade dessa linguagem é quase equivalente ao problema P vs NP . no entanto, há um caso menos óbvio para o código "simples" para o problema nesse caso.

vzn
fonte
11
O downvoter explicaria o que há de errado com esta resposta?
MaiaVictor
2
NnNNa,b,can+bn=cnnN=2
precisa saber é o seguinte
3
Não sou a favor do voto negativo, mas todas as reivindicações nesta resposta estão erradas. Todos esses três problemas são comprovadamente decidíveis (sem a necessidade de fazer suposições não comprovadas). Por que, estude a resposta de Raphael de perto.
DW
ok, talvez a entrada precise ter a TM especificada e o algoritmo decida se a TM calcula o problema. tenho que pensar mais ... acho que existe uma receita simples para esses tipos de problemas, basicamente conectando problemas abertos a idiomas indecidíveis ... mas concordamos que isso raramente é documentado / formulado nas referências de CS ... só encontramos alguns dispersos refs ... ou talvez a entrada seja uma prova e o idioma verifique se a prova está correta ... as outras respostas com alta votação mencionam números ímpares perfeitos, problema de collatz etc ... os programas são desconhecidos para parar ou não para constantes específicas .
vzn
Desculpe pela confusão! em alguma reflexão adicional, as asserções estão corretas na forma em que descrevem programas simples que não se sabe terminar (para todas as entradas) (isto é, a pergunta original) e a falha da idéia geral esboçada / apontada pela DW está tentando converter cada uma delas em idiomas indecidíveis. continuará a ponderar sobre essa última idéia de construção, procurando uma que seja bem-sucedida. Outra maneira de ver isso é que os problemas podem ser vistos como instâncias / entradas individuais para um solucionador de problemas de interrupção, mas não realmente (conhecido por) equivalente ao próprio problema de parada.
vzn
0

1n1050

1020

gnasher729
fonte