De la

Computabilidad
a la
Hipercomputación

Alberto Pastor Nieto

Lógicas para la Informática y la I.A
Ingeniería informática
Índice
Introducción ......................................................................................................................................... 3
Los orígenes de la Computación.......................................................................................................... 4
¿Qué fue antes, los ordenadores o la teoría que analiza su comportamiento? ................................ 4
Inicios de la Teoría de la Computación........................................................................................... 4
Tópicos sobre los orígenes de la Teoría de la Computación.......................................................... 4
Modelo actual de computación, Máquinas de Turing.......................................................................... 5
Funcionamiento de las Máquinas de Turing ................................................................................... 5
Tipos de problemas ......................................................................................................................... 7
Problemas de decisión y de parada............................................................................................. 7
Demostración de la no computación del Problema de Parada.................................................... 7
Tesis de Church .............................................................................................................................. 8
Teoría de la Computación e Inteligencia Artificial.............................................................................. 9
Hipercomputación.............................................................................................................................. 10
Principales modelos en Hipercomputación........................................................................................ 12
Estrategia formal ........................................................................................................................... 12
Máquinas propuestas ............................................................................................................... 12
ATM, Máquinas aceleradas de Turing ............................................................................... 12
Máquinas de Turing de Tiempo Infinito ............................................................................. 13
Estrategia Material ........................................................................................................................ 14
Hipercomputación como un análisis crítico del modelo clásico........................................................ 15
Análisis Inverso.................................................................................................................................. 16
Diagonalización ................................................................................................................................. 18
Conclusión del Autor ......................................................................................................................... 19
Conclusión Personal........................................................................................................................... 20

2
Introducción

El texto “De la Computabilidad a la Hipercomputación” se divide claramente en dos partes, en la

primera, nos muestra de forma histórica como se ha llegado al modelo actual de computación,
señalando sus éxitos y sus limitaciones. En la segunda, partiendo de las limitaciones, hace un
recorrido por las posibles alternativas al modelo vigente, revisando las diferentes vías de
investigación que se están llevando a cabo.

Se pretende mostrar las distintas alternativas que se han propuesto, partiendo de las limitaciones de
las máquinas de Turing ya que no pueden resolver algunos problemas, destacando el problema de
parada, la imposibilidad de que se pueda saber si un problema es finito o infinito.
Se explicarán las razones de porqué se pretende plantear un nuevo modelo que sustituya al vigente y
se señalará el importancia de la Inteligencia Artificial en esta búsqueda, debido a su fracaso en lo
referente a las expectativas que se generaron en un principio.

Este trabajo sigue la estructura del texto, empezando por un acercamiento de lo que es el paradigma
actual, para después mostrar las diferentes alternativas que se van planteando, señalando sus
limitaciones y todas las dificultades que se están encontrando en esta búsqueda.

3
Los orígenes de la Computación

Comenzaremos comentando cómo se llegó al modelo actual de computación de forma breve para
podernos situar en el contexto ideal para explicar el problema a tratar.

El estudio de la computación consiste en última instancia en el análisis de todo aquello que tiene
que ver con la noción de tarea efectiva o algoritmo. Las tareas efectivas son aquellas que pueden ser
ejecutadas en un ordenador quizá ideal y no sometido a limitaciones físicas de espacio.

¿Qué fue antes, los ordenadores o la teoría que analiza su

comportamiento?
Normalmente aparece antes el ingenio que la teoría que la sustenta, gracias a algún visionario, en
cambio en este caso ocurrió todo lo contrario, se desarrolló antes la Teoría de la Computación, para
que décadas más tarde se crearan los primeros ingenios basados en ella.

Inicios de la Teoría de la Computación

En un periodo de tiempo muy corto, siendo muy pocas las personas involucradas se desarrollaron
las primeras teorías sobre la computación. Durante el invierno de 1936-37 se publicaron de forma
casi simultánea e independiente dos artículos que sentarían las bases de esta disciplina. El primero
de Alonzo Church, “An Unsolvable Problem of Elementary Number Theory” y el segundo de
Alan Turing, “On Computable Numbers, with an Application to the Enstscheidungsproblem”. Más
adelante se explicaran los principios básicos mostrados en estos artículos.
Los términos “computable”, “computabilidad” o “computación” todavía no son habituales, por lo
que se integra a estos trabajos dentro de la “Teoría de las funciones recursivas”.
La traducción de la teoría a la práctica no empieza hasta mediados de los años 40, y no se empieza a
tomar en serio hasta la década de los 50.

Tópicos sobre los orígenes de la Teoría de la Computación

Se suele pensar que los objetivos de la Teoría de la Computación son los mismos que los que tiene
la Inteligencia Artificial. Es cierto, que siempre ha existido una fuerte curiosidad por saber si
nuestras habilidades podían ser imitadas por medios artificiales, pero la Teoría de la Computación
no nace de ella. Más tarde se produce una confluencia entre ambas, al observar las distintas
posibilidades técnicas que ofrecen los ordenadores. Además la teoría de la Computación se ve
limitada como veremos en el apartado siguiente.

4
Modelo actual de computación, Máquinas de Turing
En lógica matemática se conocen como teoremas de incompletitud de Gödel a los siguientes
teoremas:

