Cela équivaut au problème de décider, compte tenu d'un programme et d'un intrant, si le programme finira par s'arrêter lorsqu'il sera exécuté avec cette entrée, ou s'il sera éternel.
C'est le papier dans lequel Turing définit les machines de polymérisation, formule le problème d'arrêt, et montre qu'il -LRB- ainsi que le Entscheidungsproblem -RRB- est insoluble.