La preuve que le problème de l'arrêt est NP-dur?

Dans cette réponse à une question sur les définitions de NP, NP-dur, et NP-complet, Jason fait la réclamation que

Le problème de l'arrêt est le classique problème NP-difficile. C'est le problème que, étant donné un programme P et e, est-il tout arrêter? C'est un problème de décision, mais il n'est pas dans NP. Il est clair que toute NP-complets problème peut être réduit à celui-ci.

Alors que je suis d'accord que le problème de l'arrêt est intuitivement beaucoup plus "dure" problème de quoi que ce soit dans NP, honnêtement, je ne peut pas venir avec un officiel, mathématiques la preuve que le problème de l'arrêt est NP-dur. En particulier, je n'arrive pas à trouver un polynôme en temps many-to-one mapping à partir d'instances de chaque problème dans NP (ou au moins, connu NP-complet de problème) sur le problème de l'arrêt.

Est-il une simple preuve que le problème de l'arrêt est NP-dur?

OriginalL'auteur templatetypedef | 2011-08-09