Les presento una traducción de las primeras páginas del artículo de Alan Turing “SOBRE NÚMEROS COMPUTABLES CON UNA APLICACIÓN AL PROBLEMA DE RESOLUCIÓN” de 1936. Los primeros capítulos contienen una descripción de las computadoras, que luego se convirtieron en la base de la informática moderna.
La traducción completa del artículo y la explicación se pueden leer en el libro del divulgador estadounidense Charles Petzold, titulado “Reading Turing: A Journey Through Turing’s Historical Article on Computability and Turing Machines” (ISBN 978-5-97060-231-7, 978-0-470-22905-7)
Artículo original:
https://www.astro.puc.cl/~rparra/tools/PAPERS/turing_1936.pdf
SOBRE NÚMEROS COMPUTABLES CON APLICACIÓN AL PROBLEMA DE RESOLUCIÓN
AM TURING
[Recibido el 28 de mayo de 1936 – Leído el 12 de noviembre de 1936]
Los números “computables” pueden describirse brevemente como números reales cuyas expresiones como fracciones decimales se pueden calcular de un número finito de formas. Aunque a primera vista este artículo trata los números como computables, es casi igual de fácil definir y explorar funciones computables de una variable entera, una variable real, una variable computable, predicados computables y similares. Sin embargo, los problemas fundamentales asociados con estos objetos computables son los mismos en cada caso. Para una consideración detallada, elegí los números computables como objeto computable porque el método para considerarlos es el menos engorroso. Espero describir pronto la relación de los números computables con las funciones computables, etc. Paralelamente se realizarán investigaciones en el campo de la teoría de funciones de una variable real expresada en términos de números computables. Según mi definición, un número real es computable si su representación decimal puede ser escrita por una máquina.
En los párrafos 9 y 10 doy algunos argumentos para demostrar que los números computables incluyen todos los números que naturalmente se consideran computables. En particular, muestro que algunas clases grandes de números son computables. Incluyen, por ejemplo, las partes reales de todos los números algebraicos, las partes reales de los ceros de las funciones de Bessel, los números π, e y otros. Sin embargo, los números computables no incluyen todos los números definibles, como lo demuestra el siguiente ejemplo de un número definible que no es computable.
Aunque la clase de números computables es muy grande y en muchos aspectos similar a la clase de números reales, sigue siendo enumerable. En el §8 considero ciertos argumentos que parecerían sostener lo contrario. Cuando uno de estos argumentos se aplica correctamente, se extraen conclusiones que, a primera vista, son similares a las de Gödel*. Estos resultados tienen aplicaciones extremadamente importantes. En particular, como se muestra a continuación (§11), el problema de resolución no puede tener solución.
En un artículo reciente, Alonzo Church introdujo la idea de “calculabilidad efectiva”, que es equivalente a mi idea de “computabilidad”, pero tiene una definición completamente diferente. Church también llega a conclusiones similares respecto del problema de la resolución. La prueba de la equivalencia de “computabilidad” y “efectivamente calculable” se presenta en el anexo de este artículo.
1. Computadoras
Ya hemos dicho que los números computables son aquellos números cuyas cifras decimales son contables por medios finitos. Aquí se necesita una definición más clara. Este artículo no hará ningún intento real de justificar las definiciones aquí dadas hasta que lleguemos al §9. Por ahora, sólo señalaré que la razón (lógica) (para esto) es que la memoria humana es, por necesidad, limitada.
Comparemos a una persona en el proceso de calcular un número real con una máquina que es capaz de cumplir sólo un número finito de condiciones q1, q2, …, qR; Llamemos a estas condiciones “configuraciones m”. Esta máquina (es decir, así definida) está equipada con una “cinta” (análoga al papel). Esta cinta que pasa por la máquina se divide en tramos. Llamémoslos “cuadrados”. Cada uno de estos cuadrados puede contener algún tipo de “símbolo”. En cualquier momento, sólo hay uno de esos cuadrados, digamos el r, que contiene el símbolo que está “en esta máquina”. Llamemos a ese cuadrado “símbolo escaneado”. Un “carácter escaneado” es el único carácter del que la máquina es, por así decirlo, “directamente consciente”. Sin embargo, al cambiar su configuración m, la máquina puede recordar efectivamente algunos de los caracteres que ha “visto” (escaneado) anteriormente. El posible comportamiento de la máquina en cualquier momento está determinado por la configuración m qn y el símbolo escaneado***. Llamemos a este par de símbolos qn, “configuración”. La configuración así designada determina el posible comportamiento de una máquina determinada. En algunas de estas configuraciones en las que el cuadrado escaneado está en blanco (es decir, no contiene un carácter), la máquina escribe un nuevo carácter en el cuadrado escaneado y en otras de estas configuraciones borra el carácter escaneado. Esta máquina también es capaz de moverse para escanear otro cuadrado, pero de esta manera sólo puede moverse al cuadrado adyacente a la derecha o a la izquierda. Además de cualquiera de estas operaciones, se puede cambiar la configuración m de la máquina. En este caso, algunos de los caracteres escritos formarán una secuencia de dígitos, que es la parte decimal del número real que se está calculando. El resto no serán más que marcas imprecisas para “ayudar a la memoria”. En este caso, sólo se podrán borrar las marcas inexactas mencionadas anteriormente.
Afirmo que las operaciones aquí consideradas incluyen todas aquellas operaciones que se utilizan en el cálculo. El fundamento de esta afirmación es más fácil de entender para el lector que comprende la teoría de máquinas. Por lo tanto, en la siguiente sección continuaré desarrollando la teoría en cuestión, a partir de la comprensión del significado de los términos “máquina”, “cinta”, “escaneado”, etc.
*Gödel “Sobre las oraciones formalmente indecidibles de los Principia Mathematics (publicado por Whitehead y Russell en 1910, 1912 y 1913) y sistemas relacionados, Parte I”, Journal of Mathematics. Física, boletín mensual en alemán n° 38 (año 1931, págs. 173-198).
** Alonzo Church, “Un problema indecidible en la teoría elemental de números”, American J. of Math., No. 58 (1936), págs. 345-363.
*** Alonzo Church, “Una nota sobre el problema de la resolución”, J. of Symbolic Logic, No. 1 (1936), págs. 40-41
Leave a Reply