Parabolanoi

"El problema de decisión se resuelve al responder sí o no a una pregunta respecto de alguna propiedad de una clase de problemas. Si existe un logaritmo que permita una de estas dos respuestas, se dice que éste es un algoritmo de decisión, y del problema de decisión se dice que se puede decidir algorítmicamente. [...]"

"[...] El problema de decisión ha de entenderse en la forma de la pregunta siguiente: ¿Existe o no una máquina de Türing que resuelva una cierta clase de problemas? En tanto que el concepto de solución algorítmica consiste en afirmar: los problemas de una clase son resueltos por una máquina de Türing [...]

"La teoría de algoritmos responde negativamente a una serie de casos. Uno de los primeros de este tipo [es el teorema de Church, que dice que el] problema de deducibilidad es algorítmicamente insoluble, a saber, carece de algoritmo de decisión. [Otro es que] el problema de convertibilidad también carece de algoritmos de decisión. [...] El matemático soviético Andrei Andriéievich Markov y el matemático norteamericano Emil Post [llegaron asimismo que] el problema de equivalencia de palabras es algorítmicamente irresoluble. [...]

"Supóngase que una máquina de Türing se ha fijado una cierta configuración. Dos casos son posibles: 1) la máquina es aplicable a esta configuración, es decir, al poner en marcha la máquina desde esta configuración de detendrá, con posterioridad a un número finito de ciclos, en una configuración final, evitando la señal de alto; 2) la máquina no es aplicable a esta configuración, es decir, la señal de alto jamás aparece y la máquina cae en un proceso infinito. Así las cosas, aparece el problema general [de la decisión de la aplicabilidad]...

"El problema de la decisión de la autoaplicabilidad carece de un algoritmo de decisión...

"El descubrimiento de problemas algorítmicamente irresolubles creó en la ciencia una situación tal, que un matemático que se proponga construir un algoritmo, deberá considerar la posibilidad de su inexistencia. [...]"

Boris Avraamovich Trajtenbrot

Introducción a la Teoría Matemática de las Computadoras y de la Programación

"Hasta ahora nos hemos atenido al punto de vista de que algoritmos diferentes se realizan en máquinas de Türing diferentes (diferentes por lo que toca a sus esquemas funcionales). Sin embargo, se puede construir una máquina universal de Türing, capaz en cierto sentido de ejecutar cualquier algoritmo, es decir, capaz de ejecutar el trabajo de toda máquina de Türing...

[Esta máquina universal de Türing deberá] hacer notar que tanto el esquema funcional de la máquina por imitar, como la configuración inicial correspondiente, figuran en calidad de datos originales (información inicial) del algoritmo de imitación que hemos descrito. La información original es tratada o «procesada», por el algoritmo y convertida en una configuración final que representa el resultado arrojado por la máquina por imitar. Una máquina universal debe realizar igual cosa. Sin embargo, al respecto es necesario tener en cuenta las dos circunstancias siguientes: 1. No es posible introducir directamente en la cinta de una máquina universal el esquema funcional de la máquina por imitar y la configuración correspondiente en calidad de información original. [...] 2. [Que] solamente dispone de un alfabeto externo y fijo, y, por la otra, debe ser capaz de recibir en calidad de información original todos los esquemas y configuraciones posibles, y éstos pueden contener letras de los más diversos alfabetos, [...]

Así las cosas, nuestro primer cuidado [en la máquina universal de Türing] debe consistir en definir un procedimiento que nos permita escribir los esquemas funcionales y configuraciones [de la máquina por imitar], a saber, información en una dimensión y alfabeto finito." 

Boris Avraamovich Trajtenbrot

Introducción a la Teoría Matemática de las Computadoras y de la Programación

"Las particularidades que permiten distinguir  una máquina de Türing de las máquinas electrónicas, [...] son las siguientes: 1. La segmentación de un proceso de operaciones simples se lleva hasta el límite de lo posible en una máquina de Türing. [...] 2. Una parte de la memoria de una máquina de Türing está representada por una cinta infinita, [...]" 

Boris Avraamovich Trajtenbrot

Introducción a la Teoría Matemática de las Computadoras y de la Programación

"[...] los teoremas de insolubilidad algorítmica al demostrar que la matemática no se reduce a la construcción de algoritmos, implican que el proceso de conocimiento en la matemática no puede automatizarse al extremo. [...] A la luz de estos hechos, resulta un mayor absurdo afirmar que una máquina puede remplazar el trabajo creativo del matemático." 

[...] toda máquina computadora físicamente realizable es tan sólo un modelo aproximado de una máquina de Türing. En efecto, la memoria externa de una máquina real es de extensión limitada, mientras que una máquina de Türing tiene una cinta infinita. [...]" 

Boris Avraamovich Trajtenbrot

Introducción a la Teoría Matemática de las Computadoras y de la Programación pp. 141-142

"Todo algoritmo puede definirse en términos de un esquema funcional de Türing y realizarse en la correspondiente máquina de Türing...

[...] Además de los esquemas funcionales de las máquinas de Türing, se han propuesto otros procedimientos para precisar este concepto [de algoritmo]. Así, por ejemplo, A. A. Markov llegó al concepto de algoritmo normal [...]; Gödel y Kleene han llegado al concepto de algoritmo recursivo (función recursiva). Sin embargo, todas las formulaciones tendientes a precisar el concepto de algoritmo han resultado ser equivalentes. El hecho no puede considerarse casual; [...]." 

Boris Avraamovich Trajtenbrot

Introducción a la Teoría Matemática de las Computadoras y de la Programación p. 114