● "En todo sistema formal consistente que contenga los números naturales con su aritmética es
posible construir una sentencia de la cual no es posible probar ni su veracidad ni su falsedad
dentro del sistema".

● "Ningún sistema formal consistente permite demostrar su propia consistencia."

Alan Turing, en su trabajo "Los números computables, con una aplicación al

Entscheidungsproblem" (publicado en 1936), reformuló los resultados obtenidos por Gödel en 1931
sobre los límites de la demostrabilidad y la computación, sustituyendo al lenguaje formal universal
descrito por Gödel por lo que hoy se conoce como Máquina de Turing.

Esta máquina era capaz de implementar cualquier problema matemático que pudiera representarse
mediante un algoritmo. Demostró que el problema de la decisión era irresoluble, al igual que el
problema de la parada para las Máquinas de Turing. El problema de parada nos dice que no es
posible decidir algorítmicamente si una máquina de Turing dada llegará a pararse o no, ya que en
algunos problemas pueden ser de solución infinita.

Funcionamiento de las Máquinas de Turing

La máquina de Turing consta de:

● un cabezal lector/escritor
● una cinta de datos infinita.

Las operaciones que se pueden realizar en esta máquina se limitan a:

● avanzar el cabezal lector/escritor para la derecha.

● avanzar el cabezal lector/escritor para la izquierda.
● el cabezal lee el contenido
● el cabezal borra el contenido anterior y escribe un nuevo valor.

El cómputo es determinado a partir de una tabla de estados de la forma:

(estado, valor) ---> (\nuevo estado, \nuevo valor, dirección)

Esta tabla toma como parámetros el estado actual de la máquina y el carácter leído de la cinta,
dando la dirección para mover el cabezal, el nuevo estado de la máquina y el valor a ser escrito en
la cinta.
La memoria se divide en espacios de trabajo denominados celdas, donde se pueden escribir y leer
símbolos. Inicialmente todas las celdas contienen un símbolo especial denominado “blanco”. Las
instrucciones que determinan el funcionamiento de la máquina tienen la forma, “si estamos en el
estado x leyendo la posición y, donde hay escrito el símbolo z, entonces este símbolo debe ser
reemplazado por este otro símbolo, y pasar a leer la celda siguiente, bien a la izquierda o bien a la
derecha”.

5
 Ilustración 1: Máquina de Turing

Si estado está en la posición del cabezal de lectura/escritura se suplanta el valor que tuviera por
\nuevo valor, y se mueve el cabezal a la posición especificada por dirección. La siguiente
instrucción a ejecutar vendrá dada por \nuevo estado. Si una instrucción no es aplicable, porque no
esté el valor de estado bajo el cabezal, por ejemplo, se intenta la siguiente instrucción, y si ninguna
es aplicable, la máquina se detiene y la computación acaba, siendo el resultado el escrito en la cinta
en ese momento. Si una computación no acaba, se dice que diverge y no produce ninguna salida.
Formalmente se define una máquina de Turing de la siguiente forma:

● es un conjunto finito de estados

● es un conjunto finito de símbolos de cinta, el alfabeto de cinta.

● es el estado inicial.

● es un símbolo denominado blanco, y es el único símbolo que se puede repetir un

número infinito de veces.

● es el conjunto de estados finales de aceptación.

● es una función parcial denominada función de

transición, donde L es un movimiento a la izquierda y R es el movimiento a la derecha.

Con una máquina tan sencilla como esta, se pueden realizar todos los tipos de cómputo que
cualquier ordenador pueda hacer. Se puede probar de forma matemática que para cualquier
programa se puede crear una máquina de Turing equivalente, no lo haremos aquí, ya que se sale de
los objetivos de este trabajo.

6
Tipos de problemas
Los tipos de problemas computacionales dependiendo de su comportamiento son:

● Problemas P (Deterministas). Para cada par estado y símbolo posible existe a lo sumo
una posibilidad de ejecución.
● Problemas NP (No deterministas) Las soluciones de éstos, se obtienen en tiempo
polinómico. Existe al menos un par [estado, símbolo] con más de una posible combinación
de actuaciones.
● Problemas no computables: aquí aparece el problema de parada.

Problemas de decisión y de parada

Su enunciado plantea la cuestión de si existe o no un procedimiento de decisión que sea capaz de
determinar en tiempo finito si una fórmula de la Lógica elemental es o no un teorema. Tanto Church
como Turing observan que cualquier respuesta a este problema pasa por aclarar de manera
satisfactoria a qué se hace referencia con procedimiento de decisión. Es claro que dicho
procedimiento es una rutina o algoritmo que permite ofrecer la respuesta a un problema dado. La
repuesta ofrecida por Church y Turing a dicho problema es negativa. No existe un un algoritmo que
permita determinar si dada una fórmula, ésta es o no un teorema de la Lógica Elemental. Ésto, no
quiere decir que no se pueda alcanzar esta conclusión en muchos casos, sino, que no existe un
método general aplicable a todos ellos.
Aquí entra la discursión sobre que entender como tarea efectiva. Si se considera como tarea efectiva
un procedimiento finito consistente en una serie de instrucciones cada una de las cuales da paso a la
siguiente en función de ciertos factores sin dejar en ningún momento un lugar a la elección
arbitraria, entonces el problema de decisión no tiene solución.

