Algunos v\u00ednculos <\/b><\/p>\n
entre el teorema de G\u00f6del de 1931 <\/b><\/p>\n
y el resultado de Turing de 1936 [II]<\/b><\/p>\n
\u00a0<\/b><\/p>\n
En 1931, el eminente matem\u00e1tico y l\u00f3gico alem\u00e1n cerrar\u00eda \u2014de una forma inesperada para Hilbert\u2014 las cuestiones de la completitud y de la consistencia de ciertas teor\u00edas matem\u00e1ticas. En definitiva \u2014y de forma breve\u2014 [primer teorema de incompletitud de G\u00f6del] \u201ccualquier teor\u00eda que contenga la aritm\u00e9tica de Peano convenientemente axiomatizada, y sea consistente, es incompleta\u201d. Adem\u00e1s [segundo teorema de incompletitud de G\u00f6del] \u201ces imposible dar una demostraci\u00f3n de la consistencia de la teor\u00eda \u2018dentro\u2019 de la teor\u00eda\u201d.<\/p>\n
Para lograr establecer estos resultados \u2014en particular, el primero\u2014, G\u00f6del recurre a una especie de \u201cpiedra de Rosetta\u201d. Es decir, recurre a tres lenguajes distintos \u2014el lenguaje ordinario, el lenguaje formal y el lenguaje matem\u00e1tico de la aritm\u00e9tica\u2014 para los que establece como se traduce de uno a otro[1]<\/a>, uno de los cuales es el lenguaje de la aritm\u00e9tica de los n\u00fameros naturales entendidos como objetos matem\u00e1ticos y no como objetos formales.<\/p>\n Precisa cuales son los \u2018diccionarios\u2019. Los conjuntos, relaciones y funciones aritm\u00e9ticas \u2018traducibles\u2019 al lenguaje formal son los \u2018primitivos recursivos\u2019, un concepto que en ulteriores trabajos el propio G\u00f6del ampliar\u00e1 \u2018recursivo\u2019. Resulta que las expresiones \u2018metamatem\u00e1ticas\u2019 relativas al lenguaje formal \u2014<\/i>por ejemplo, \u201c<\/i>j<\/i>(v1<\/sub>)<\/i> es una f\u00f3rmula con la \u00fanica variable llibre v1<\/sub><\/i>\u201d, \u201cla sentencia s<\/i> admite una demostraci\u00f3n en la teor\u00eda formal\u201d, etc.\u2014 se pueden transformar en conjuntos o relaciones primitivos recursivos por medio de la g\u00f6delizaci\u00f3n.<\/p>\n Sin embargo, quedaba todav\u00eda en el tintero la cuesti\u00f3n de la decidibilidad de la teor\u00eda, la cual como ya hemos indicado depende de disponer de un concepto \u201cfino\u201d de algoritmo. Este problema ser\u00eda resuelto en 1936, simult\u00e1neamente, por Alonzo Church [1903-1995], y Alan M. Turing [1912-1954].<\/p>\n La presentaci\u00f3n de Turing es por su simplicidad y naturalidad la m\u00e1s comprensible y la que m\u00e1s proyecci\u00f3n ha tenido en la teor\u00eda de la computaci\u00f3n, y m\u00e1s si cabe porque, en el trabajo de 1936, establece la \u201cexistencia de la m\u00e1quina universal\u201d; esto es, una m\u00e1quina U<\/i> que, frente a unos datos, se puede comportar como cualquiera de las m\u00e1quinas de computaci\u00f3n M<\/i>: puede sumarlos, multiplicarlos, etc. Basta con que indiquemos c\u00f3mo queremos que se comporte en cada caso. Formalmente,<\/p>\n U(mM<\/sub>, n1<\/sub>,…,nk<\/sub>):=M(n1<\/sub>,…,nk<\/sub>)<\/i>,<\/p>\n en donde mM<\/sub> <\/i>dice a la m\u00e1quina U <\/i>que debe actuar como la m\u00e1quina M<\/i>; de hecho, cada m\u00e1quina M<\/i> admite un c\u00f3digo num\u00e9rico mM<\/sub><\/i>.<\/p>\n Adem\u00e1s, Turing, en general, usa el mismo lenguaje para dar la \u201cm\u00e1quina\u201d \u2014el programa computacional\u2014 como para realizar la computaci\u00f3n, un avance realmente notable con respecto de quienes, antes que \u00e9l, hab\u00edan intentado ofrecer m\u00e1quinas de c\u00e1lculo. La suya, claro est\u00e1, es una m\u00e1quina te\u00f3rica o formal antes que una m\u00e1quina mec\u00e1nica.<\/p>\n Con este concepto de \u2018computabilidad\u2019 Turing puede establecer dos resultados importantes:<\/p>\n (1) El c\u00e1lculo de predicados de primer orden no es deicible: \u201cninguna \u00a0\u00a0\u00a0 m\u00e1quina puede decidir si una f\u00f3rmula es o no un teorema del \u00a0\u00a0\u00a0\u00a0 c\u00e1lculo de predicados.<\/p>\n (2) Hay problemas que \u2018no\u2019 son computables: as\u00ed aparece el \u201cproblema de la parada\u201d: \u2018no\u2019 es posible construir una m\u00e1quina que, si le damos como entrada, el c\u00f3digo mM\u00a0<\/sub><\/i>de una m\u00e1quina M <\/i>y unos ciertos \u00a0\u00a0\u00a0\u00a0\u00a0 datos num\u00e9ricos n1<\/sub>,…,nk<\/sub><\/i>, nos diga si M(n1<\/sub>,…,nk<\/sub>)<\/i> se parar\u00e1 o continuar\u00e1 procesando indefindamente.<\/p>\n Hemos relacionado, pues, Turing con Hilbert.<\/p>\n Pero, \u00bfqu\u00e9 lo vincula con G\u00f6del? La respuesta nos las dan las \u2018funciones recursivas [parciales]\u2019. Una m\u00e1quina de Turing calcula las funciones recursivas y s\u00f3lo \u00e9stas. Este es un v\u00ednculo muy estrecho entre algunos de los conceptos introducidos por G\u00f6del y algunos de los conceptos introducidos por Turing que justifican, creo, que en 1963 G\u00f6del a\u00f1adiera un ap\u00e9ndice al art\u00edculo de su teorema de 1931 afirmando que las aportaciones de Turing permit\u00edan \u201cuna definici\u00f3n precisa <\/b>e indudablemente adecuada de la noci\u00f3n general de sistema formal de los teoremas vi y xi\u201d.[2]<\/a><\/p>\n <\/p>\n Josep Pla i Carrera<\/p>\n profesor em\u00e9rito de la ub<\/p>\n jpla@ub.edu<\/a><\/p>\n Referencias biblogr\u00e1ficas<\/b><\/p>\n Church, Alonzo (1936). \u201cA note on the Entscheidungsproblem\u201d. Journal of \u00a0\u00a0 Symbolic Logic, <\/i>p\u00e0gs.\u00a040\u201341.<\/p>\n Cutland, Nigel (1980). Computability. An introduction to recursive function theory. <\/i>Cambridge University Press. Cambridge.<\/p>\n G\u00f6del, Kurt (1930).\u201cDie Vollst\u00e4ndigkeit der Axiome des logischen Funktio- nenkalk\u00fcls\u201d. Monatshefte f\u00fcr Mathematik und Physik<\/i>, 37, p\u00e1gs. 349-360. Traducci\u00f3n castellana en G\u00f6del, K. (1981), p\u00e1gs. 20-\u00a0\u00a0\u00a0 34.<\/p>\n G\u00f6del, Kurt (1931).\u201c\u00dbber formal unentscheidbare S\u00e2tze der Principia \u00a0\u00a0\u00a0\u00a0 Mathematica und verwandter System\u201d. Monatshefte f\u00fcr Mathematik und Physik<\/i>, 38, p\u00e1gs. 173-198. Traducci\u00f3n castellana en \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 G\u00f6del, K. (1981), p\u00e1gs. 45-89.<\/p>\n Hilbert, David (1899). Grundlagen der Geometrie<\/i>. Teubner: Sttugart.<\/p>\n [1]<\/a> El lector interesado puede recurrir al cap\u00edtulo 11 de Pla i Carrera, J. (2013).<\/p>\n<\/div>\n [2]<\/a> El lector interesado puede recurrir a Cutland [1980], cap\u00edtulo 8, p\u00e1gs. 143-156.<\/p>\n<\/div>\n","protected":false},"excerpt":{"rendered":" Algunos v\u00ednculos entre el teorema de G\u00f6del de 1931 y el resultado de Turing de 1936 [II] \u00a0 En 1931, el eminente matem\u00e1tico y l\u00f3gico alem\u00e1n cerrar\u00eda \u2014de una forma inesperada para Hilbert\u2014 las cuestiones de la completitud y de la consistencia de ciertas teor\u00edas matem\u00e1ticas. En definitiva \u2014y de forma breve\u2014 [primer teorema de… Seguir leyendo El teorema de G\u00f6del, una aproximaci\u00f3n a la verdad matem\u00e1tica (II)<\/span><\/a><\/p>\n","protected":false},"author":5,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[3,7,9],"tags":[16,96,419],"class_list":["post-3671","post","type-post","status-publish","format-standard","hentry","category-actualidad","category-libros","category-personajes","tag-alan-turing","tag-david-hilbert","tag-kurt-godel","entry"],"_links":{"self":[{"href":"http:\/\/pimedios.jesussoto.es\/index.php?rest_route=\/wp\/v2\/posts\/3671","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/pimedios.jesussoto.es\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/pimedios.jesussoto.es\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/pimedios.jesussoto.es\/index.php?rest_route=\/wp\/v2\/users\/5"}],"replies":[{"embeddable":true,"href":"http:\/\/pimedios.jesussoto.es\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=3671"}],"version-history":[{"count":4,"href":"http:\/\/pimedios.jesussoto.es\/index.php?rest_route=\/wp\/v2\/posts\/3671\/revisions"}],"predecessor-version":[{"id":3674,"href":"http:\/\/pimedios.jesussoto.es\/index.php?rest_route=\/wp\/v2\/posts\/3671\/revisions\/3674"}],"wp:attachment":[{"href":"http:\/\/pimedios.jesussoto.es\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=3671"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/pimedios.jesussoto.es\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=3671"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/pimedios.jesussoto.es\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=3671"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}
\n