En este documento proponemos y analizamos desde el punto de vista de la complejidad computacional varias nuevas variantes de máquinas de Turing no deterministas. En la primera de dichas variantes, una máquina acepta una palabra de entrada dada si y solo si una de sus computaciones más cortas posibles en esa palabra es aceptante; por otro lado, la máquina rechaza la palabra de entrada cuando todas las computaciones más cortas realizadas por la máquina en esa palabra son rechazantes. Somos capaces de demostrar que la clase de lenguajes decididos en tiempo polinomial por tales máquinas es . Cuando consideramos máquinas que deciden una palabra de acuerdo con la decisión tomada por la computación más corta lexicográficamente primero, obtenemos una nueva caracterización de . También se discuten una serie de otras formas de decidir un lenguaje con respecto a las computaciones más cortas de una máquina de Turing.