De este problema se deduce el que lo engloba, denominado problema de parada:

“No hay un procedimiento efectivo capaz de determinar de manera general si otro

procedimiento igualmente efectivo es capaz de finalizar arrojando un resultado cuando se le
suministra un input o situación de partida”

Nuestros algoritmos no parecen ser tan eficaces como desearíamos, ya que no podemos saber en
general si estos van a terminar a menos que lo hagan.

Demostración de la no computación del Problema de Parada

Suponiendo que existe una máquina de Turing para el problema de la parada, H, se puede construir
una máquina modificada H1 que acepte la codificación de una máquina de Turing como entrada y
determine si esta máquina se detiene cuando acepta una determinada cadena de entrada (a H).
Ahora se considera otra máquina H2 que es como H1 pero que sigue ejecutándose (no para)
mientras la máquina dada se detenga por su propia entrada y que se detiene si la máquina dada no se
detiene para su entrada. Si a H2 se le da como entrada una codificación de sí misma, se ejecuta sí y
sólo sí se para. Esto es una contradicción. Y la contradicción está en la existencia de una máquina H
para el problema de la parada (es errónea esta suposición).

7
Tesis de Church
“Toda tarea efectiva que podamos concebir y expresar de forma precisa en un determinado
formalismo, puede ser expresada igualmente en el formalismo de las máquinas de Turing”
Ampliando su alcance:
“Todo algoritmo o procedimiento efectivo es computable por una máquina de Turing”

Aunque se asume como cierta, la tesis de Church-Turing no puede ser probada. Esto es debido a
que “procedimiento efectivo” y “algoritmo” no son conceptos dentro de ninguna teoría matemática
y no son definibles fácilmente. La evidencia de su verdad es abundante pero no definitiva.
Precisamente la tesis de Church establece que la definición de algoritmo o procedimiento efectivo
es una máquina de Turing.

Se ha acordado que un procedimiento efectivo o algoritmo consiste en un número finito y preciso

de pasos descrito en un número finito de símbolos que podría ser también ejecutado por un ser
humano. En general, la ejecución de un algoritmo no requiere de mayor inteligencia que la
necesaria para entender y seguir las instrucciones.
La tesis de Church-Turing ha sido tan exitosa que la mayoría la supone verdadera, en este punto el
autor del texto plantea una cuestión:

Si en otros campos de las matemáticas existen distintas formas de interpretar la noción general,
como pasa en la aritmética o la geometría. ¿Por qué tendría que haber una única forma de
interpretar formalmente la noción intuitiva de tarea efectiva?

8
Teoría de la Computación e Inteligencia Artificial

La prosperidad de la Inteligencia Artificial se debe en gran medida a la forma que tiene la Teoría de
la Computación de interpretar la idea de Algoritmo. Desde antiguo, el deseo de imitar las
habilidades cognitivas del ser humano siempre ha estado presente. En la antigüedad incluso era una
obsesión.
Siempre ha habido corrientes mecanicistas con el objetivo de crear réplicas artificiales del ser
humano, en su totalidad o en parte. Lo que no ha permanecido constante es la teoría subyacente en
la que se basaba para lograr sus objetivos. Los autómatas músicos de los siglos XVIII XIX se
basaban en la mecánica racional, los actuales, en la Teoría de la Computación.
Una de las razones de cambio de paradigma es el grado de autorreferencia que presenta este
modelo, sin que aparezcan paradojas. Una máquina de Turing se diferencia de otra por el programa
que ejecuta, siendo un programa una cadena finita de instrucciones. Asignar un número a ese
programa es una tarea llamada codificación (la tarea contraria se llama decodificación). Un código
es un entero positivo que contiene toda la información del programa.
Una máquina de Turing procesa enteros positivos y nada impide que una de estas máquinas
contenga los mecanismos para decodificar enteros positivos. La autorreferencia es evidente.
¿Qué sucede cuando una máquina con código i procesa como input el número i y posee
además los mecanismos para decodificar enteros positivos?
Turing demostró que estas máquinas son máquinas de Turing igualmente. El resultado por el que se
llega a esta conclusión es por el “Teorema de existencia de Máquinas Universales”.
¿Qué importancia tiene la existencia de máquinas universales para la IA?
Hasta la aparición de la Teoría de la Computación la imitación de tareas típicamente humanas era
tratada como una mera hipótesis o se limitaba a algún aspecto concreto y aislado. La cosa cambia a
partir de la demostración de la existencia de máquinas universales.
¿Cuantas tareas concretas puede ejecutar una máquina universal?
Todas, aquellas que pueden ser ejecutadas por máquinas de Turing. Basta con identificar su código.
A partir de ese momento, la posibilidad de concebir la imitación de las habilidades cognitivas del
ser humano deja de ser un sueño. Pasa algún tiempo hasta que los investigadores tomen conciencia
de la aparición de la disciplina llamada Inteligencia Artificial. El primero que se plantea si una
máquina puede pensar, es el propio Turing.
El paso del tiempo y la ausencia de resultados definitivos ha venido provocando una sensación de
desconfianza, llevando a los investigadores a replantearse ciertos principios. Quizá la teoría de
fondo en la que se sustenta la I.A. presente unas carencias que estén bloqueando el progreso de esta
disciplina. Los fundamentos de la interpretación estándar de la computabilidad deben ser revisados
y criticados a la búsqueda de posibilidades que pueden haber quedado ocultas. A estas nuevas vías
de investigación se las conoce por Hipercomputación.

