|
Máquina de Turing
La máquina de Turing es un modelo computacional introducido por Alan Turing en el trabajo “On computable numbers, with an application to the Entscheidungsproblem”, publicado por la Sociedad Matemática de Londres, en el cual se estudiaba
la cuestión planteada por David Hilbert sobre si las matemáticas son decidibles, es decir, si hay un método definido que pueda aplicarse a cualquier
sentencia matemática y que nos diga si esa sentencia es cierta o no. Turing construyó un modelo formal de computador, la máquina
de Turing, y demostró que existían problemas que una máquina no podía resolver. La máquina de Turing es un modelo matemático
abstracto que formaliza el concepto de algoritmo.
Diagrama
artístico de una máquina de Turing.
Descripción
La máquina de Turing consta de un cabezal lector/escritor
y una cinta infinita en la que el cabezal lee el contenido, borra el contenido anterior y escribe un nuevo valor. 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 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.
Con este aparato extremadamente sencillo es posible
realizar cualquier cómputo que un computador digital sea capaz de realizar.
Mediante este modelo
teórico y el análisis de complejidad de algoritmos, fue posible la categorización de problemas computacionales de acuerdo a su comportamiento, apareciendo
así, el conjunto de problemas denominados P y NP, cuyas soluciones en tiempo polinómico son encontradas según el determinismo y no determinismo respectivamente de la máquina de Turing.
De hecho, se puede
probar matemáticamente que para cualquier programa de computadora es posible crear una máquina de Turing equivalente. Esta prueba resulta de la
Tesis de Church-Turing, formulada por Alan Turing y Alonzo Church, de forma independiente a mediados del siglo XX.
La idea subyacente
en el concepto de máquina de Turing es una persona ejecutando un procedimiento efectivo definido formalmente, donde el espacio
de memoria de trabajo es ilimitado, pero en un momento determinado sólo una parte finita es accesible. 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 la leer la celda siguiente, bien a la izquierda o bien a la derecha. La máquina
de Turing puede considerarse como un autómata capaz de reconocer lenguajes formales. En ese sentido es capaz de reconocer los lenguajes recursivamente
enumerables, de acuerdo a la jerarquía de Chomsky. Su potencia es, por tanto, superior a otros tipos de autómatas, como el autómata finito, o el autómata con pila, o igual a otros modelos con la misma potencia computacional.
Una máquina de Turing con una
sola cinta puede ser definida como una 6-tupla M = (Q, Γ, s, b, F, δ), donde
- Q
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.
Existen en la literatura
un abundante número de definiciones alternativas, pero todas ellas tienen el mismo poder computacional, por ejemplo se puede
añadir el símbolo S como símbolo de "no movimiento" en un paso de cómputo.
Ejemplo
Definimos una máquina
de Turing sobre el alfabeto {'0', '1'}, donde 0 representa el símbolo blanco. La máquina comenzará su proceso situada sobre
un símbolo "1" de una serie. La máquina de Turing copiará el número de símbolos "1" que encuentre hasta el primer blanco detrás
de dicho símbolo blanco. Es decir, situada sobre el 1 situado en el extremo izquierdo, doblará el número de símbolos 1, con
un 0 en medio. Así, si tenemos la entrada "111" devolverá "1110111", con "1111" devolverá "111101111", y sucesivamente.
El conjunto de estados
es {s1, s2, s3, s4, s5} y el estado inicial es s1. La tabla que describe la función de transición es la siguiente: Estado Símbolo Símbolo Mov. Estado
Estado Símbolo Símbolo Mov.
Estado Leido escrito
sig.
leido escrito
sig. - - - - - - - - - - - - - - - - - - - -
- - - - - - - - - - - - - - - - - - - - s1 1 -> 0
R s2
s4 1
-> 1
L s4 s2
1 -> 1 R
s2
s4 0
-> 0 L s5 s2
0 -> 0 R
s3
s5 1
-> 1
L s5 s3
0 -> 1 L
s4
s5 0
-> 1
R s1 s3 1 -> 1
R s3
El funcionamiento de
una computación de esta máquina se puede mostrar con el siguiente ejemplo (en negrita se resalta la posición de la cabeza
lectora/escritora): Paso Estado Cinta Paso Estado Cinta - - - - - - - - - - - - - - - - - - - - - - - 1 s1 11 9 s2 1001 2 s2 01
10 s3 1001 3 s2 010 11
s3 10010 4 s3
0100 12 s4 10011 5 s4 0101 13 s4
10011
6 s5 0101
14 s5 10011 7 s5 0101 15
s1 11011 8 s1 1101
-- Parada --
La máquina realiza
su proceso por medio de un bucle, en el estado inicial s1, reemplaza el primer 1 con un 0, y pasa al estado s2, con el que
avanza hasta la derecha, saltando los símbolos 1 hasta un 0 (que debe existir), cuandolo encuentra pasa a ser s3, con este
estado avanza saltando los 1 hasta encontrar otro 0 (la primera vez no habría ningún 1). Una vez en el extremo derecho, añade
un 1. Después comienza elproceso de retorno; con s4 vuelve a la izquierda saltando los 1, cuand encuentra un 0 (en el medio
de la secuencia), pasa a s5 que continúa a la izquierda saltando los 1 hasta el 0 que se escribió al principio. Se reemplaza
de nuevo este 0 por 1, y pasa al símbolo siguiente, si es un 1, se pasa a otra iteración del bucle, pasando al estado s1 de
nuevo. Si es un símbolo 0, será el símbolo central, con lo que la máquina se detiene al haber finalizado su cómputo.
[editar]
Máquinas de Turing deterministas
y no deterministas
La entrada de una máquina
de Turing viene determinada por el estado actual y el símbolo leído, siendo el cambio de estado, la escritura de un nuevo
símbolo y el movimiento las acciones a tomar en función de una entrada. En el caso de que para cada par estado y símbolo posible
exista a lo sumo una posibilidad de ejecución, diremos que es una máquina de Turing determinista, mientras que en el caso
de que exista al menos un par (estado, símbolo) con más de una posible combinación de actuaciones diremos que se trata de
una máquina de Turing No Determinista.
La función de transición
δ en el caso no determinista, queda definida como sigue:
La capacidad de cómputo
de ambas versiones es equivalente; se puede demostrar que dada una máquina de Turing no determinista existe otra máquina de
Turing determinista equivalente, en el sentido de que reconoce el mismo lenguaje, y viceversa. No obstante, la velocidad de
ejecución de ambos formalismos no es la misma, pues si una máquina no determinista M reconoce una cierta palabra de tamaño
n en un tiempo O(t(n)), la máquina determinista equivalente reconocerá la
palabra en un tiempo O(2t(n)). Es decir, el no determinismo
permitirá reducir la complejidad de la solución de los problemas, permitiendo resolver, por ejemplo, problemas de complejidad
exponencial en un tiempo polinómico (Ver complejidad computacional).
[editar]
Máquina Universal de Turing
Una máquina de Turing
computa una determinada función parcial de carácter definido, y unívoca, definida sobre las secuencias de posibles cadenas
de símbolos de su alfabeto. En este sentido se puede considerar como equivalente a un programa de ordenador, o lo que es lo mismo, a un algoritmo. Sin embargo es posible realizar una codificación de la tabla que representa a una máquina de Turing,
a su vez, como una secuencia de símbolos en un determinado alfabeto; por ello, podemos construir una máquina de Turing que
acepte como entrada la tabla que representa a otra máquina de Turing, y, de esta manera, simule su comportamiento.
En 1947, Turing indicó:
Se puede demostrar
que es posible construir una máquina especial de este tipo que pueda realizar el trabajo de todas las demás. Esta máquina
especial puede ser denominada máquina universal.
Esta fue, posiblemente,
la idea germinal del concepto de Sistema Operativo, un programa que puede, a su vez, ejecutar en el sentido de controlar otros programas, demostrando su
existencia, y abriendo camino para su construcción real.
Con esta codificación
de tablas como cadenas, se abre la posiblidad de que unas máquinas de Turing se comporten como otras máquinas de Turing. Sin
embargo, muchas de sus posibilidades son indecidibles, pues no admiten una solución algorítmica. Por ejemplo, un interesante problema es determinar si una
máquina de Turing cualquiera se parará en un tiempo finito sobre una determinada entrada; problema conocido como Problema de la parada, y que Turing demostró que era indecidible. En general, se puede demostrar que cualquier cuestión no
trivial sobre el comportamiento o la salida de una máquina de Turing es un problema indecidible.
Presentaremos algunas variantes de las máquinas de Turing y veremos que son equivalentes. Mostraremos las equivalencias
entre las diversas modificaciones de las máquinas de Turing de manera más bien coloquial. Anque se puede presentar demostraciones
rigurosas en base a descripciones instantáneas, aquí las omitiremos con la certeza de que el lector podrá construirlas a partir
de las indicaciones que presentamos. denotará a la clase de máquinas de Turing tal como las hemos definido. Diremos que dos clases de máquinas y
son equivalentes si toda máquina en una clase es simulada por una máquina en la otra, es decir,
donde c y d son funciones apropiadas de conversión
de palabras de un alfabeto a otro, considerando los alfabetos de ambas máquinas, que cumplen además .
Máquinas con cintas semi-infinitas, :
Estas son máquinas de Turing donde las casillas de la cinta se ponen en correspondencia con mas
no con , es decir, la cinta de cada máquina de esta clase tiene una casilla inicial a la izquierda, digamos c0,
y se prolonga indefinidamente a la derecha.
Proposición
6.1 y son equivalentes.
En efecto, por un lado, tenemos que toda máquina es
en sí del tipo . Recíprocamente, enumeremos las casillas de la cinta semi-infinita C como Dada
una máquina M del tipo enumeremos a las casillas de la cinta de M como Pongamos
un símbolo especial S en c0 e identifiquemos al sector ``negativo'' de la cinta de M con las
casillas impares de C y al ``no-negativo'' de M con las casillas pares de C:
Observamos que el movimiento hacia una casilla contigua en la cinta de M se traduce a dos movimientos
contiguos en C. Cada vez que se ``atraviesa'' S en C se cambia de sentido: Un movimiento a la derecha
en M corresponde a dos hacia la izquierda en C y viceversa. Hechas estas observaciones, de manera directa se
puede simular a M usando C. Máquinas con cintas de varias pistas,
:
Estas son máquinas de Turing cuyas cintas tienen varias ``pistas''. Pueden verse también como máquinas de varias cintas con
movimientos ``sincronizados'': Movimiento que se hace en una cinta, se hace en todas.
Proposición
6.2 y son equivalentes.
En efecto, por un lado, tenemos que toda máquina es
en sí del tipo . Recíprocamente, dada una máquina Mk del tipo con
k pistas, la podemos simular con una máquina M del tipo de
cualquiera de las dos maneras alternativas:
1.
Si A es el alfabeto de Mk, entonces en cada momento el funcionamiento de Mk
depende de la lista de k símbolos que aparece en la casilla actual, consistente de k casillas, una por cada
pista. Esto define a una máquina del del tipo sobre el alfabeto Ak que es una potencia cartesiana del original.
2.
Consideremos una cinta de una sola pista en donde sus casillas se agrupan en bloques de k casillas. La
posición j-ésima de la i-ésima pista en la cinta de Mk corresponde a la posición -ésima
de la nueva cinta. En esta nueva, casillas contiguas en lamisma pista de Mk distanciarán de k casillas.
El mecanismo de funcionamiento se modifica para que cada movimiento de Mk obligue a revisar un bloque de
k casillas y haga la modificación correspondiente, trabajando siempre en bloques.
Máquinas con cintas de varias cintas,
: Estas son máquinas de Turing con varias cintas con movimientos ``independientes''.
Proposición
6.3 y son equivalentes.
Demostraremos que y son equivalentes. En efecto, por un lado, tenemos que toda máquina es
en sí del tipo . Recíprocamente, dada una máquina del tipo con k pistas, la podemos simular con una máquina del
tipo , con 2k pistas como sigue: Cada cinta Cj da origen a dos pistas Pj0,Pj1.
La pista Pj1 tiene el mismo contenido que la cinta Cj. La pista Pj0
está en blanco salvo en la posición donde se encuentra la j-ésima cabeza lectora de ,
en la cual hay una marca `` '' para marcar que ésa es la casilla escudriñada en la j-ésima cinta. Con esto, la máquina se construye de manera inmediata. Máquinas con dos símbolos,
:
Estas son máquinas de Turing sobre el alfabeto (0+1).
Proposición
6.4 y son equivalentes.
En efecto, por un lado, tenemos que toda máquina es
en sí del tipo . Recíprocamente, dada una máquina M del tipo sobre
un alfabeto con m símbolos, sea . Cada símbolo en el alfabeto puede codificarse mediante una cadena de k bits. Por tanto M puede
verse como una m''aquina de k pistas. De acuerdo con la segunda construcción de la máquina del tipo simuladora
de una máquina del tipo, ob tenemos una máquina del tipo que simula a M.
Jerarquía de Chomsky
Saltar a navegación, búsqueda
En lingüística la jerarquía
de Chomsky es una clasificación jerárquica de distintos tipos de gramáticas formales que generan lenguajes formales. Esta jerarquía fue descrita por Noam Chomsky en 1956.
La jerarquía
La Jerarquía de Chomsky consta de cuatro
niveles:
- Gramáticas de
tipo 0 (sin restricciones), que incluye a todas las gramáticas formales. Estas gramáticas generan todos los lenguajes capaces
de ser reconocidos por una máquina de Turing. Los lenguajes son conocidos como lenguajes recursivamente
enumerables. Nótese que esta categoría es diferente de la de los lenguajes recursivos, cuya decisión puede ser realizada por una máquina de Turing que se detenga.
- Gramáticas de
tipo 1 (gramáticas sensibles al contexto) generan los lenguajes sensibles al contexto. Estas gramáticas tienen reglas de la forma con
A a no terminal y α, β y
γ cadenas de terminales y no terminales. Las cadenas α y β pueden ser vacías, pero γ no puede serlo. La regla está
permitida si S no aparece en la parte derecha de ninguna regla. Los lenguajes descritos
por estas gramáticas son exactamente todos aquellos lenguajes reconocidos por una máquina de Turing no determinista cuya cinta de memoria está acotada por un cierto número entero de veces sobre la longitud
de entrada.
- Gramáticas de
tipo 3 (gramáticas regulares) generan los lenguajes regulares. Estas gramáticas se restringen a aquellas reglas que tienen en la parte izquierda un no terminal, y
en la parte derecha un solo terminal, posiblemente seguido de un no terminal. La regla también
está permitida si S no aparece en la parte derecha de ninguna regla. Estos lenguajes son
aquellos que pueden ser aceptados por un autómata finito. También esta familia de lenguajes pueden ser obtenidas por medio de expresiones regulares.
Nótese que el conjunto
de gramáticas correspondiente a los lenguajes recursivos no es un miembro de la jerarquía.
Cada lenguaje regular
es a su vez libre del contexto, asimismo un lenguaje libre del contexto es también dependiente del contexto, éste es recursivo
y a su vez, recursivamente enumerable. Las inclusiones son, sin embargo, propias, es decir, existen en cada nivel lenguajes
que no están en niveles anteriores.
[editar]
Lenguajes Recursivamente Enumerables
(de tipo 0)
Artículo principal: Lenguaje recursivamente enumerable
Las gramáticas que
generan estos lenguajes pueden tener reglas compresoras.
[editar]
Lenguajes Dependientes del Contexto
(sensibles al contexto, de tipo 1)
No existen reglas compresoras,
salvo, opcionalmente, la que deriva el axioma a la palabra vacía.
Existen reglas en las
que un símbolo no terminal puede derivar a formas sentenciales distintas, según los símbolos que aparezcan a su alrededor
[editar]
Lenguajes Independientes del Contexto
(de contexto libre, de tipo 2)
La mayoría de los lenguajes de programación entran en ésta categoría.
[editar]
Lenguajes Regulares (de tipo 3)
Se pueden expresar también mediante expresiones regulares. Ampliar lenguaje regula
Una gramática libre de contexto G=(V,T,P,S) se dice estar en forma normal de Chomsky si sus producciones son de cualquiera de las dos formas
Proposición
3.1 Toda gramática libre de contexto G=(V,T,P,S) que no genere a la palabra vacía
se puede transformar en una gramática libre de contexto G'=(V',T,P',S') en forma normal
de Chomsky.
En efecto, dada una gramática G, apliquemos el último procedimiento de la sección anterior para transformar
a G en una gramática G'' sin variables inútiles ni producciones vacías ni producciones unitarias equivalente
a G. A las producciones que quedasen de la forma con y las dejamos sin cambio alguno. A cada producción de la forma ,
con y , la transformamos en una sucesión de producciones de la forma siguiente: A cada símbolo terminal que
aparezca en la palabra le asociamos una variable nueva Xa e incorporamos la producción .
Así pues las producciones que no sean de la forma con X variable y a terminal, han de ser de la forma ,
con todos variables. Para cada una de estas últimas producciones introducimos k-2 nuevas variables e
incorporamos la sucesión de producciones
Obtenemos así la forma normal equivalente a la gramática dada.
Una gramática libre de contexto G=(V,T,P,S) se dice estar en forma normal de Greibach si sus producciones son de la forma
Veremos que la construcción de formas normales de Greibach equivalentes a gramáticas dadas es procedimental.
Para cualquier gramática libre de contexto G, definamos, para cada variable ,
a los conjuntos siguientes:
Primeramente observemos que podemos ``componer producciones'' de manera que tengamos siempre
una gramática equivalente a la gramática dada.
Lema 3.1 (Composición de producciones)
Si es una producción en G y las producciones en P(Y) pueden escribirse como entonces al sustituir por las producciones ,
obtenemos una gramática equivalente a G.
En efecto, en toda derivación terminal que aplique en un momento la producción ,
necesariamente se ha de aplicar una producción en P(Y) para suprimir el símbolo Y.
Lema 3.2 (Transformación de producciones
``reflexivas'') Para cada variable enumeremos Q(X) y R(X) como
Sea Z una variable que no ocurra en V. Sea la
gramática que se obtiene al sustituir el conjunto de producciones P(X) por las producciones
En efecto, toda derivación siniestra, en la gramática original, de una palabra en L(G) ha de determinar
una derivación diestra de la misma palabra en la gramática transformada. La demostración de la afirmación anterior es directa.
Como mera ilustración, consideremos tan solo un ejemplo: La gramática con producciones genera
al lenguaje consistente de las palabras de la forma b (ab)*. De acuerdo con la construcción anterior,
como y , obtenemos la gramática
Presentemos sendas derivaciones, siniestra en la gramática original y diestra en la transformada, para la palabra
bababab:
Veamos ahora el resultado principal de esta sección:
Proposición
3.2 Toda gramática libre de contexto G=(V,T,P,S) que no genere a la palabra vacía
se puede transformar en una gramática libre de contexto G*=(V*,T,P*,S*)
en forma normal de Greibach.
Sea pues G=(V,T,P,S) una gramática libre de contexto que no genere a .
La transformación a una forma normal de Greibach la hacemos gradualmente mediante los pasos siguientes:
1.
Sea G'=(V',T,P',S') la forma normal de Chomsky de G.
2.
Modificaremos a las producciones en P' para tenerlas tales que toda producción, cuyo consecuente se inicie
con una variable, ha de ser de la forma con j>i, para un cierto orden en el conjunto de variables actuales, digamos .
Para esto apliquemos el procedimiento cuyo seudocódigo se presenta en la figura
|
Figure
6.3: Modificaciónde producciones de acuerdo con el orden de V'. |
|
|
Por lo visto en el lema , la gramática G'' así obtenida es equivalente a G.
3.
Ahora, hecha la transformación anterior, se tiene que
·
la última variable Xm sólo puede ser antecedente de
producciones cuyos consecuentes se inician con símbolos terminales,
·
las producciones en P(Xm-1) cuyos
consecuentes se inician con Xm pueden transformarse, siguiendo el lema de ``Composición de producciones'',
en producciones equivalentes cuyos consecuentes se inician con símbolos terminales,
·
de manera sucesiva para i=m-2 hasta i=1 las producciones
en P(Xi) cuyos consecuentes se inician con algún Xj, con j>i,
pueden transformarse, siguiendo el lema de ``Composición de producciones'', en producciones equivalentes cuyos consecuentes
se inician con símbolos terminales.
Con todas estas transformaciones la gramática resultante G*=(V*,T,P*,S*)
es, en efecto, equivalente a G y está en forma normal de Greibach.
Hilbert era uno de los matemáticos más prominentes de su generación. Poco tiempo después de haberse doctorado,
se interesó en la teoría de invariantes algebraicos. (Por ejemplo, dada una forma cuadrática, el determinante de la matriz
correspondiente es invariante bajo rotaciones). En 1888, a
los 26 años, Hilbert demostró que, dada una forma algebraica, existe un número finito de invariantes que generan a todos los
demás. (Una especie de base). Con este resultado y con su trabajo posterior, Hilbert prácticamente resolvió todos los problemas
interesantes que había sobre invariantes.
Habiendo agotado ese tema, se dedico a la Teoría de Números. Rápidamente descubrió unas demostraciones de la trascendencia de ð y
de e más simples y directas que las demostraciones originales. Su principal contribución fue una generalización de la Ley de Reciprocidad Cuadrática (publicada en 1898), que les permitió a él
y a matemáticos posteriores extender la Teoría de
Números a campos más abstractos y generales.
Entonces, volvió a cambiar de tema. En 1899 publicó el libro “Fundamentos
de la Geometría”. Una exposición axiomática
de la Geometría (Euclidiana y No Euclidiana) que
se sujeta a los requisitos más estrictos del rigor matemático que se estaban desarrollando en el momento y que son la norma
hoy en día. A partir de entonces, Hilbert estuvo muy interesado en los Fundamentos de las Matemáticas. En particular, se preocupó
por la existencia de una colección de axiomas que fuera consistente y completa.
Para la solución de ciertas ecuaciones que aparecen en la
Física, un método muy común es encontrar una función que minimice cierta integral (El Principio de Dirichlet).
Como el problema proviene de una situación física, la gente simplemente asumía la existencia de dicha función minimizadora.
Pero a mediados del siglo XIX, Weierstrass dio ejemplos donde no existía tal función. Sin embargo, el Principio de Dirichlet
parece tan simple y natural que Hilbert decidió tratar de rescatarlo. Y en Septiembre de 1899 publicó un artículo donde demostró
que, bajo ciertas condiciones, el Principio de Dirichlet es válido. Dichas condiciones son satisfechas por los problemas que
aparecen más comúnmente en la Física, pero excluyen
los ejemplos puramente matemáticos de Weierstrass.
Es claro que Hilbert estaba interesado en varias áreas de las Matemáticas.
Su método de trabajo consistía en concentrarse en algún problema y tratar de simplificarlo, de hacerlo más claro. Para él,
el rigor matemático era una herramienta en este proceso. A través del rigor, uno puede evitar las falsas suposiciones que
pueden llevar al error y a la confusión.
Con su prestigio en aumento, Hilbert recibió una invitación para dar una
conferencia plenaria en el Segundo Congreso Internacional de Matemáticas en 1900. Esta fue la conferencia “Problemas
Matemáticos”. En ella habló de la importancia de un buen problema para el impulso de las Matemáticas y de su convicción
filosófica de que dado cualquier problema matemático, tarde ó temprano se le encontrará una solución.
Fue así que
propuso una lista de 23 problemas, no como un reto, sino como un incentivo para los matemáticos del nuevo siglo. Esta lista
es conocida como “Los Problemas de Hilbert” y consta de problemas importantes en Teoría de Números, Álgebra, Geometría,
Análisis, Teoría de Conjuntos y Fundamentos Axiomáticos.
La lista incluye problemas tan famosos como la Hipótesis del Continuo. Al intentar la solución de los problemas, el
objetivo de Hilbert de estimular el crecimiento de las Matemáticas se ha cumplido con creces. Aún hoy, el sueño de muchos
matemáticos es contribuir a la solución de alguno de ellos e ingresar así a la elite que se conoce no oficialmente como “The
Honors Class”.
En este momento, de los 23 problemas, 16 se consideran básicamente resueltos, 4 son más programas
de trabajo que problemas concretos, y 3 permanecen sin resolver (a esta categoría pertenece el problema #8; La Hipótesis de Riemann). En futuros artículos iremos comentando con mayor
detalle algunos de los problemas.
|
