¿Qué es una máquina de Turing no determinista?

Una máquina de Turing consta de tres partes: una cinta que puede almacenar información, un cabezal de ‘lectura-escritura’ que puede moverse hacia la izquierda o la derecha a lo largo de la cinta, leer información de la cinta y escribir información en la cinta, y una máquina de estado finito que controla el movimiento y la actividad del cabezal de lectura-escritura. Una máquina de Turing no determinista reemplaza la máquina de estados finitos con una máquina de estados no determinista. La diferencia representa cuánto tiempo lleva resolver diferentes clases de problemas. Algunos problemas pueden resolverse en el tiempo que está limitado por una función polinómica basada en el tamaño de la entrada. Por ejemplo, resolver x = 5 + 2 podría tomar 1 unidad de tiempo, x = 5 + 3 + 7 tomaría 2 unidades, x = a1 + a2 + a3 + … + an tomaría n-1 unidades de tiempo. Otras clases de problemas se denominan no polinomiales, ya que están unidas por una función exponencial en el tamaño de la entrada. Entonces, si tiene un candado de bicicleta viejo que tiene una etiqueta de ‘rueda’ 1-10, en el peor de los casos, se necesitarían 10 intentos para encontrar la combinación para abrirlo. Si tiene 2 ruedas, toma 100 intentos (10 ^ 2), para n ruedas, toma 10 ^ n intentos (en el peor de los casos). Una máquina de Turing no determinista puede resolver problemas no polinómicos en tiempo polinómico. Entonces, en general, la intuición puede ayudar a reducir el tiempo promedio esperado para resolver un problema, pero no afecta el peor de los casos necesarios para resolver un problema. Entonces, la intuición no es una máquina de Turing no determinista (a menos que siempre tenga la razón).