9
Hipercomputación

El término Hipercomputación se emplea para referirse a la siguiente idea:

“...el cómputo de funciones o números que no pueden ser calculados en el sentido de Turing
[...] i.e, no pueden ser calculados a través de un número finito de pasos realizados por un
agente humano dotado de lápiz y papel que opera de manera efectiva” [Copeland 2004, p.251]
Su uso empieza a extenderse durante la década de 1990 convirtiendose en una referencia habitual a
partir del “Hipercomputation WorkShop” celebrado en 2000 en el University College. En los
últimos años ha pasado de ser una curiosidad propia de lógicos o filósofos, a ser una alternativa real
para los expertos en IA.
No se trata de un ámbito con unos objetivos y una metodología demasiado definidos, sino de un
conjunto de estrategias que intentan proponer modelos alternativos a los vigentes.
Muchos autores ven que el origen de la hipercomputación está en el concepto de oráculo,
introducido por Turing en 1939.
“Supongamos que se nos suministran ciertos recursos sin expecificar, aptos para resolver
cuestiones numéricas, algo similar a un oráculo. No entraremos en la naturaleza de ese
oráculo salvo para dejar claro que no puede tratarse de una máquina. Con la ayuda de éste
oráculo, formaremos un nuevo tipo de máquina (O-máquina) que tiene como uno de sus
procesos básicos el de resolver un determinado problema numérico”. [Davis 1965, p.167]
El concepto de oráculo se presenta para poder generar una serie de sistemas (lógicas), con respecto
a la cual se pueda definir un límite, lo que el propio Turing denomina ordinal logic. Este sistema
límite se podría emplear para probar más cosas de las que se pueden probar en cada uno de los
sistemas de esa serie.
Los intentos para desarrollar modelos alternativos de la computabilidad tienen otro origen. El
primer intento de alternativa al paradigma actual fue el modelo conexionista y su definición de red
neuronal. Una de estas redes está formada por elementos de proceso que simulan a las neuronas,
estas se conectan entre ellas en capas. Se intenta simular el funcionamiento del cerebro humano
imitando las características de sistema distribuido, paralelo y fácil de adaptarse a nuevas
circunstancias. A la máquina de Turing se le opondría una red neuronal existiendo alguna
posibilidad de que estas últimas fueran capaces de hacer algo que queda más allá del alcance de las
primeras. Se concluye que una red neuronal estándar no es más potente que una máquina de
Turing. El modelo que se sigue en IA con las máquinas de Turing es de tipo funcionalista, lo que
importa en este paradigma es la función que realiza, no la estructura que se tiene.
Resumiendo:
● Modelo conexionista: Intenta afrontar el problema de la IA desde el punto de vista de la
similitud estructural para obtener conductas y comportamientos similares a los del cerebro
humano.
● Modelo funcionalista: Intenta abordar el problema imitando las funciones que realiza, sin
preocuparse de la estructura, éste paradigma está más ligado al modelo computacional
clásico.

10
Una segunda linea de investigación procede de las discursiones filosóficas surgidas en torno a la
posibilidad lógica de concebir lo que se denomina una supertarea. Este concepto se remonta a las
paradojas de Zenón. Se maneja la posibilidad de concebir sin contradicción una tarea compuesta
de infinitos pasos que finaliza en tiempo finito.
Russell 1914, Weyl 1927 y Blake 1926 consideraron de forma independiente los distintos aspectos
del concepto de supertarea, dicho concepto se reavivó a medidos del sigo XX con trabajos de
Thomson, Benacerraf y Chihara.
El autor que unió esta problemática con el mundo de la computación fue G.Boolos cuando introdujo
el concepto de Zeus Machine en 1974. En el momento actual, J.Copeland es el principal defensor de
esta opción, creando teóricamente las ATM, máquinas aceleradas de Turing, que serán explicadas
más adelante. De lo que trata es de analizar si es posible concebir que tareas efectivas adopten la
forma de una supertarea. Si es posible, estaríamos ante tareas que ninguna máquina de Turing
podría ejecutar, sin que ello se pudiera considerar que no se trata de una tarea efectiva.
Otra línea de investigación se centra en el intento de superar ciertos resultados de limitación
relativos al alcance y potencia de la Lógica a través de sistemas basados en ordinales. Esta línea de
investigación comparte con la anterior el intento de sacar algún partido del concepto de infinito para
obtener consecuencias que vaya algo más allá de los requisitos finistas del modelo clásico. También
se encuentra relacionada con la computación cuántica, debido a su orientación, queda fuera del
alcance del trabajo.

11
Principales modelos en Hipercomputación
Entre los diferentes modelos que se han propuesto para sustituir al actual, se pueden distinguir dos
formas para afrontar el problema. La primera de ellas propone que la solución debe estar
relacionada con el dominio de la lógica y de las matemáticas, así como sucedió con el modelo
clásico. A esta estrategia se la denomina formal. La segunda busca la solución en la física de la
naturaleza para que se puedan superar los límites teóricos del modelo clásico, esta estrategia se
denomina estrategia material.

