Sea "P" el conjunto de todos los programas que se detienen, y "|p|" el tamaño en bits de un programa "p", Ω está definida de la siguiente manera: