Teoria De La Coputabilidad

TEOR´ DE LA COMPUTABILIDAD
IA
J. Climent Vidal.
1.

´
Descripcion.

La teor´ de la computabilidad, tambi´n denominada teor´ de la recurıa
e
ıa
si´n, es una de las cuatro partes que constituyen lal´gica matem´tica, sieno
o
a
do las otras tres, la teor´ de conjuntos, la teor´ de modelos y la teor´
ıa
ıa
ıa
de la demostraci´n, y se ocupa del estudio y clasificaci´n de las relaciones
o
o
yaplicaciones computables. Adem´s, la teor´ de la computabilidad, junto
a
ıa
con la teor´ de aut´matas, lenguajes y m´quinas, es el fundamento de la
ıa
o
a
inform´tica te´rica y esta, a su vez, de la industriade los ordenadores.
a
o
Desde tiempo inmemorial se sabe que cierta clase de problemas, e.g., la
determinaci´n del m´ximo com´n divisor de dos n´meros enteros, mediante
o
a
u
u
el algoritmo deEuclides, o la determinaci´n de los n´meros primos, mediante
o
u
la criba de Erat´stenes, son algor´
o
ıtmicamente solubles, i.e., hay algoritmos
o procedimientos mec´nicos que permiten obtener la soluci´ndel problema
a
o
en cuesti´n. De manera que hasta principios del siglo XX se daba por hecho
o
que exist´ algoritmos y que el unico problema resid´ en determinarlos.
ıan
´
ıa
As´ pues, si lo que sedesea es determinar un algoritmo, no hay ninguna
ı
necesidad de definir la clase de todos los algoritmos; eso s´lo es necesario si
o
se pretende demostrar que alg´n problema no es algor´
u
ıtmicamentesoluble,
i.e., que para dicho problema no hay ning´n algoritmo que lo resuelva.
u
Es posible que el primero en afirmar la no existencia de un algoritmo fuera
Tietze en 1908, qui´n dijo de los gruposde presentaci´n finita:
e
o
“. . . la cuesti´n acerca de cu´ndo dos grupos son isomorfos no es soluble
o
a
en general.”
Pero parece ser que fue, por una parte, el problema de la decidibilidad
de lal´gica de predicados planteado por Hilbert y Ackermann en su libro
o
sobre l´gica, publicado en 1928, y, por otra, el asunto de la solubilidad de
o
todo problema matem´tico, lo que indujo, en aras a...