Estrategia formal
Los modelos que se obtienen al adoptar esta estrategia suelen estar basados en la alteración de
alguna de las características de la arquitectura básica de una máquina de Turing. El primer cambio
tiene que ver con el número de pasos que es posible ejecutar en un dispositivo antes de alcanzar un
estado final o de parada, Gold introduce la distinción entre limit states y successor states
terminología típica de series inductivas.
Esta idea a sido retomada en los últimos años por Hamkin y Lewis con las máquinas de tiempo
infinito (ITTM). El primer estado límite de una ITTM sería el resultante de considerar una máquina
de Turing estándar que no finaliza en un número finito de pasos.

Máquinas propuestas

ATM, Máquinas aceleradas de Turing

A principios de la década de los 20, Bertrand Russell, Ralph Blake y Hermann Weyl propusieron
independientemente la idea de proceso que ejecutara su primer paso en una unidad de tiempo, y
cada paso siguiente en la mitad de tiempo que el anterior. Como se cumple que:
1+1/2+1/4+1/8+...<2
este proceso podría terminar en un número infinito de pasos en dos unidades de tiempo. Turing
nunca mencionó cuánto tiempo tarda su máquina en ejecutar un paso de manera individual, por
tanto este modelo no entra en conflicto con la concepción matemática de la máquina de Turing
original.
Consideramos una máquina de Turing acelerada, A, que está programada para simular una máquina
de Turing arbitraria con una entrada arbitraria. Si la máquina de Turing se detiene ante su entrada, A
cambiará un valor de la cinta específico (por ejemplo el primer cuadrado de la cinta) de 0 a 1. Si la
máquina de Turing no se detiene, entonces A dejará el cuadro de la cinta con el valor 0. En
cualquier caso, después de 2 unidades de tiempo, el primer espacio de la cinta de A contiene el valor
de la función de la parada para esa máquina de Turing y esa entrada específica.
Por tanto, no hay otra diferencia entre una máquina de Turing acelerada y una máquina de Turing
estándar que la velocidad con la que la acelerada opera. En concreto, A no ha resuelto el problema
de la parada porque la máquina de Turing está definida para que saque el valor después de que se
detenga. Por tanto A no se detendrá si simula una máquina que no se detiene. Sin embargo, la
situación que se ha descrito sugiere un cambio pequeño que permitiría a A resolver el problema de
la parada: Sacar como salida de la máquina cualquier valor después de dos unidades de tiempo (la
máquina ya debería haber parado si fuera a hacerlo).

12
Máquinas de Turing de Tiempo Infinito
En el artículo “Máquinas de Turing de tiempo infinito”, Joel Hamkins y Andy Lewis presentaron un
modelo de máquina de Turing que operaba durante un número “trasfinito” de pasos. Podríamos
imaginar, por ejemplo, una máquina que incluyera una máquina de Turing acelerada (M) como
componente. M empezaría a computar, y después de 2 unidades de tiempo, M se detendría y se
resetearía a su estado inicial, dejando la cinta como se quedara tras acabar su computación. Se
podría volver a poner en funcionamiento M, con su cabezal de lectura/escritura al principio de la
cinta. Se volvería a ejecutar durante dos unidades de tiempo. De esta forma, esta máquina ejecutaría
dos secuencias infinitas de pasos una a continuación de otra. Si añadimos una sucesión infinita de
ejecuciones de la máquina, M ejecutará infinitas secuencias en un número infinito de pasos.
Las máquinas de Turing de tiempo infinito son una extensión natural de las máquinas de Turing que
operan un número “trasfinito” de veces. Para determinar la configuración de la máquina en
cualquier ciclo sucesor, la nueva configuración queda definida a partir de la anterior de acuerdo con
las reglas de la máquina de Turing estándar. En el tiempo del límite ordinal, sin embargo, la
configuración de la máquina se define basándose en todas las configuraciones precedentes. La
máquina alcanza un “estado límite” especial y cada espacio de la cinta toma un valor de la siguiente
manera: El cuadrado de la cinta n en el tiempo límite a toma el valor de: 0 si el cuadrado se ha
establecido como 0; 1 si el cuadrado se ha establecido como 1; y 1 si el cuadrado ha variado entre 0
y 1 con una frecuencia ilimitada.
El cabezal de la máquina vuelve al primer espacio de la cinta y la máquina continúa con su
computación desde el “estado límite” como si estuviera en cualquier otro estado. Como de
costumbre, si no hay un paso apropiado para ejecutarse en algún punto, la máquina se detiene. De
esta forma se puede ejecutar un número finito de pasos y luego detenerse, o bien un número infinito
de pasos y luego detenerse ó mantenerse computando “un número ordinal de veces” y nunca llegar
a detenerse.
Esta máquina podría computar cualquier función recursivamente enumerable en Ω pasos,
estableciendo el primer cuadrado de la cinta a 0, después se evaluaría la función y se establecería el
primer cuadrado de la cinta a 1 si f(n)=1. Si f(n)=1 después de otros Ω pasos el primer cuadrado de
la cinta mantendría el valor de 1, y si f(n)=0 el primer cuadrado almacenaría el valor de 0.

