La Máquina de Turing, es la muestra perfecta de que determinadas tareas no son automatizables o que ciertas funciones no son compatibles. Esta máquina es una máquina que no tiene restricciones de capacidad, de memoria ni de tiempo de ejecución.
Una función es computable si, y sólo si, hay una máquina de Turing que la computa: si le damos uno o varios argumentos como finita de pasos programados e imprime como
Turing sostenía que esta cuestión sólo puede resolverse experimentalmente y pro p onía lo que luego se ha llamado el test de Turing: podemos decir que una máquina piensa si un interlocutor humano, comunicándose por escrito con ella y con otros humanos, es incapaz de distinguir a la máquina de los otros interlocutores humanos. Además de todo esto, Las partidas de ajedrez y la creación de nuevos teoremas, también han sido propuestos.
Hace tiempo, los ordenadores solo realizaban problemas que se ponían a los estudiantes porque se dudaba de su capacidad para resolver problemas sin solución. Hasta que llegaron Larry Wos y William McCune, ellos crearon un ordenador capaz de resolver problemas sin soluciones encontradas por el hombre. Un ejemplo de ello, es que pudo resolver el problema planteado por Herbert Robbins a Alfred Tarski, y que consistía en lo siguiente:
¿Es cierto sistema de ecuaciones era equivalente a la definición de un álgebra de Doole?
Ningún matemático fue capaz de responder a esta pregunta, hasta que llegó a manos de Larry Wos y William McCune y su máquina, que respondió correctamente al problema.
Con esto se demostró que el concepto de máquinas de Turing era cierto, que pueden pensar.