https:\/\/www.astro.puc.cl\/~rparra\/tools\/PAPERS\/turing_1936.pdf<\/a><\/p>\nSOBRE N\u00daMEROS COMPUTABLES CON APLICACI\u00d3N AL PROBLEMA DE RESOLUCI\u00d3N<\/p>\n
AM TURING<\/p>\n
[Recibido el 28 de mayo de 1936 – Le\u00eddo el 12 de noviembre de 1936]<\/p>\n
Los n\u00fameros “computables” pueden describirse brevemente como n\u00fameros reales cuyas expresiones como fracciones decimales se pueden calcular de un n\u00famero finito de formas. Aunque a primera vista este art\u00edculo trata los n\u00fameros como computables, es casi igual de f\u00e1cil 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\u00f3n detallada, eleg\u00ed los n\u00fameros computables como objeto computable porque el m\u00e9todo para considerarlos es el menos engorroso. Espero describir pronto la relaci\u00f3n de los n\u00fameros computables con las funciones computables, etc. Paralelamente se realizar\u00e1n investigaciones en el campo de la teor\u00eda de funciones de una variable real expresada en t\u00e9rminos de n\u00fameros computables. Seg\u00fan mi definici\u00f3n, un n\u00famero real es computable si su representaci\u00f3n decimal puede ser escrita por una m\u00e1quina.<\/p>\n
En los p\u00e1rrafos 9 y 10 doy algunos argumentos para demostrar que los n\u00fameros computables incluyen todos los n\u00fameros que naturalmente se consideran computables. En particular, muestro que algunas clases grandes de n\u00fameros son computables. Incluyen, por ejemplo, las partes reales de todos los n\u00fameros algebraicos, las partes reales de los ceros de las funciones de Bessel, los n\u00fameros \u03c0, e y otros. Sin embargo, los n\u00fameros computables no incluyen todos los n\u00fameros definibles, como lo demuestra el siguiente ejemplo de un n\u00famero definible que no es computable.<\/p>\n
Aunque la clase de n\u00fameros computables es muy grande y en muchos aspectos similar a la clase de n\u00fameros reales, sigue siendo enumerable. En el \u00a78 considero ciertos argumentos que parecer\u00edan sostener lo contrario. Cuando uno de estos argumentos se aplica correctamente, se extraen conclusiones que, a primera vista, son similares a las de G\u00f6del*. Estos resultados tienen aplicaciones extremadamente importantes. En particular, como se muestra a continuaci\u00f3n (\u00a711), el problema de resoluci\u00f3n no puede tener soluci\u00f3n.<\/p>\n
En un art\u00edculo reciente, Alonzo Church introdujo la idea de \u201ccalculabilidad efectiva\u201d, que es equivalente a mi idea de \u201ccomputabilidad\u201d, pero tiene una definici\u00f3n completamente diferente. Church tambi\u00e9n llega a conclusiones similares respecto del problema de la resoluci\u00f3n. La prueba de la equivalencia de \u201ccomputabilidad\u201d y \u201cefectivamente calculable\u201d se presenta en el anexo de este art\u00edculo.<\/p>\n
1. Computadoras<\/p>\n
Ya hemos dicho que los n\u00fameros computables son aquellos n\u00fameros cuyas cifras decimales son contables por medios finitos. Aqu\u00ed se necesita una definici\u00f3n m\u00e1s clara. Este art\u00edculo no har\u00e1 ning\u00fan intento real de justificar las definiciones aqu\u00ed dadas hasta que lleguemos al \u00a79. Por ahora, s\u00f3lo se\u00f1alar\u00e9 que la raz\u00f3n (l\u00f3gica) (para esto) es que la memoria humana es, por necesidad, limitada.<\/p>\n
Comparemos a una persona en el proceso de calcular un n\u00famero real con una m\u00e1quina que es capaz de cumplir s\u00f3lo un n\u00famero finito de condiciones q1, q2, …, qR; Llamemos a estas condiciones “configuraciones m”. Esta m\u00e1quina (es decir, as\u00ed definida) est\u00e1 equipada con una \u201ccinta\u201d (an\u00e1loga al papel). Esta cinta que pasa por la m\u00e1quina se divide en tramos. Llam\u00e9moslos “cuadrados”. Cada uno de estos cuadrados puede contener alg\u00fan tipo de “s\u00edmbolo”. En cualquier momento, s\u00f3lo hay uno de esos cuadrados, digamos el r, que contiene el s\u00edmbolo que est\u00e1 “en esta m\u00e1quina”. Llamemos a ese cuadrado “s\u00edmbolo escaneado”. Un “car\u00e1cter escaneado” es el \u00fanico car\u00e1cter del que la m\u00e1quina es, por as\u00ed decirlo, “directamente consciente”. Sin embargo, al cambiar su configuraci\u00f3n m, la m\u00e1quina puede recordar efectivamente algunos de los caracteres que ha “visto” (escaneado) anteriormente. El posible comportamiento de la m\u00e1quina en cualquier momento est\u00e1 determinado por la configuraci\u00f3n m qn y el s\u00edmbolo escaneado***. Llamemos a este par de s\u00edmbolos qn, \u201cconfiguraci\u00f3n\u201d. La configuraci\u00f3n as\u00ed designada determina el posible comportamiento de una m\u00e1quina determinada. En algunas de estas configuraciones en las que el cuadrado escaneado est\u00e1 en blanco (es decir, no contiene un car\u00e1cter), la m\u00e1quina escribe un nuevo car\u00e1cter en el cuadrado escaneado y en otras de estas configuraciones borra el car\u00e1cter escaneado. Esta m\u00e1quina tambi\u00e9n es capaz de moverse para escanear otro cuadrado, pero de esta manera s\u00f3lo puede moverse al cuadrado adyacente a la derecha o a la izquierda. Adem\u00e1s de cualquiera de estas operaciones, se puede cambiar la configuraci\u00f3n m de la m\u00e1quina. En este caso, algunos de los caracteres escritos formar\u00e1n una secuencia de d\u00edgitos, que es la parte decimal del n\u00famero real que se est\u00e1 calculando. El resto no ser\u00e1n m\u00e1s que marcas imprecisas para \u201cayudar a la memoria\u201d. En este caso, s\u00f3lo se podr\u00e1n borrar las marcas inexactas mencionadas anteriormente.<\/p>\n
Afirmo que las operaciones aqu\u00ed consideradas incluyen todas aquellas operaciones que se utilizan en el c\u00e1lculo. El fundamento de esta afirmaci\u00f3n es m\u00e1s f\u00e1cil de entender para el lector que comprende la teor\u00eda de m\u00e1quinas. Por lo tanto, en la siguiente secci\u00f3n continuar\u00e9 desarrollando la teor\u00eda en cuesti\u00f3n, a partir de la comprensi\u00f3n del significado de los t\u00e9rminos \u201cm\u00e1quina\u201d, \u201ccinta\u201d, \u201cescaneado\u201d, etc.<\/p>\n
*G\u00f6del \u201cSobre las oraciones formalmente indecidibles de los Principia Mathematics (publicado por Whitehead y Russell en 1910, 1912 y 1913) y sistemas relacionados, Parte I\u201d, Journal of Mathematics. F\u00edsica, bolet\u00edn mensual en alem\u00e1n n\u00b0 38 (a\u00f1o 1931, p\u00e1gs. 173-198).
\n** Alonzo Church, \u201cUn problema indecidible en la teor\u00eda elemental de n\u00fameros\u201d, American J. of Math., No. 58 (1936), p\u00e1gs. 345-363.
\n*** Alonzo Church, \u201cUna nota sobre el problema de la resoluci\u00f3n\u201d, J. of Symbolic Logic, No. 1 (1936), p\u00e1gs. 40-41<\/p>\n","protected":false},"excerpt":{"rendered":"
Les presento una traducci\u00f3n de las primeras p\u00e1ginas del art\u00edculo de Alan Turing “SOBRE N\u00daMEROS COMPUTABLES CON UNA APLICACI\u00d3N AL PROBLEMA DE RESOLUCI\u00d3N” de 1936. Los primeros cap\u00edtulos contienen una descripci\u00f3n de las computadoras, que luego se convirtieron en la base de la inform\u00e1tica moderna. La traducci\u00f3n completa del art\u00edculo y la explicaci\u00f3n se pueden […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[8],"tags":[],"class_list":["post-70","post","type-post","status-publish","format-standard","hentry","category-notes"],"translation":{"provider":"WPGlobus","version":"3.0.6","language":"es","enabled_languages":["en","ru","zh","de","ja","fr","es","pt","hi"],"languages":{"en":{"title":true,"content":true,"excerpt":false},"ru":{"title":true,"content":true,"excerpt":false},"zh":{"title":true,"content":true,"excerpt":false},"de":{"title":true,"content":true,"excerpt":false},"ja":{"title":true,"content":true,"excerpt":false},"fr":{"title":true,"content":true,"excerpt":false},"es":{"title":true,"content":true,"excerpt":false},"pt":{"title":true,"content":true,"excerpt":false},"hi":{"title":true,"content":true,"excerpt":false}}},"_links":{"self":[{"href":"https:\/\/demensdeum.com\/blog\/es\/wp-json\/wp\/v2\/posts\/70","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/demensdeum.com\/blog\/es\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/demensdeum.com\/blog\/es\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/demensdeum.com\/blog\/es\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/demensdeum.com\/blog\/es\/wp-json\/wp\/v2\/comments?post=70"}],"version-history":[{"count":2,"href":"https:\/\/demensdeum.com\/blog\/es\/wp-json\/wp\/v2\/posts\/70\/revisions"}],"predecessor-version":[{"id":189,"href":"https:\/\/demensdeum.com\/blog\/es\/wp-json\/wp\/v2\/posts\/70\/revisions\/189"}],"wp:attachment":[{"href":"https:\/\/demensdeum.com\/blog\/es\/wp-json\/wp\/v2\/media?parent=70"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/demensdeum.com\/blog\/es\/wp-json\/wp\/v2\/categories?post=70"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/demensdeum.com\/blog\/es\/wp-json\/wp\/v2\/tags?post=70"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}