Transfinito: De forma sencilla, un número transfinito es un número mayor que cualquier número
natural. Es un número infinito que definió teóricamente Georg Cantor para que conjuntos infinitos
pudieran ser comparados. El mínimo número transfinito es ω.

Por supuesto, ninguna de estos tipos de máquinas ha podido ser implementado de manera física,
pero nos sugieren posibles implementaciones en un futuro, el cual no parece muy cercano.

Las críticas más recientes a las máquinas de Turing proceden de otro concepto, el de la interacción.
En la teoría las máquinas de Turing son entidades transparentes, pero se comportan como auténticas
cajas negras mientras dura la rutina que ejecutan. No emiten ni un solo bit ni aceptan ningún dato
externo mientras el proceso tiene lugar. Pi-calculus desarrollado por Milner puede entenderse como
un intento de desarrollar esta idea. También las coupled Turing Machines de Copeland desarrollan
esta idea.

13
No es extraño que esta estrategia formal intente encontrar una forma de calcular la función asociada
al problema de parada. Han sido pocos los autores que se han parado a considerar la estructura
lógica del problema de parada y de la función asociada a su cálculo, esta estructura se basa en la
técnica de diagonalización. Autores como Enrique Alonso y María Manzano señalan que la correcta
interpretación de esta técnica y de su uso, pueden ser de gran ayuda cuando se intentan entender
ciertas limitaciones del concepto vigente de tarea computable. Y esto mismo, vale para interpretar el
concepto de supertarea.

Estrategia Material
La idea de esta estrategia es la búsqueda de modelos dotados de capacidades causales capaces de
superar las limitaciones formales que poseen los mecanismos basados en la Lógica. Afronta el
peligro de producir propuestas que de un modo u otro colapsen sobre el modelo clásico. La objeción
que realizan los escépticos es la referente al lenguaje en la que se expresan las tareas. Todo se
reduce a la comparación de los lenguajes en que se expresan las rutinas. Para saber si algo puede ser
visto como un avance o no en el cálculo de funciones no-Turing computables hay q acudir al análisis
formal de las funciones afectadas. Y al proceder así nos encontramos con problemas de
implementación del estilo de los que se afrontan desde la estrategia formal. Un ejemplo es el de las
redes neuronales, sólo divergen del modelo clásico cuando los valores de activación en la red son
número reales o cuando las entradas son números reales. El problema es como se especifica de
forma finita un número real?
Ninguna de las estrategias que se ha mostrado son independientes una de la otra, pudiéndose
completar. La primera es claramente no implementable, lo que lleva a buscar algún fenómeno de
tipo natural capaz de representar de alguna forma las propiedades formales de cada una de las
propuestas. Es un caso parecido a la lucha de software – hardware, en la que la sinergia es la mejor
opción.

14
Hipercomputación como un análisis crítico del modelo clásico
En la actualidad no se puede ser muy optimistas con los resultados obtenidos en este campo. Parece
obvio que se está muy lejos de encontrar posibles implementaciones físicas de los modelos teóricos
planteados hasta la fecha, tampoco es evidente que estos modelos muestren conductas que resulten
preferibles a las del modelo clásico. Es posible, que por lo menos de una forma teórica, una ATM
calcule de forma efectiva funciones que las máquinas de Turing no puedan ejecutar de ningún
modo, se destaca aquí el problema de parada. Algún precio habrá que pagar por ello, seguramente
haya que verse obligado a aceptar una interpretación nueva y extraña de lo que significa una tarea
efectiva y una rutina.
La consideración de nuevos modelos que sustituyan a los clásicos nos está permitiendo revisar el
modelo actual, centrándonos en los aspectos más problemáticos del mismo.
Varios autores se han percatado que el hecho de tener una cinta infinita no es inocente. Esta
idealización en las TM (máquinas de Turing) afecta al espacio, mientras que en las ATM es una
limitación de tiempo. Una ATM exige una cantidad infinita de material capaz de contener una
cantidad infinita de información, una necesidad del modelo. Davis en 2001 propone una solución al
problema del espacio, diciendo que se puede considerar una cinta de cálculo en la cual cada celda
ocupa la mitad de la anterior, alcanzando un límite, con el precio de operar en un espacio denso y
contínuo.
También cabe destacar las que son las idealizaciones sobre las que reposa el modelo clásico. Turing
toma como punto de partida una situación experimental en la que se consideran ciertos elementos
dejando fuera otros. El punto de partida podría haber sido otro. La imagen inicial de Turing es
representar la forma de operar de manera efectiva de un ser humano cuando resuelve cierto tipo de
problemas, omitiendo otros componentes, que pudieran ser asumidos por otro modelo matemático
alternativo. La idea general resulta atractiva porque permite entender las dificultades que el modelo
clásico tiene con algunos aspectos básicos de la actividad cognitiva de los humanos. Muchas veces
el paradigma actual da la impresión de que las tareas se realizan de forma forzada y poco natural,
ello nos hace pensar que la idea de Turing al proponer su modelo no intenta responder a una
conducta excesivamente realista.
¿Existen otros modelos que puedan servir como punto de partida que puedan establecer
traducciones más potentes de la forma en la que los humanos actúan para lograr una tarea
efectiva?
Las máquinas de Turing prácticamente no interaccionan con su entorno ni con otras. Todos los
procesos están controlados por una unidad central que no se comunica con el exterior, su
interacción es de forma muy artificial, así como los procesos de cambio.
“El modelo computacional clásico nunca ve más de una única máquina asociada a la ejecución de
una determinada tarea”. No existen recursos teóricos para expresar otra posibilidad. Resulta
claramente forzado hablar de evolución, cambio e interrelación. Las máquinas de Turing son
extremadamente discretas con respecto a su forma de actuar, nunca aportan información intermedia.
En relación con lo anterior, uno de los objetivos de la Inteligencia Artificial clásica es la de producir
una conducta original e independiente. Se añade el problema de especiación, la capacidad de una
entidad artificial de tener una conducta original y escapar al control del ser humano y persistir a lo
largo del tiempo transmitiendo a otras entidaes del mismo tipo sus pautas básicas. Hoy en día todo
esto se enmarca dentro del campo de la ciencia ficción, no obstante, las cosas pueden estar
cambiando en este punto. El autor del texto hace un llamamiento a que se empiecen a considerar
conceptos que parezcan extravagantes ya que con el tiempo pueden servir para replantearse diversos
aspectos del modelo computacional.

