Aspects du jump de Turing

Theodore A. Slaman

Le jump de Turing est la fonction qui assigne à chaque ensemble X de nombres naturels, l’ensemble X′ du problème de l’arrêt relatif à X. X′ est l’exemple canonique d’un ensemble arithmétiquement définissable qui n’est pas récursif en X.

On discutera deux aspects de cette fonction remarquable et de ses itérations. D’abord, nous allons examiner la thèse que le seul moyen définissable et robuste de produire, à partir de X, un ensemble strictement plus complexe que X lui-même, est de produire un ensemble au moins aussi complexe que X′. Ensuite, nous discuterons comment cet aspect canonique du jump et du double jump amène à la preuve, par Shore et Slaman, que le saut est définissable dans l’ordre partiel des degrés de Turing.

Address: Department of Mathematics, University of California, Berkeley, CA 94720-3840, USA

E-mail: slaman@math.berkeley.edu