Finite Combinatory Processes
Etapa 1 · Los fundamentos (1763–1942) › Computabilidad
- Linaje
- Símbolos y lógica
- Tipo
- Publicación
Quién
City College de Nueva York
Qué ocurrió
Emil Post publica en el Journal of Symbolic Logic «Finite Combinatory Processes. Formulation 1», tres páginas que describen a un trabajador que marca casillas siguiendo instrucciones, un modelo de cálculo casi idéntico a la máquina de Turing.
Qué aportó
Tercera definición independiente de qué es un cálculo mecánico, publicada el mismo año que las de Church y Turing. Su estilo, reglas que reescriben cadenas de símbolos, reaparece en los sistemas de producción de la IA simbólica.
Desarrollo
Emil Post, nacido en 1897 en Augustów, en la Polonia entonces rusa, emigró de niño a Nueva York. En su tesis de 1920 había demostrado que la lógica de proposiciones es consistente y completa, y en los años veinte llegó por su cuenta a ideas cercanas a la incompletitud, que no publicó. Trabajaba como profesor de secundaria y, desde 1936, en el City College de Nueva York.
Su artículo de 1936 ocupa tres páginas y empieza situándose junto al teorema de Gödel y los resultados de Church sobre problemas sin solución. Describe un espacio de casillas en fila y un trabajador que solo puede hacer unas pocas cosas: marcar la casilla en la que está, borrarla, moverse a la de al lado y comprobar si está marcada para elegir la instrucción siguiente. Post propone que todo lo que se puede calcular con un procedimiento finito se puede calcular así.
Es casi lo mismo que la máquina de Turing, que se publicaba en Londres esos mismos meses. Una nota del artículo lo advierte: invita a compararlo con el de Turing y aclara que se escribió de forma completamente independiente.
Post siguió por un camino propio. En los años cuarenta estudió sistemas que transforman cadenas de símbolos mediante reglas de reescritura, y con ellos se demostró que ciertos problemas de palabras no tienen solución. Esa forma de describir un cálculo como reglas que reescriben símbolos es la que retoman la teoría de lenguajes formales y los sistemas de reglas de la IA simbólica.
Viene de
Teoremas de incompletitud (1931), Cálculo lambda y problema irresoluble (abril de 1936)
Influencia directa documentada
El artículo se presenta desde la primera frase como un desarrollo en la línea del teorema de incompletitud de Gödel y de los problemas sin solución de Church
Lleva a
On Computable Numbers (30 de noviembre de 1936)
Convergencia independiente
Dos modelos casi idénticos de cálculo mecánico, escritos por separado; una nota del artículo de Post invita a compararlo con el de Turing y aclara que se escribió de forma independiente
Hilos que pasan por aquí
- De la pregunta de Hilbert a la máquina universal (paso 6 de 7)
Bibliografía
Fuente original
Estudios y contexto
Cómo citar
«Finite Combinatory Processes». En La historia de la IA, revisión del 13 de noviembre de 2026. https://thehistoryofai.com/es/hito/post-procesos-combinatorios
Última revisión de esta ficha: 13 de noviembre de 2026.