Comprendre une réduction

Supposons un décideur arrete_partout. Pour décider si un programme q s'arrête sur une entrée y, construisons le programme r qui, sur n'importe quelle entrée, exécute q sur y (en ignorant son argument). Alors r s'arrête sur toutes les entrées si et seulement si q s'arrête sur y. Si arrete_partout r existait, on déciderait l'arrêt de q sur y — impossible. Donc « s'arrêter partout » est indécidable.