15
Análisis Inverso
Aunque hay muchos problemas insolubles el primero de ellos y al cual se pueden reducir los demás
es el problema de parada, éste, permite definir un conjunto numérico K, de la siguiente forma:

K ={x / fx(x) tales que la x-ésima función numérica arroja un resultado cuando se le
suministra el valor x como entrada }

Determinar si un entero positivo dado i, pertenece o no a K constituye la forma canónica y habitual

de referirse al problema de la decisión.
Los nuevos modelos que se proponen buscan soluciones para este problema. K representa el
comportamiento de la insolubilidad de cualquier problema. Carece de un contenido propio
considerándose como una expresión puramente formal y abstracta de insolubilidad. Aunque sea
importante definir los límites de la computación clásica, pocos autores se han parado a analizar
cómo se llega a la conclusión de que K no es computable. La técnica para mostrar este extremo se
conoce como técnica de diagonalización.
El autor del texto propone llevar a cabo un análisis inverso del estudio de la insolubilidad
consistente en lo siguiente:
“Dada la estructura formal de la demostración por la que se establece la insolubilidad del
problema de parada, ¿qué condiciones debería poseer cualquier otra clase de procedimientos
para que fuera capaz de contener entre sus miembros uno que pudiera resolver el problema
de parada de las máquinas de Turing?”

Se plantea distintas preguntas que va respondiendo, la primera es si basta el argumento diagonal

clásico para rechazar la existencia de una solución efectiva del problema de parada aunque basada
en procedimientos distintos a los de TM's, la respuesta es negativa. Se lleva a esta conclusión
aplicando la Tesis de Church. Concluye a esta pregunta con lo siguiente:
“El método empleado por un determinado procedimiento H para identificar y hacer
referencia a los elementos de otra clase P no puede ser definible en P”.
Ese procedimiento H podría abordar el problema de parada en P sin contradicción, pero pagando un
precio alto. La clave está en los métodos empleados para interpretar la enumerabilidad efectiva de
una clase de procedimientos. Esta enumeración es definible en términos de máquina de Turing.
Estas conclusiones son consecuencias del teorema de Forma Normal de Kleene.
Las ambigüedades no permiten responder a la pregunta de si se puede concebir sin contradicción la
existencia de un algoritmo particular para resolver el problema de parada de cada función Turing-
computable sin que exista un algoritmo general de todas ellas.
Por último se propone a resolver la pregunta de si las ATM's podrán resolver el problema de parada.
Comienza hablando de los oráculos propuestos por Turing, mostrándolos como cajas negras. No
sabemos nada sobre su naturaleza ni su funcionamiento. Las ATM's se pueden considerar Oráculos,
pero por otras razones. Resuelven cuestiones numéricas que quedan fuera del alcance de las TM's,
pero en este caso tenemos mucha información del modo en el que trabajan. Aparece el concepto de
oráculos translúcidos, oráculos que se comportan como cajas grises.
Queda un problema todavía por tratar, y es el dominio de las ATM's y de las condiciones ideales
bajo las que operan.

