Dana Scott Autómatas finitos y su problema de decisión (fragmento) "Un autómata no determinista no es una máquina probabilística, sino una máquina con múltiples opciones en sus movimientos. En cada etapa de su movimiento a través de una cinta, tendrá la libertad de elegir uno de varios nuevos estados internos. Por supuesto, alguna secuencia de opciones conducirá a situaciones imposibles desde las cuales no es posible ningún movimiento, o a estados finales que no pertenecen a la clase F designada. Sin embargo, ignoraremos todos estos fallos y aceptaremos que la máquina opte por una cinta si hay al menos una combinación ganadora de opciones de estados que conduzca a un estado final designado. La siguiente definición precisa esta convención. Por lo tanto, los autómatas ordinarios son casos especiales de autómatas no deterministas, y los identificaremos libremente con sus contrapartes. A primera vista, uno podría imaginar que estos nuevos autómatas son más genéricos que los ordinarios, pero éste no es el caso. Mostraremos una directa percepción de un autómata ordinario, definiendo exactamente el mismo conjunto de cintas como una máquina no determinista dada." El Poder de la Palabra epdlp.com