Comment vérifier si un programme se termine?

Y at-il une règle générale qui peut être utilisée pour déterminer cela? E.g:Comment vérifier si un programme se termine?

int i = 10; 
while (i > 1) { 
    if (i%2 == 0) i = i/2; 
    else i = 3*i - 1; 
}

Source

2010-09-26 fastcodejava

Il est intéressant de noter que ce programme particulier fonctionnera pour toujours. Puisque '3i-1' est plus grand que' i' pour tout 'i> 0', cela augmentera toujours la valeur. Et la seule façon d'obtenir 0 à partir d'une opération 'i/2' (pour' i> 0') est de commencer par 'i == 1'. Et si 'i == 1', vous n'utiliserez pas la ligne' i = i/2' puisque 'i' est impair. La conjecture de collatz devrait commencer 'while (i> 1)' plutôt que 0. – paxdiablo

@paxdiablo Modifié en 'while (i> 1)' – fastcodejava

'i% 2' est 0 quand' i' est pair, 1 quand 'i' est impair, donc la ligne 'i = i/2' ne s'exécutera que si' i' est impair. En outre, Collatz est également connu comme le problème 3n * plus * 1. – Olathe

Ceci est le halting problem. Il n'existe pas d'algorithme capable de faire ce que vous demandez.

En particulier, s'il y avait un tel algorithme, alors le collatz conjecture, lié à la fonction dans votre question, serait trivial (ou du moins beaucoup plus facile).

Source

2010-09-26 06:16:27 aaronasterling

Pourquoi cela a-t-il baissé? Est-ce parce que j'étais un peu en dehors de ma grammaire? J'apprécie cependant le passage de 4787 à 4785. Les nombres ronds sont gentils. – aaronasterling

@UncleO. Le titre de la question est "Comment puis-je vérifier si un algorithme se termine?". La première phrase de la question est "Y at-il une règle générale qui peut être utilisée pour déterminer cela?". C'est le problème d'arrêt. Ne laissez pas la présence d'un exemple spécifique de vous confondre. Notez également que OP a lu ma réponse et l'a ensuite sélectionné comme répondant à la question. – aaronasterling

Je pensais que c'était une bonne réponse étant donné la question. +1 – JoshD

Vous faites peut-être référence au problème d'arrêt. En bref, il n'y a pas de façon générale de déterminer si un programme va s'arrêter. Découvrez this article.

Source

2010-09-26 06:17:00 JoshD

Pourquoi cela a-t-il été voté? Est-ce parce que c'est semblable à la réponse d'Aaron? Nous les mettons en place à quelques secondes l'une de l'autre! J'aimerais avoir vos commentaires ... – JoshD

En général, "non". Comme tout le monde l'a dit, avec votre exemple spécifique, il peut être prouvé qu'il ne se termine pas, car i est toujours plus petit si i est pair (ou si i est non positif et impair, mais étant donné les conditions initiales, cela n'arrivera jamais)). Le plus petit nombre pair positif est 2, il passera alors à 1 pour l'itération suivante, où il sera ensuite transformé en 2.

Fait intéressant, vous ne vérifiez pas la conjecture de Collatz, car vous itérez même, 3 * n-1 si impair "et la Conjecture Collatz itère" réduisent de moitié si pair, 3 * n + 1 si impair ". Je ne peux pas trouver cette séquence discutée avec une recherche rapide.

Source

2010-09-26 08:51:34 Vatine

Comment vérifier si un programme se termine?

Répondre

Questions connexes