16
Supongamos que tenemos una ATM que dada una entrada, no alcanza un estado de parada estándar,
sino que continúa acelerando de algún modo. El estado final de una de estas máquinas es el límite
de algún proceso infinito que no nos resulta accesible. Resulta imprescindible añadir algún tipo de
interfaz que recoja el resultado obtenido por una máquina que opera de forma acelerada, si existe y
refleje que no existe en otro caso. El modo más simple de apreciar este comportamiento es suponer
que una ATM consta de un mecanismo que se ejecuta en un régimen acelerado un programa
previamente dado para escribir el resultado de esa rutina, si existe, deteniéndose en una celda en
blanco de otro modo. Podemos suponer, sin pérdida de originalidad, que el proceso siempre termina
en k segundos. De esta manera una ATM alcanza el mismo resultado que sus correlatos en el
dominio de las TM's cuando este existe alcanzando de otro modo un resultado previamente
convenido a los k segundos. Se puede decir que una ATM computa todas las funciones computables
por las TM's. La clase de estas funciones está sometida a la técnica de la diagonalización.
Mediante este procedimiento se puede establecer la imposibilidad de enumerar ciertas clases de
objetos. Éstos son separables e identificables mediante nombres. Las clases de funciones cuyos
valores se pueden calcular mediante el uso de máquinas de Turing y tales además están definidas
para todos sus posibles argumentos no son enumerables. No es posible separar las funciones
computables de las que pueden quedar indefinidas. No es posible saber cuando una determinada
entrada no devolverá una salida. Con todos estos datos nos damos cuenta de que las ATM's son
unas máquinas de Turing que funcionan de una manera especial y puesto que las TM's forman una
clase enumerable, las ATM's también. Hay una función ATM calculable por cada ATM y ninguna
más. Cada ATM tiene como las TM's un código asociado que lo identifica. Hay una contradicción
entre ésto y lo que anteriormente se expuso de que no eran enumerables, lo que a algunos autores
les ha llevado a pensar que el término de supertarea es inviable. El problema se debe a las
dificultades del manejo de conceptos que se relacionan con el infinito. Las máquinas de Turing no
están sometidas a ningún comportamiento concreto definido en el tiempo. De este modo es posible
acoplar unas máquinas a otras, permitiendo que funcionen de una manera combinada. Las ATM's
tienen un comportamiento temporal definido, finalizan en k segundos. No es posible combinarlas.
Se puede simular con TM's pero hay aspectos que dependen de la posibilidad de combinar objetos
del mismo tipo y no de simulaciones.

17
Diagonalización

Mostraremos que no podemos contar todas las sucesiones binarias o, en otras palabras, las
sucesiones infinitas de ceros y unos.
Supongamos que pudiéramos y veamos que obtenemos una contradicción. Etiquetamos cada
sucesión binaria B1, B2, B3,... ad infinitum. Como anteriormente, hagamos una lista con los
elementos de cada sucesión en una tabla o matriz.
Definimos ahora una sucesión binaria D, eligiendo un 0 como primer término de la sucesión D si 1
es el primer término de B1 y un 1 si es 0. Entonces, elegimos un 0 como segundo término de D si 1
es el segundo término de B2 y un 1 si es 0, y así sucesivamente. La sucesión binaria resultante, D,
no puede estar en la lista, porque si lo estuviera entonces tendría que coincidir con alguna sucesión
Bn para algún n. Pero nos hemos asegurado deliberadamente que la n-ésima columna de D difiere
de la de Bn, lo que supone una contradicción.
Sin importar cómo hagamos la lista de las sucesiones binarias, siempre encontraremos una nueva
sucesión, D, que no está en la lista.
Este procedimiento se denomina diagonalización. Como se puede ver, hemos obtenido una regla
simple para ello, de tal manera que dada una regla para contar una lista de números binarios siempre
tendríamos otra regla para calcular un número binario diagonal que no está en esa lista.

Ilustración 2: Ejemplo de
diagonalización

18
Conclusión del Autor

Al intentar buscar alternativas se plantean soluciones demasiado abstractas definidas en muchos

casos sin demasiado rigor. Pero se puede destacar que pequeños cambios en el comportamiento
superficial del modelo clásico pueden suponer unos cambios sustanciales respecto a propiedades
formales subyacentes.
La conclusión que se puede obtener del análisis inverso es que el problema de parada y otras
limitaciones aparentes no deben ser vistas como una especie de maldición contra el alcance de
nuestras capacidades cognitivas. Este problema solo parece el precio a pagar por disponer de la
capacidad para nombrar de forma efectiva los objetos de una cierta clase. La enumerabilidad
efectiva de los miembros de un conjunto es una condición necesaria para hablar con propiedad de la
representación completa de una clase de objetos por parte de la intuición matemática. Resolver esta
limitación podría comprometer la seguridad que da saber que nuestra descripción no deja fuera nada
que deba estar dentro. No parece posible alcanzar el paraíso matemático por lo que hace a nuestra
capacidad para describir tareas de forma efectiva.

19
Conclusión Personal

Que el modelo actual está limitado es un hecho evidente, por ello se están buscando diferentes
modelos alternativos que sustituyan mejorando el vigente. No obstante como se ha podido ver
durante todo este trabajo, eso no es tarea nada fácil. Se han propuesto varios modelos que sólo son
posibles en la teoría, pero imposibles de implementar. No es por ser pesimista, pero creo q se está
bastante lejos de hallar un modelo que sustituya al de las máquinas de Turing, ojalá me equivoque.
No obstante, es interesante el hecho de que varios investigadores se dediquen a esta complicada
búsqueda ya que replantean el paradigma actual centrándose en sus carencias y sus limitaciones y
eso es bueno para una evolución a futuros modelos alternativos, que aunque no lleguen a un modelo
en el que todo sea perfecto y todos los problemas estén solucionados, mejoren sustancialmente al
actual. Quizá halla que esperar a que aparezcan otros genios como fueron Turing y Church para
llevar a cabo otra revolución en este campo.

20