Funciones Recursivas Parciales - Universidad Nacional del Surcs.uns.edu.ar/materias/tc2do/downloads/Apuntes/Funciones... · 2019-09-27 · 2. Funciones Recursivas Primitivas Las funciones

Teorıa de la Computabilidad

Notas de curso referidas a

Funciones Recursivas Parciales

Dr. Carlos Ivan Chesnevar

Dr. Marıa Laura Cobo

Catedra de Teorıa de la Computabilidad

Departamento de Ciencias e Ingenierıa de la ComputacionUniversidad Nacional del Sur

Bahıa Blanca, 2019(1ra. Edicion)

Teorıa de la Computabilidad – Notas de Curso – por C.I. Chesnevar, M.L. Cobo y D.R. Garcia

Introduccion

El presente texto intenta brindar una version integrada de algunos temas teori-cos y practicos que forman parte del programa de la materia Teorıa de la Compu-tabilidad, correspondiente al Departamento de Cs. e Ing. de la Computacion de laUniversidad Nacional del Sur. En particular, el material aquı presentado desarrollalos conceptos correspondientes al tema de Funciones Recursivas Parciales.

Si bien existe gran numero de textos para abordar los conceptos correspondientesa este tema, resulta difıcil encontrar un unico libro de texto que considere el enfo-que utilizado en esta materia. Esta situacion dio origen a un conjunto de apunteselaborados por la profesora Sandra Gabelli, posteriormente consolidados y refina-dos en notas de curso realizadas por el profesor Juan C. Augusto en 1995, quien sedesempeno como profesor hasta 2001. A partir de 2002 se introdujeron nuevos recur-sos didacticos y materiales adicionales, que obligaron a revisar, replantear, corregiry actualizar varios aspectos de los presentados en las notas de curso del profesorJuan C. Augusto. Esa motivacion fue la que guio la confeccion de este nuevo texto,que complementa y corrige apuntes y notas usadas hasta el momento en la mate-ria. El material presentado esta en constante evolucion y correccion, por lo que seagradecera especialmente toda sugerencia, crıtica o comentario sobre el mismo.

Carlos Ivan ChesnevarUniversidad Nacional del Sur – Bahıa Blanca, Argentina

Nota: puede contactarse a los responsables del presente texto por vıa electronica alas direcciones abajo indicadas.Dr. Carlos Ivan Chesnevar: Email: [email protected] – Web: http://cs.uns.edu.ar/∼cicDr. Marıa Laura Cobo: Email: [email protected]

–ii–


Funciones Recursivas Parciales

1. Introduccion y motivaciones

El concepto matematico de funcion brinda una abstraccion sumamente util pa-ra modelar gran numero de problemas de la vida real. En el capıtulo referido aMaquinas de Turing hemos visto como definir funciones Turing-computables, estoes, maquinas de Turing capaces de implementar un procedimiento efectivo que seaequivalente al comportamiento de una determinada funcion matematica. Considere-mos por caso la funcion f(x, y) = x+ y, con x, y ∈ Nat. Sabemos que en particularesta funcion es Turing-computable, pues fue posible construir una maquina de Tu-ring capaz de computar dicha funcion. Pero cabe entonces la pregunta: . . . ¿todafuncion matematica es Turing-computable? Apartentemente la respuesta debe serafirmativa, dado que cada vez que se calcula el valor de una funcion se aplica alguntipo de proceso de manipulacion de sımbolos (esto es, un procedimiento efectivo)que permite llegar a un resultado. Cabe igualmente la pregunta ¿todo procedimien-to efectivo tiene una funcion matematica equivalente? ¿cual es el lımite de lo queresulta computable a traves de funciones?

En este capıtulo abordaremos estas cuestiones a traves de las denominadas fun-ciones recursivas parciales. Las funciones recursivas parciales brindan una versionalternativa para conceptualizar la nocion de procedimiento efectivo, utilizando co-mo abstraccion basica la nocion matematica de funcion. Este enfoque se origino apartir de las investigaciones del matematico Stephen Cole Kleene y del logico-matematico Kurt Godel, y es contemporaneo a las investigaciones de Alan Turing.

Este capıtulo se estructurara como sigue: primeramente, en la seccion 2 estu-diaremos la clase de las funciones recursivas primitivas, que constituyen una sub-clase particularmente interesante de las funciones recursivas parciales. Se vera quea traves de estas funciones pueden capturarse gran numero de problemas para loscuales existen procedimientos efectivos. En la seccion 3 se analizara el concepto depredicado como una herramienta auxiliar para la definicion de funciones, permitien-do la caracterizacion de los denominados predicados recursivos primitivos. Luego, enla seccion 4 se presentara la funcion de Ackermann, la cual pone en evidencia quelas funciones recursivas primitivas no bastan para capturar completamente la nocionde procedimiento efectivo. La seccion 5 estara dedicada a solucionar esta limitacion,extendiendo el poder de las funciones recursivas primitivas a traves del denominadooperador de minimizacion. Esto completara nuestro objetivo inicial de capturar lanocion de procedimiento efectivo a traves de funciones, estableciendo la clase de lasdenominadas funciones recursivas parciales. La seccion 6 analizara un caso particu-lar de aplicacion de las funciones recursivas primitivas para el dominio de n-uplas decadenas de sımbolos. En la seccion 7 se presentaran algunas aplicaciones practicas dela teorıa de funciones recursivas parciales. Finalmente, en la seccion 8 se presentanalgunos datos historicos y biograficos sobre la evolucion de las funciones recursivasparciales.

–1–


2. Funciones Recursivas Primitivas

Las funciones recursivas primitivas son funciones totales1 de la forma f : Natn→Nat,n ≥ 0. Una funcion recursiva primitiva (abreviadamente denotada frpri) esta defi-nida entonces con dominio en n-uplas de numeros naturales (incluyendo al cero) ycon imagen en numeros naturales (incluyendo al cero). Las funciones recursivas pri-mitivas se construyen a partir de ciertos ‘esquemas’ o constructores basicos. Tres deestos constructores corresponden a las denominadas funciones iniciales (o funcionesbase), conocidas como funcion cero, funcion sucesor y funcion identidad generaliza-da, y denotadas como cero, succ y Πn

i respectivamente. Los dos esquemas restantescorresponden a los constructores, y recibien el nombre de composicion y recursionprimitiva.

Existe un amplio numero de funciones matematicas que puede caracterizarse enterminos de funciones recursivas primitivas. Como se vera posteriormente, puedeprobarse que toda funcion recursiva primitiva es total y siempre es Turing-compu-table. Veremos mas adelante que la recıproca de esta afirmacion no es cierta (notoda funcion Turing-computable es una funcion recursiva primitiva), y mostraremostambien como aumentar el poder expresivo de la recursion primitiva para obteneruna clase mas potente de funciones denominada funciones recursivas parciales (veaseseccion 5).

Definicion 2.1 [Funcion Recursiva Primitiva] Una funcion f se dira funcion recur-siva primitiva sobre Nat si satisface alguno de los siguientes casos:1) La funcion f es alguna de las tres funciones base o iniciales siguientes:

Funcion cero : Es una funcion de la forma cero : Natn→{0}, tal que

cero(x1, . . . , xn) = 0, ∀(x1, x2, . . . , xn) ∈ Natn, n ∈ Nat

Funcion sucesor : Es una funcion de la forma succ : Nat→Nat, tal que

succ(x) = x+ 1, ∀x ∈ Nat

Funcion de identidad generalizada : Es una funcion de la forma Πni : Natn→Nat,

con n > 0, tal que

Πni (x1, x2, . . . , xn) = xi

En otras palabras, Πni (x1, x2, . . . , xn) devuelve el i-esimo elemento de la n-upla

(x1, x2, . . . , xn), con 1 ≤ i ≤ n.

2) La funcion f se obtiene a partir de otras funciones recursivas primitivas por laaplicacion de las siguientes funciones constructoras (o simplemente constructores):

1Recordemos que una funcion matematica se dice total si esta definida para todos los elementosde su dominio. Ejemplo: f : Nat2→Nat, f(x, y) = x− y no es una funcion total, pues existen variospares (x, y) para los cuales f no esta definida, tales como f(4, 5), f(1, 6), etc.

–2–


Composicion : Sean h : Natm→Nat una funcion total, m ≥ 0, y sean g1, g2,. . . gm funciones, tal que gi : Natn→Nat, con n ≥ 0, para i = 1 . . .m. La funcionf : Natn→Nat puede ser definida por composicion a partir de las funciones hy g1, g2, . . . ,gm como sigue:

f(x1, . . . , xn) = h(g1(x1, . . . , xn), . . . gm(x1, . . . , xn))

Formalmente:

f(x1, . . . , xn) = [h ◦ (g1, . . . gm)](x1, . . . , xn)

Recursion primitiva : Sea g una funcion recursiva primitiva total n-aria, y seah una funcion recursiva primitiva total n + 2-aria. Luego puede definirse unafuncion f , n+ 1-aria, tal que para toda n-upla (x1, . . . , xn) ∈ Natn y m ∈ Natse tiene:

f(x1, . . . , xn, 0) = g(x1, . . . , xn)f(x1, . . . , xn,m+ 1) = h(x1, . . . , xn,m, f(x1, . . . , xn,m))

En este caso se dice que f se obtiene a partir de g y h por recursion primitiva.

Ninguna otra funcion (excepto las que pueden obtenerse a partir de los casos 1 y 2)es una funcion recursiva primitiva. 2

Se menciono inicialmente que las funciones recursivas primitivas se construyen apartir de funciones inciales y el uso de constructores. Mostraremos a continuacion dosejemplos de funciones que ilustran como determinar cuando una funcion es recursivaprimitiva.

Ejemplo 2.1 Considerese la funcion f : Nat2→Nat, tal que f(x, y) = y ∀x, y ∈ Nat.Notese que esta funcion es recursiva primitiva, en virtud de que constituye un casoparticular de la funcion de identidad generalizada (def. 2.1), ya que se define como:

f(x, y) = Π22(x, y)

Luego f ≡ Π22, y consecuentemente f es frpri. 2

Ejemplo 2.2 Considerese la funcion constante tres : Nat→Nat, tal que tres(x) = 3,∀x ∈ Nat. Notese que puede obtenerse una funcion recursiva primitiva con estecomportamiento, concretamente:2

tres(x) = succ(succ(succ(cero(x))))

Formalmente:

2Notese que matematicamente podrıa adoptarse la definicion tres : Nat→{3}. Pero esta no serıa(en sentido estricto) una funcion recursiva primitiva, dado que la imagen es un subconjunto de losnumeros naturales.

–3–


Figura 1: Expresando una funcion a partir de funciones recursivas primitivas:analogıa con un rompecabezas

tres(x) = succ ◦ succ ◦ succ ◦ cero(x)

Esta funcion recursiva primitiva ha sido obtenida a partir de las funciones ini-ciales cero y succ, aplicando sucesivamente el constructor de composicion. 2

Los ejemplos 2.1 y 2.2 ilustran un problema comun a resolver: dada una funcionmatematica f , mostrar que f es una funcion recursiva primitiva. ¿Como lograr esteobjetivo? Para esto deberemos ‘jugar’ con las distintas funciones basicas y cons-tructores provistos por la definicion 2.1, y utilizarlos de manera analoga a piezas deun rompecabezas que deben combinarse apropiadamente para llegar a armar unafigura determinada (en nuestro caso, la funcion f buscada). La figura 1 ilustra estasituacion.

Es claro que recurrir unicamente a la intuicion para determinar si una funcion fes o no una funcion recursiva primitiva es un tanto engorroso, dado que hay variasmaneras de combinar las funciones base y los constructores entre sı a partir de loenunciado en la definicion 2.1. Con el objeto de clarificar como se combinan las fun-ciones basicas y constructores al definir una nueva funcion matematica se introducirala nocion de derivacion formal de una funcion recursiva primitiva. La derivacion for-mal es simplemente una lista de la secuencia de pasos que refleja cuales funcionesbasicas y constructores se requieren para la construccion de la definicion de unafuncion matematica dada, y en que orden se debe hacer su aplicacion. Formalmente:

Definicion 2.2 [Derivacion formal (recursiva primitiva) de una funcion f ] Sea f unafuncion recursiva primitiva. Denominaremos derivacion formal (recursiva primitiva)de f a una secuencia de pasos S=[s1, s2, . . . , sk], tal que cada paso si es

Una funcion base o inicial, o bien

Una funcion recursiva primitiva que puede obtenerse a partir una o mas funcio-nes definidas en algun paso previo sj ∈ S, j < i por medio de los constructoresde composicion y recursion primitiva

–4–


2

Puede demostrarse que toda funcion recursiva primitiva tiene una derivacion for-mal asociada. Esto queda establecido formalmente como consecuencia del siguientelema:

Lema 2.1 Una funcion f es una funcion recursiva primitiva si existe alguna deriva-cion formal recursiva primitiva para f . 2

Demostracion: Realizar esta prueba como ejercicio.

Analizaremos seguidamente algunos ejemplos de funciones recursivas primitivas ca-racterizadas a traves de sus respectivas derivaciones formales.

Ejemplo 2.3 Considerese la funcion constante tres : Nat→Nat y su definicion entermino de funciones recursivas primitivas (ejemplo 2.2).

La funcion tres ha sido obtenida a partir de las funciones iniciales cero y succ,aplicando sucesivamente el constructor de composicion. Una derivacion formal re-cursiva primitiva para tres serıa la siguiente:

1. cero(x) es frpri por ser funcion inicial.

2. succ(x) es frpri por ser funcion inicial.

3. succ ◦ cero(x) es frpri por composicion, a partir de los pasos 1 y 2.

4. succ ◦ succ ◦ cero(x) es frpri por composicion, a partir de los pasos 2 y 3.

5. succ ◦ succ ◦ succ ◦ cero(x) ≡ tres(x) es frpri por composicion, a partir de lospasos 4 y 2.

La secuencia S correspondiente (de acuerdo a la def. 2.2) serıa entonces la siguiente:

S = [ cero(x), succ(x), succ ◦ cero(x), succ ◦ succ ◦ cero(x),succ ◦ succ ◦ succ ◦ cero(x) ]

2

Seguidamente se presentaran algunos ejemplos de funciones matematicas queson funciones recursivas primitivas. En algunos casos se ilustrara la secuencia depasos asociada a la derivacion formal de la funcion definida, quedando el resto delas derivaciones formales como ejercicio para el lector.

Ejemplo 2.4 Considerese la funcion f : Nat→Nat, f(x) = x + 2. Puede probarseque f es una funcion recursiva primitiva. En efecto, si se toma h ≡ g1 = succ,resulta f(x) = h(g1(x)) = succ◦ succ(x). En este caso se ha obtenido f a partir de lafuncion base succ y el constructor composicion. Debajo se indica la correspondientederivacion formal recursiva primitiva para f :

1. succ(x) es frpri por ser funcion inicial.

–5–


2. succ ◦ succ(x) ≡ f(x) es frpri por composicion a partir del paso 1.

2

Ejemplo 2.5 Considerese la funcion f : Nat3→Nat, f(x, y, z) = x + 1. Puede pro-barse que f es una funcion recursiva primitiva dado que puede escribirse en terminosde las funciones sucesor, identidad generalizada y el constructor composicion:

f(x1, x2, x3) = h(g1(x1, x2, x3)) = succ ◦ Π31(x1, x2, x3)

Debajo se indica la correspondiente derivacion formal recursiva primitiva para f :

1. Π31(x1, x2, x3) es frpri por ser funcion inicial.

2. succ◦Π31(x1, x2, x3) ≡ f(x1, x2, x3) es frpri por composicion a partir del paso 1.

2

Ejemplo 2.6 Considerese la funcion suma : Nat2→Nat, tal que suma(x1, x2) =x1+x2. Puede probarse que suma es una funcion recursiva primitiva, en virtud de quepuede definirse utilizando identidad generalizada, recursion, sucesor y composicion:

suma(x1, 0) = Π11(x1)

suma(x1, x2 + 1) = succ(Π33(x1, x2, suma(x1, x2)))

= succ ◦ Π33(x1, x2, suma(x1, x2))

Debajo se muestra un ejemplo de como calcular el valor de suma(2, 2) a partir dela definicion anterior:

suma(2, 2) = suma(2, 1 + 1) = succ ◦ Π33(2, 1, suma(2, 1)) =

succ ◦ Π33(2, 1, suma(2, 0 + 1)) =

succ ◦ Π33(2, 1, succ ◦ Π3

3(2, 0, suma(2, 0))) =succ ◦ Π3

3(2, 1, succ ◦ Π33(2, 0,Π1

1(2))) =succ ◦ Π3

3(2, 1, succ ◦ Π33(2, 0, 2)) =

succ ◦ Π33(2, 1, succ(2)) = succ ◦ Π3

3(2, 1, 3) =succ ◦ Π3

3(2, 1, 3) =succ(3) = 4

2

Ejemplo 2.7 [Funcion signo] Considerese la funcion signo : Nat→Nat, definidacomo sigue:

signo(x) =

{1 si x > 00 si caso contrario

Esta funcion es recursiva primitiva pues puede definirse de la siguiente manerautilizando el constructor de recursion primitiva:

signo(0) = cero()signo(x+ 1) = succ ◦ cero(x, signo(x))

2

–6–


Ejemplo 2.8 [Funcion sumat] Considerese la funcion sumat : Nat→Nat para cal-cular la sumatoria de los numeros de 1 a n. La misma puede definirse informalmentecomo sigue:

sumat(x) = 0 + 1 + . . .+ x

Esta funcion puede definirse recursivamente de manera informal como sigue:

sumat(0) = 0sumat(x+ 1) = (x+ 1) + sumat(x)

En particular, notemos que la expresion (x + 1) + sumat(x) es equivalente ax+sumat(x)+1, y que puede escribirse informalmente como succ(x+sumat(x)). Asu-mamos contar con una funcion recursiva primitiva suma(x, y) que sume dos numerosnaturales. Luego lo anterior puede escribirse como succ(suma(x, sumat(x))). For-malmente, esto puede expresarse unicamente en terminos de funciones recursivasprimitivas como sigue:

suma ◦ (succ ◦ Π21,Π

22)(x, sumat(x))

Esto lleva a reescribir la definicion 2.8 formalmente como:

sumat(0) = cero()sumat(x+ 1) = suma ◦ (succ ◦ Π2

1,Π22)(x, sumat(x))

Para garantizar que sumat(x) es en efecto una funcion recursiva primitiva faltaaun probar que suma(x1, x2) lo es. Sea suma : Nat×Nat→Nat, definida como sigue:

suma(x1, x2) = x1 + x2

Como se mostro en el ejemplo 2.6, hemos podido probar que esta funcion esrecursiva primitiva debido a que puede definirse uilizando el constructor de recursionprimitiva como sigue:

suma(x1, 0) = Π11(x1)

suma(x1, x2 + 1) = succ ◦ Π33(x1, x2, suma(x1, x2))

2

Ejemplo 2.9 [Funcion predecesor ]3 Si bien la funcion succ es una de las funcionesbases provistas por la definicion de funcion recursiva primitiva, cabe observar queno sucede lo mismo con la nocion de predecesor. Veamos que es posible definir unafuncion pred : Nat → Nat para capturar este concepto como una funcion recursivaprimitiva. Notese que efectivamente pred puede definirse como:

pred(x) =

{0 si x = 0

x− 1 si x ≥ 1

Luego puede expresarse lo anterior como:

pred(0) = cero(x)pred(x+ 1) = Π2

1(x, pred(x))

2

3Algunos de los ejemplos siguientes fueron adaptados a partir de [Aug95] y [LP98].

–7–


Ejemplo 2.10 [Funcion difp (diferencia primitiva)] Recordemos que las funcionesrecursivas primitivas tienen siempre como imagen al conjunto Nat ∪ {0}. En conse-cuencia, no es conveniente definir la nocion de resta tradicional entre naturales de lamanera usual, dado que no puede asegurarse que el resultado de x−y, con x, y ∈ Natsea natural (por ejemplo, 5−8). Se optara entonces por la nocion de resta o diferen-cia primitiva, la cual se define como una funcion de la forma difp : Nat2 → Nat. Laidea intuitiva es que difp(x, y) = x − y cuando el resultado de la diferencia sea unvalor natural (incluıdo el 0), y que difp(x, y) = 0 en caso contario. Formalmente:

difp(x, y) =

{0 si x < y

x− y si x ≥ y

Veamos como formular la definicion anterior en terminos recursivos. Para facilitarel acercamiento al problema, conviene atacar el problema de definir x− (y+1) (puesnotemos que la definicion recursiva debe contemplar y + 1 como argumento a laizquierda de la igualdad). Pero resulta:

x− (y + 1) = x− y − 1 = (x− y)− 1

Usando notacion de funciones recursivas primitivas lo anterior puede expresarsecomo se muestra abajo:

difp(x, 0) = Π11(x)

difp(x, y + 1) = (pred ◦ Π33)(x, y, difp(x, y))

Nota: en lo sucesivo se utilizara el operador infijo.− para notar informalmente la

diferencia primitiva. Ası, en lugar de difp(x, y) se escribira x.−y. 2

Ejemplo 2.11 [Funcion difabs ] La diferencia en valor absoluto entre x e y (esto es|x−y|) es tambien una funcion recursiva primitiva. Definimos para esto una funciondifabs(x, y) : Nat2 → Nat de la forma siguiente:

difabs(x, y) =def

{(x

.−y) si x ≥ y

(y.−x) si x < y

La funcion difabs puede expresarse como una funcion recursiva primitiva comosigue:

difabs(x, y) = suma(difp(x, y), difp(y, x))

Formalmente, resulta:

difabs(x, y) = suma ◦ (difp ◦ (Π21,Π

22), difp ◦ (Π2

2,Π21))(x, y)

La funcion difabs es entonces una funcion recursiva primitiva, pues resulta decombinar dos funciones recursivas primitivas suma y difp usando el constructor decomposicion. 2

–8–


Ejemplo 2.12 [Funcion identidad] Consideremos id : Nat→ Nat, la funcion identi-dad definida como id(x) = x, ∀x ∈ Nat. La funcion id puede definirse como funcionrecursiva primitiva como sigue:

id(0) = cero()id(y + 1) = (succ ◦ Π2

1)(y, f(y))

2

Definicion 2.3 [Funcion Knj ] Se denominara funcion constante n-aria (denotada

Knj , con n ≥ 0 y j ≥ 0) a la funcion Kn

j : Natn → Nat, tal que Knj (n) = j para

cualquier n-upla n ∈ Natn. 2

Ejemplo 2.13 Considerese la definicion 2.3. Luego K237(x1, x2) = 37 para todo

x1, x2 ∈ Nat2. Tambien K53(x1, x2, x3, x4, x5) = 3, para toda 5-upla x ∈ Nat5. 2

Puede probarse el siguiente lema, que establece que todas las funciones constantesson recursivas primitivas.

Lema 2.2 Toda funcion constante Knj es recursiva primitiva. 2

Demostracion: Se deja como ejercicio para el lector.

3. Predicados Recursivos Primitivos

Desde un punto de vista conceptual, la teorıa de las funciones recursivas pri-mitivas se enriquece considerablemente al poder modelar relaciones matematicas.Un elemento importante en este contexto es la definicion de predicado n-ario paracapturar relaciones entre numeros naturales:

Definicion 3.1 [Predicado n-ario] Un predicado n-ario (denotado P (n)) es unarelacion n−aria sobre numeros naturales, esto es P (n) ⊆ Natn. Sea P (n) un pre-dicado n-ario, y sea (x1, x2, . . . , xn) una n-upla. Diremos que P (x1, x2, . . . , xn) esverdadero cuando (x1, x2, . . . , xn) ∈ P (n), y diremos que P (x1, x2, . . . , xn) es falsoen caso contrario. 2

Ejemplo 3.1 Considerese los predicados menor ⊆ Nat2 e igual ⊆ Nat2, dondemenor(x, y)={(x, y) ⊆ Nat2 | x < y} e igual(x, y)={(x, y) ⊆ Nat2 | x = y}. Luegomenor(2, 3) es verdadero, menor(1, 1) es falso, e igual(1, 1) es verdadero. 2

Como hemos visto, los predicados expresan un resultado utilizando los terminoslogicos verdadero y falso. Notemos que estos terminos pueden asociarse a dos nume-ros naturales distinguidos (por ejemplo, 1 ≡ verdadero y 0 ≡ falso). Muy facilmentepuede pensarse entonces cualquier predicado P (n) a partir de una funcion asociadaa P , denominada fP , que devuelva 1 precisamente cuando P es verdadero y 0 cuandoP es falso. Dicha funcion sera llamada funcion caracterıstica del predicado P . Lanecesidad de la funcion caraterıstica como forma de representar un predicado radicaen que la imagen de la funcion es un conjunto de numeron naturales y por lo tantopueden tratarse y definirse como una frpri. Formalmente estas funciones se definende la siguiente manera:

–9–


Definicion 3.2 [Funcion caracterıstica de un predicado P ] La funcion caracterısticade un predicado P (n) es una funcion n-aria fP : Nat→{0, 1} definida como sigue:

fP (x) =def

{1 si P (x) es verdadero0 si P (x) es falso

2

Podemos ahora estudiar a los predicados en el contexto de las funciones recur-sivas parciales. En efecto, podemos distinguir aquellos predicados cuyas funcionescaracterısticas asociadas son precisamente funciones recursivas primitivas. Todo pre-dicado que satisfaga esta condicion se denominara predicado recursivo primitivo.Formalmente:

Definicion 3.3 [Predicado Recursivo Primitivo] Un predicado P se dice recursivoprimitivo si y solo si su funcion caracterıstica fP es recursiva primitiva.4 2

Ejemplo 3.2 [Adaptado de [Aug95]] Puede demostrarse que igual(x, y) es un pre-dicado recursivo primitivo. Para esto debe mostrarse que su funcion caracterısticalo es, lo que puede hacerse informalmente a traves de la siguiente formulacion. Seala funcion figual : Nat→Nat definida como figual(x, y) = 1

.−sg(difabs(x, y)) o mas

formalmente

figual(x, y) = difp ◦ (K21, sg ◦ (difabs ◦ (Π2

1,Π22)))(x, y)

Como la funcion figual devuelve 1 cuando y = x y 0 en caso contrario, puede afirmarseque figual se comporta como funcion caracterıstica del predicado igual. Como figuales una funcion recursiva primitiva, entonces (por def. 3.3) se concluye que igual esun predicado recursivo primitivo. 2

Ejercicio 3.1 Mostrar que los predicados menor y mayor son recursivos primi-tivos. 2

Dado que un predicado P (n) tiene asociado un valor de verdad para una instanciaparticular P (c1, c2, . . . , cn) (esto es, P (c1, c2, . . . , cn) es o bien verdadero o bien falso),pueden definirse nuevos predicados a partir de las operaciones logicas de conjuncion,disyuncion y negacion. Si P y Q son dos predicados, definimos nuevos predicados¬P , P ∧Q y P ∨Q de la manera siguiente:

El predicado ¬P (X), formado por todas aquellas n-uplas (x1, . . . , xn) que nosatisfacen P (X).

El predicado P (X) ∧ Q(X), formado por todas aquellas n-uplas (x1, . . . , xn)que satisfacen P (X) y Q(X).

4Notese que el nombre del predicado es el subındice correspondiente al nombre de la funcion.Esta notacion refleja entonces que cada predicado P tiene asociada una funcion caracterısticaparticular fP .

–10–


El predicado P (X) ∨ Q(X) formado por todas aquellas n-uplas (x1, . . . , xn)que satisfacen o bien P (X) o bien Q(X).

Si P y Q son predicados recursivos primitivos, la definicion de un nuevo predicadoa traves de los operadores logicos de conjuncion, disyuncion y negacion resulta enun predicado recursivo primitivo. Formalmente:

Lema 3.1 [Composicion de Predicados Recursivos Primitivos] Si P y Q son predi-cados recursivos primitivos, entonces los predicados ¬P , P ∨Q y P ∧Q tambien loson. 2

Demostracion: Queda como ejercicio para el lector. Sugerencia: utilizar las opera-ciones aritmeticas de resta, suma y multiplicacion. Es importante tener en cuentaque el resultado de la funcion asociada al predicado debe seguir siendo solo 0 o 1.

Corolario 3.1 Sean P y Q son predicados recursivos primitivos, y sean fP y fQsus respectivas funciones caracterısticas recursivas primitivas. Entonces las funcionescaracterısticas f¬P , fP∨Q y fP∧Q asociadas a los predicados ¬P , P ∨ Q y P ∧ Qtambien son recursivas primitivas. 2

Demostracion: Es directa a partir de las definiciones 3.2 y 3.3, y el lema 3.1.El siguiente ejemplo ilustra una aplicacion del lema 3.1.

Ejemplo 3.3 [Funcion signo′] Considerese la funcion signo (ejemplo 2.7). Entoncesla funcion signo′, definida como

signo′(x) =

{1 si x = 00 si caso contrario

es recursiva primitiva. Notese que signo(x) devuelve siempre 1 o 0, por lo cual puedepensarse a esta funcion como un predicado. Pero entonces signo′(x) =def ¬signo(x).Luego, por lema 3.1, puede asegurarse que signo′ es una funcion recursiva primitiva.2

Si P1,P2, . . . , Pm son predicados recursivos primitivos, diremos que son disjuntosentre sı cuando para toda n-upla (x1, x2, . . . , xn) se verifica que no pertenece a masde una relacion determinada por los predicados P1, P2, . . . , Pm.

Ejemplo 3.4 Sea Par(x) el predicado que determina si x es un numero par o no.Este predicado puede ser calculado mediante la siguiente funcion caracteristica:

Informalmente Formalmente

par(0) = 1 par(0) = succ ◦ cero()

par(x+ 1) = 1.−par(x) par(x+ 1) = difp ◦ (succ ◦ cero,Π2

2)(x, par(x))

–11–


Claramente este predicado es disjunto del predicado Impar(x) ya que un numeronatural no puede ser simultaneamente par e impar. De hecho, impar puede definirsede la siguiente manera:

impar(x) = difp ◦ (succ ◦ cero, par ◦ Π11)(x) [1

.−par(x)]

Considerese por otro lado el predicado Mult3(x), que resulta verdadero si y solo six es multiplo de 3. En tal caso, Par(x) no es disjunto del predicado Mult3(x), puesexisten numeros pares que son divisibles por 3. Se analizara en detalle como definirel predicado Mult3(x) en el ejemplo 3.8. 2

Definicion 3.4 [Funcion recursiva primitiva definida por casos] Sean P1,P2, . . . , Pm

predicados recursivos primitivos disjuntos y sean g1, g2, . . . , gm funciones recursivasprimitivas. Se denominara funcion recursiva primitiva definida por casos a todafuncion f con la siguiente estructura:

f(x1, x2, . . . , xn) =

g1(x1, x2, . . . , xn) si P1(x1, x2, . . . , xn) es verdaderog2(x1, x2, . . . , xn) si P2(x1, x2, . . . , xn) es verdadero. . .gm(x1, x2, . . . , xn) si Pm(x1, x2, . . . , xn) es verdadero

2

Lema 3.2 Sea g(x1, . . . , xn) una funcion recursiva primitiva definida por casos. En-tonces f es una funcion recursiva primitiva. 2

Demostracion: Queda como ejercicio para el lector. Sugerencia: definir f utilizandolas funciones caracterısticas de los predicados considerados de tal forma que anulenlos valores asociados a cada funcion gi cuando el predicado es falso para la n-upladada. Tener en cuenta tambien que los predicados son mutuamente excluyentes.

El siguiente ejemplo ilustra como aplicar el lema 3.2 en la determinacion de queuna determinada funcion es recursiva primitiva.

Ejemplo 3.5 [La funcion max] Supongase que queremos definir en terminos derecursion primitiva a la funcion max : Nat2→Nat, donde max(x, y) es el mayor valorentre x e y. Intuitivamente se tiene una funcion por casos:

max(x, y) =

{x si x > yy si x ≤ y

Notemos que lo anterior puede expresarse equivalentemente como sigue:

max(x, y) =

{Π2

1(x, y) si mayor(x, y)Π2

2(x, y) si ¬mayor(x, y)

Donde mayor(x, y) corresponde a un predicado que tiene asociado el valor ver-dadero cuando x > y y falso en caso contrario. Hemos probado que mayor(x, y) esrecursivo primitivo. Por lema 3.1, su complemento ¬mayor(x, y) tambien lo es. Esclaro que Π2

1(x, y) y Π22(x, y) son funciones recursivas primitivas. Luego la definicion

anterior de max(x, y) es una funcion por casos (definicion 3.4), y como tal –porlema 3.2– es una funcion recursiva primitiva. 2

–12–


Dada una cierta funcion f , es claro que no existe una unica forma de definir f atraves de funciones recursivas primitivas (en otras palabras, pueden existir distintasderivaciones formales para una misma funcion f).

Ejemplo 3.6 [Definicion alternativa de max] Considerese la funcion signo defini-da anteriormente (ejemplo 2.7). Puede obtenerse una funcion caracterıstica para elpredicado mayor(x, y) de la manera siguiente:

fmayor(x, y) = signo(x.−y)

Segun el ejemplo 3.3, se tiene tambien que

fmenor o igual(x, y) = signo′(x.−y)

Naturalmente ambas funciones son mutuamente excluyentes. Esto posibilita de-finir la funcion max como sigue:

max(x, y) = fmayor(x, y) ∗ x+ fmenor o igual(x, y) ∗ y

Mas formalmente:

max(x, y) =suma(producto(Π2

1(x, y), signo(difp(x, y))), producto(Π22(x, y), signo′(difp(x, y))))

De donde se sigue que:max(x, y) = suma ◦

(producto ◦ (Π21, signo ◦ difp ◦ (Π2

1,Π22)),

producto ◦ (Π22, signo

′ ◦ difp ◦ (Π21,Π

22)))(x, y) 2

Definicion 3.5 [Cuantificacion existencial/universal acotada] Sea n ∈ Nat,n > 0, y sea P un predicado (n+1)-ario. La cuantificacion existencial acotada de P esun nuevo predicado Q, tambien (n+ 1)-ario, tal que para cada (x1, x2...xn) ∈ Natn,y m ∈ Nat, Q(x1, x2...xn,m) es verdadero si y solo si ∃i, 0 ≤ i ≤ m, tal queP (x1, x2...xn, i) es verdadero. Abreviadamente esto puede expresarse como:

Q(x1, x2...xn,m) si y solo si (∃i)≤m[P (x1, x2...xn, i)].

Analogamente, la cuantificacion universal acotada es un predicado R tal que

R(x1, x2...xn,m) si y solo si (∀i)≤m[P (x1, x2...xn, i)]

2

Ejemplo 3.7 Notese la definicion de la cuantificacion existencial acotada:

Q((x1, ..., xn),m) sssi (∃i)≤m[P ((x1, x2...xn), i)]

Considerese por caso el predicado existemenor(x1, x2). Este podrıa definirse como

existemenor(x1, x2) sssi (∃i)≤x2 [menor(x1, i)]

–13–


En este caso, existemenor(3, 2) sssi (∃i)≤2[menor(3, i)]. Luego existemenor(3, 2) esfalso. 2

La necesidad de la cuantificacion acotada (tanto existencial como universal) radi-ca en que para ciertos predicados no pueden definirse como funciones caracterısticas,como lo muestra el siguiente ejemplo.

Ejemplo 3.8 Tomemos como ejemplo el predicado Mult3(x) que mencionamos an-teriormente. Para determinar efectivamente si un numero x es o no multiplo de 3,matematicamente se tienen dos alternativas:

1. Dividir x por 3 y fijarnos que la division haya sido entera o el resto sea iguala 0

2. Verificar si existe algun valor entre 0 y x tal que multiplicado por 3 sea iguala x.

La primera posibilidad es inaplicable en el contexto de las funciones frpri, yaque la division tiene su imagen en los reales a pesar de tener como dominio losnaturales.5 Por esto nos resta solamente la segunda opcion que claramente estahaciendo uso de la cuantificacion acotada. Veamos entonces como definimos nuestrafuncion caracterıstica para Mult3(x). Puede hacerse esto como sigue:

Mult3(x) si solo si (∃y)≤x[3 ∗ y = x]

2

Lema 3.3 [Lema de la Cuantificacion acotada] Sea P un predicado recursivo pri-mitivo, y sean Pe y Pu predicados correspondientes a la cuantificacion existencialacotada y cuantificacion universal acotada de P , respectivamente. Entonces Pe y Pu

son predicados recursivos primitivos. 2

Demostracion: Se deja como ejercicio para el lector.El siguiente teorema brinda un resultado importante, pues nos permite asegurar

que toda funcion recursiva primitiva esta bien definida para todos los elementos desu dominio (esto es, Natn, para algun n > 0). En matematicas, toda funcion quecumple esta propiedad se la denomina funcion total.6

Teorema 3.1 Toda funcion recursiva primitiva es una funcion total. 2

Demostracion: Por el lema 2.1, sabemos que una funcion f es recursiva primitiva siy solo si tiene asociada una derivacion formal recursiva primitivadf = [s1, s2, s3, . . . , sk], con sk ≡ f . Realizaremos entonces la prueba por induccionsobre la longitud de la derivacion formal recursiva primitiva.

5Mas adelante se proveeran maneras de lidiar con este tipo de funciones.6Al pie de la pagina 2 se analizo el significado del concepto matematico de funcion total.

–14–


Caso base: Supongamos que | df | = 1. Luego f es necesariamente alguna funcionrecursiva primitiva inicial o base (esto es, la funcion cero, sucesor o identidad gene-ralizada). Pero como se enuncio en la definicion 2.1, cada una de estas funciones estotal. Luego f es total.Hipotesis inductiva: Supongamos que para toda funcion recursiva primitiva g,| dg | < k, k > 1, se verifica que g es una funcion total.Paso Inductivo: Queremos probar que f (funcion recursiva primitiva) es una fun-cion total, con | df | = k. Por definicion 2.1, f fue obtenida o bien por composiciono bien por recursion primitiva partir de otras funciones recursivas primitivas.

Si f fue obtenida por composicion a partir de otras funciones recursivas primitivasg1, g2, . . . , gm y h, entonces cada una de estas funciones tiene una derivacion formalcon longitud menor a k. Luego por hipotesis inductiva, cada una de ellas es unafuncion total, de donde se deduce que f es una funcion total.

Un razonamiento analogo se aplica en el otro caso. Si f fue obtenida por recur-sion primitiva a partir de otras funciones recursivas primitivas g y h, entonces porhipotesis inductiva cada una de ellas es una funcion total, y por consiguiente f esuna funcion total.

4. La funcion de Ackermann: una funcion recur-

siva no primitiva

Tal como hemos visto en el teorema 3.1, podemos asegurar que toda funcionrecursiva primitiva es una funcion total. Por sus caracterısticas –si bien no hemosprovisto aun el resultado formal correspondiente– toda funcion recursiva primitivapuede ser computada a traves de una maquina de Turing. Notemos sin embargoque dentro de todas las funciones computables a traves de maquinas de Turing setiene gran numero de funciones que son funciones parciales. En efecto, puede suce-der que una maquina de Turing nunca se detenga para una entrada determinada. Esrazonable suponer entonces que puedan existir funciones Turing-computables queno sean recursivas primitivas.

En 1925, el matematico aleman Hilbert planteo el problema de determinar siexistıa alguna funcion total computable que no fuera recursiva primitiva. En 1928,Wilhelm Ackerman (estudiante de doctorado que estaba trabajando con Hilbert)encontro la respuesta a este problema, definiendo una funcion que –en honor asu descubridor– es conocida hoy dıa como funcion de Ackerman. La funcion deAckerman tiene la forma ack : Nat × Nat → Nat, y su definicion puede darse dedistintas maneras alternativas. Dos ejemplos de como definirla se muestran en lafigura 2.

Seguidamente se muestra un ejemplo de como calcular la funcion de Ackermanpara los casos particulares de ack(0, 3) y ack(3, 0).

Ejemplo 4.1 [Computacion de Ackerman – Adaptado de [Aug95]]. Consideremosel calculo de ack(0, 3). Segun la definicion de la figura 2, resulta ack(0, 3) = 4.Consideremos ahora el calculo de ack(3, 0). Resulta:

ack(3, 0) = ack(2, 1)

–15–


Algoritmo ack:Datos de entrada: a1, a2

Datos de salida: ResultadoComienzo

Si a1 = 0entonces

Resultado ← a2 + 1si no

si a2 = 0entonces

Resultado ← ack(a1 − 1, 1)si no

Resultado← ack(a1 − 1, ack(a1, a2 − 1))fin si

fin si.Fin Algoritmo

ack(0, a2) = a2 + 1ack(a1 + 1, 0) = ack(a1, 1)ack(a1 + 1, a2 + 1) = ack(a1, ack(a1 + 1, a2))

Figura 2: Funcion de Ackerman: dos definiciones alternativas

Pero para calcular ack(2, 1) se requieren varios calculos intermedios. En efecto:

ack(2, 1) = ack(1, ack(2, 0)︸︷︷︸3

)

︸︷︷︸5

ack(2, 0) = ack(1, 1) = 3ack(1, 1) = ack(0, ack(1, 0)︸︷︷︸

2

)

= ack(0, 2) = 3ack(1, 0) = ack(0, 1) = 2ack(1, 3) = ack(0, ack(1, 2)︸︷︷︸

4

)

= ack(0, 4) = 5ack(1, 2) = ack(0, ack(1, 1)︸︷︷︸

3

)

= ack(0, 3) = 4

Por lo tanto ack(2, 1) = 5. 2

Cabe observar que la especificacion de la recursividad de la funcion de Ackermandifiere de las funciones primitivas estudiadas ya que su definicion se basa en elconcepto de recursividad anidada. La recursion anidada consiste en que parte de

–16–


los parametros de la funcion de Ackerman (que esta definida recursivamente) sonprecisamente invocaciones a la funcion misma. Se puede demostrar que la funcionde Ackerman no es recursiva primitiva, pero dada la complejidad y longitud de lademostracion no se la considerara aquı. El teorema que se enuncia a continuacionsintetiza los principales resultados obtenidos hasta el momento sobre la teorıa defunciones recursivas primitivas:

Teorema 4.1 Toda funcion recursiva primitiva es una funcion total. La recıprocadel Teorema no es cierta (esto es, no toda funcion total es una funcion recursivaprimitiva). 2

Demostracion: La primer parte del teorema esta probada por el lema 3.1. Lasegunda parte esta justificada con la existencia de la funcion de Ackerman.

Figura 3: Relacion entre funciones recursivas parciales, recursivas primitivas yTuring-computables

Genericamente se denomina funcion recursiva a aquella funcion que es una fun-cion total. Ası, la funcion de Ackerman es una funcion recursiva. La mayorıa de lasfunciones que se utilizan habitualmente son recursivas primitivas, en virtud de locual durante muchas decadas se creyo que con ellas se podıan representar todas lasfunciones totales. El resultado de Ackerman probo lo contrario, y motivo la exten-sion de las funciones recursivas primitivas con un nuevo constructor adicional, dando

–17–


lugar a las funciones recursivas parciales. La figura 3 refleja los resultados obteni-dos hasta este momento. Por su importancia, postergaremos el analisis en detallelas principales caracterısticas de las funciones recursivas parciales para la seccionsiguiente.

5. Funciones recursivas parciales

5.1. Introduccion

Hemos visto que las funciones recursivas primitivas no son suficientes para ca-racterizar a todas las funciones Turing computables. Notemos que la funcion deAckerman ack antes presentada tiene un algoritmo asociado, por lo cual es claroque puede computarse a traves de una maquina de Turing que implemente dichoalgoritmo. Sin embargo, la funcion ack no puede calcularse a traves de una funcionrecursiva primitiva. Por otro lado, sabemos que existen algoritmos que no producenuna salida para toda entrada, por lo cual se comportan de manera analoga –desdeuna perspectiva matematica– a una funcion parcial. Esto motiva la extension delas funciones recursivas primitivas para que puedan capturar la nocion de funcionrecursiva parcial. Lograremos esto extendiendo el conjunto de las funciones frpri conun nuevo constructor µ, denominado operador de minimizacion, que se define comosigue:

Definicion 5.1 [Operador de minimizacion µ] Sea n ≥ 0, g una funcion(n + 1)-aria y µy(g(n, y) = 0) el mınimo natural y tal que g(n, y) es igual a 0.La minimizacion no acotada de g es una funcion n-aria f , tal que para cualquiern ∈ Natn se verifica que f(n) =def µy(g(n, y) = 0). De esta manera, f(n) = y siexiste un valor para y que satisfaga g(n, y) = 0 de otra manera la funcion quedaindefinida. 2

Definicion 5.2 Una funcion f : Natn → Nat se denomina funcion recursiva parcialsi

1. f es una funcion base o inicial;

2. f es una funcion construıda a partir de las funciones recursivas iniciales usandoalguno de los siguientes constructores:

a) composicion;

b) recursion primitiva;

c) minimizacion no acotada.

Ninguna otra funcion sera considerada una funcion recursiva parcial. 2

Seguidamente se presentaran algunos ejemplos que ilustran la utilizacion deloperador µ de minimizacion para definir funciones recursivas parciales.7

7Los dos ejemplos que siguen fueron adaptados a partir de los presentados originalmenteen [Aug95], los que a su vez han sido tomados de textos clasicos en el tema.

–18–


Ejemplo 5.1 Sea f la funcion definida como sigue:

f(x) =def if (x = 0) then 0 else indefinido.

Aquı f es una funcion parcial, pues no esta definida para los valores distintos de 0.Puede usarse entonces el operador µy para representarla como sigue:

f(x) = µy(y + x = 0)

Notese que segun la definicion anterior, f(0) = µy(y + 0 = 0) = µy(y = 0).Esto es, f(0) resulta igual al menor y natural tal que y = 0. Claramente, el valor ybuscado es 0, por lo que f(0) = 0. Sin embargo, f(2) = µy(y + 2 = 0). Claramente,no existe ningun y natural tal que y+2 = 0. Luego f(2) esta indefinido (y en generalf(x) estara indefinido, ∀x ∈ Nat, x > 0). 2

Ejemplo 5.2 Supongase que se desea definir como funcion recursiva parcial a lafuncion f : Nat → Nat tal que dado un valor a, f(a) devuelve el mınimo b tal quea+ b = 2.

Puede reexpresarse la definicion de f como “el mınimo b tal que 2.− (a+b) = 0”

y entonces f(x) puede ser definida informalmente como f(x) = µy(2.− (x+y) = 0),

mas formalmente:

f(x) = µy(figual(difp(K22(x, y), suma(x, y)), cero(x, y))

obteniendo como expresion definitiva:

f(x) = µy[(figual ◦ (difp(K22, suma ◦ (Π2

1,Π22)), cero))](x, y)

Luego, f(0) = 2, f(1) = 1 y f(2) = 0, f(a) no esta definida para a > 2. Consideremosen mayor detalle los ejemplos anteriores:

f(0) = µy(figual(difp( K22(0, y) , suma(0, y)), cero(0, y) ) =

= µy(figual(difp( 2 , suma(0, y)), 0 ) = 2.


= µy(figual(difp( 2 , suma(2, y)), 0 ) = 0.


= µy(figual(difp( 2 , suma(3, y)), 0 ) =?

Notese que en el ultimo caso el valor resultado ¡no deberıa existir!, sin embargola funcion devuelve y = 0. En consecuencia, el ultimo ejemplo se comporta de maneraanomala. Mas adelante, en la seccion 5.6, se presentara una solucion general a esteproblema.

2

–19–


5.2. El operador de minimizacion µ: consideraciones forma-les

Es importante tener en cuenta que las funciones parciales son funciones quepueden no estar definidas para todo el dominio, es decir hay valores del dominiopara los cuales la funcion no esta definida. Es importante tener en cuenta que eldominio de las funciones recursivas parciales es nuevamente Nat, es decir, el conjuntode los numeros naturales incluıdo el cero. Utilizando el constructor de minimizacionno acotada, una funcion f(n) queda definida de la siguiente manera:

f(n) = µy(g(n, y) = 0)

La funcion de minimizacion g(n, y) = 0 debe considerar lo siguiente:

Puede no haber ningun y tal que se verfique g(n, y) = 0

Se debe garantizar que la funcion este definida para todos los valores de y.Esto se debe a que si por ejemplo g(n, 0) no esta definida, aunque g(n, 1) = 0la funcion nunca “encontrara” el resultado.

De esta manera, para cualquier funcion g(n, y) se define µy(g(n, y) = 0) como:

el menor y tal que verifique g(n, y) = 0, si ese valor de y existe y ademas, paratodo valor z tal que z ≤ y, g(n, y) 6= 0 pero g(n, z) si esta definida.

indefinida si no existe un numero y que verifique g(n, y) = 0.

Es importante tener en cuenta que µy(g(n, y) = 0) debe leerse como “el menory que verifica g(n, y = 0)”. La funcion µy(g(n, y) = 0) es una funcion solo de n;aun cuando la funcion g sea total, µy(g(n, y) = 0) no necesariamente sera total. Sepuede notar que intuitivamente el comportamiento del operador de minimizacion secorresponde al de un iterador 8 de cualquier lenguaje de programacion. El algoritmointuitivo del comportamiento del mismo es:

Algoritmo Minimizar

Datos de Entrada: nDato de Salida: y

y:= 0

Mientras g(n, y) 6= 0y:= y + 1

end {mientras}Retornar y

8Este concepto se estudiara en profundidad en la materia “Lenguajes de Programacion”.

–20–


5.3. Definiendo funciones recursivas parciales

El uso de la minimizacion es de suma utilidad para la definicion de aquellasfunciones matematicas que no se encuentran definidas en todo el dominio de losnaturales. Supongamos por ejemplo la funcion matematica f(x) = x

x−1. Claramente

la imagen de esta funcion (aun cuando su dominio sean los enteros) sera el conjuntode los numero reales (considerese por caso f(3) = 3

2= 1,5; claramente, el resultado es

un valor real). Para poder definir f dentro del formalismo que estamos describiendodebemos necesariamente redondear el resultado, definiendo a f(x) en alguna de lassiguientes formas:

f(x, y) =⌊xy

⌋f(x, y) =

⌈xy

⌉Piso Techo

Seguidamente mostraremos como obtener la funcion recursiva parcial correspon-diente a una de estas posibilidades, concretamente a la del redondeo hacia abajo opiso.

Lo primero que debemos lograr es remover el operador que indica el tipo deredondeo que se esta llevando a cabo para f(x, y) = x

y. Para ello igualamos f(x, y) a

una nueva variable, como por ejemplo z, y expresamos el operador de redondeo enterminos de una desigualdad. Para nuestro caso:⌊

x

y

⌋= z

Y de allı9

z ≤ x

y< z + 1

Ahora bien, a partir de la inecuacion anterior obtenemos la funcion g(x, y, z), la queen este caso es la que utiliza el operador de minimizacion. Hallemos la misma comosigue:

z ≤ xy

< z + 1 (1)

zy ≤ x < (z + 1)y (2)

x ≤ (z + 1)y.−1 (3)

x.−((z + 1)y

.−1) ≤ ((z + 1)y

.−1)

.−((z + 1)y

.−1) (4)

x.−((z + 1)y

.−1) ≤ 0 (5)

x.−((z + 1)y

.−1) = 0 (6)

La justificacion que permite pasar del paso (5) al (6) radica en el hecho de que unafuncion recursiva primitiva no puede tomar nunca un valor menor a cero.

Luegog(x, y, z) = x

.−((z + 1)y

.−1)

9Como z es el piso del valor de la funcion, luego la funcion original da un valor que es mayor oigual a z y menor a z + 1. Es importante notar que si se hubiese tratado del techo, la funcion realhubiese quedado acotada entre z

.−1 y z.

–21–


Formalmente la funcion g queda definida entonces como:

g(x, y, z) = difp ◦ (Π31, difp ◦ (Producto ◦ ((succ ◦ Π3

3),Π32), succ ◦ cero))(x, y, z)

y la funcion f de la siguiente manera:

f(x, y) = µz[Iguales ◦ (g ◦ (Π31,Π

32,Π

33), cero)](x, y, z)

Nota:Como regla general debe tenerse cuidado con el orden en que se despeja ladiferencia primitiva ya que esta no es asociativa, como si lo es la diferencia aritmeticaen general. En otras palabras, a

.−(b

.−c) 6= (a

.−b)

.−c, con a, b, c ∈ Nat.

5.4. Uso de trazas para verificar la definicion de funciones

Una vez obtenida la definicion de la funcion g (tal como se mostro en la seccionprecedente) es muy util verificar si la funcion definida se comporta efectivamente deigual forma que la funcion que intentamos definir. Este proceso de verificacion esaplicable a todos los formalismos, ya que cada vez que un problema es resuelto enun formalismo dado resulta indispensable verificar que la solucion encontrada seacorrecta. En el caso de las funciones recursivas parciales el mecanismo de verificacionque puede emplearse es el de las trazas. Es probable que al lector el termino le resultefamiliar a los cursos de programacion, y como se vera se trata de un concepto analogo.

Volvamos al ejemplo desarrollado en la seccion anterior. Se tenıa en ese caso quela funcion que se querıa definir era:

f(x, y) =

⌊x

y

⌋y que informalmente la funcion que hallamos es:

f(x, y) = µz[x.−((z + 1)y

.−1)︸︷︷︸

g(x,y,z)

= 0]

Probemos que la funcion esta bien definida para f(3, 2). Como se trata del pisoel resultado serıa 1. Verifiquemos efectivamente que esto es ası:

x y z (x.−(z + 1)y

.−1)︸︷︷︸

g(x,y,z)

g(x, y, z) = 0

3 2 0 3.−((0 + 1)2

.−1) 2 = 0

3 2 1 3.−((1 + 1)2

.−1) 0 = 0

Resulta claro que la funcion queda indefinida para f(3, 0). Veamos que la defini-cion hallada tambien se comporta de esa manera:

x y z (x.−(z + 1)y

.−1)︸︷︷︸

g(x,y,z)

g(x, y, z) = 0

3 0 0 3.−((0 + 1)0

.−1) 2 = 0

3 0 1 3.−((1 + 1)0

.−1) 2 = 0

3 0 2 3.−((2 + 1)0

.−1) 2 = 0

Puede observarse que el valor de z se seguira incrementando, pero al multiplicarsepor el valor de y (que es cero) hace que el valor de la funcion g no se modifique.

–22–


5.5. Como expresar la indefinicion utilizando minimizacion

En la seccion anterior observamos como se pueden definir funciones que no estandefinidas para todo el dominio mediante el uso del constructor de minimizacion.Tomemos la definicion de la funcion hallada anteriormente. Informalmente resulta:

f(x, y) = µz(g(x, y, z) = x.−((z + 1) ∗ y

.−1) = 0)

La definicion matematica de la funcion f(x, y) indica que f(x, 0) esta indefinida, yaque la division con denominador 0 no existe. Mostramos en la seccion anterior queefectivamente esto sucede. Sin embargo se presenta una anomalıa en la evaluacionde f(0, 0). Observemos en particular que sucede con la funcion hallada para f(0, 0):

f(0, 0) = µz(0.−((z + 1) ∗ 0

.−1) = 0)

Se puede observar que z = 0 satisface la igualdad y por lo tanto f(x, 0) = 0, lo queobviamente no es el resultado correcto esperado. En la proxima seccion analizaremoscomo solucionar este inconveniente.

5.6. Solucionando el problema

El problema indicado surge claramente de la construccion de la funcion g. Dadaf(n) = µy(g(n, y) = 0), veamos como construir una funcion g que garantice elcomportamiento de la funcion original.

Para ello necesitamos de las siguientes componentes:

1. Pred(n) un predicado que determina si n conforma un grupo de valores quehacen a la funcion indefinida, es decir

Pred(n) =

{1 si f(n) no esta definida0 si f(n) esta definida

2. g(n, y), la funcion que se obtiene siguiendo el metodo explicado anteriormente.A dicha funcion la llamaremos clasico(n, y).

3. Una funcion caso esp(n, y) que este definida de manera tal que no exista ningunvalor de y que verfique caso esp(n, y) = 0 si se da el predicado Pred(n) ydevuelva el valor de f(n) en caso contrario.

5.6.1. Solucion:

A partir de estas tres funciones construimos la funcion g que buscamos. La mismatendra la siguiente forma:

g(n, y) =

{caso esp(n, y) Pred(n)clasico(n, y) ¬Pred(n)

Veamos por que esta alternativa para la funcion g es correcta:

g(n, y) = (Pred(n) ∗ caso esp(n, y))︸︷︷︸A

+ ((1.−Pred(n)) ∗ clasico(n, y))︸︷︷︸

B

–23–


Veamos ahora como se aplica lo recien presentado al caso puntual de la funcionlogaritmo.

Ejemplo 5.3 [Funcion blogx yc]

1. Considerese f(x, y) = blogx yc. Sea entonces f(x, y) = z, siendo z una variableentera positiva. Resulta entonces:

z ≤ logx y < z + 1xz ≤ y < xz+1

y ≤ xz+1.−1

y.−(xz+1

.−1) ≤ (xz+1

.−1)

.−(xz+1

.−1)

y.−(xz+1

.−1) ≤ 0

y.−(xz+1

.−1) = 0

Luego la funcion clasico que utilizaremos en la construccion de g es:

clasico(x, y, z) = y.−(xz+1

.−1)

2. El valor de los parametros de f que hacen que la funcion sea indefinida esy = 0, por lo que el predicado que necesitamos es:

Pred(x, y) = Iguales(y, 0)

3. Por ultimo es necesario utilizar la funcion caso esp. En este caso la funciondebe estar indefinida, y por lo tanto no debe existir ningun valor de y queverifique caso esp(x, y, z) = 0. Esto puede lograrse simplemente utilizando lafuncion constante K3

1(x, y, z) que siempre devolvera 1, independientemente delvalor de z. Luego se tendra:

caso esp(x, y, z) = K31(x, y, z)

Es importante tener en cuenta que esta ultima funcion debe hacer uso de lavariable de minimizacion (en este caso z).

Resta entonces escribir la definicion de g y de f :

f(x, y) = µz(g(x, y, z) = 0)

g(x, y, z) = (Iguales(y, 0)︸︷︷︸Pred

∗ (K31(x, y, z))︸︷︷︸caso esp

) + ((1.−Iguales(y, 0))︸︷︷︸

¬Pred

∗ (y.−(xz+1

.−1))︸︷︷︸

clasico

)

Si f(x, 0) la funcion g queda con la siguiente forma:

g(x, 0, z) = (Iguales(0, 0)︸︷︷︸Pred

∗ (K31)(x, y, z))︸︷︷︸caso esp

) + ((1.−Iguales(0, 0))︸︷︷︸

¬Pred

∗ (0.−(xz+1

.−1))︸︷︷︸

clasico

)

es decir:

–24–


g(x, 0, z) = (1 ∗ (K31(x, y, z))︸︷︷︸caso esp

) + (0 ∗ (0.−(xz+1

.−1))︸︷︷︸

clasico

)

Es claro que la funcion f(n) esta indefinida ya que caso esp nunca puede tomar elvalor cero, es decir no existe ningun valor de z tal que (K3

1(x, y, z))︸︷︷︸caso esp

= 0 2

Nota: En este caso como la funcion siempre esta indefinida cuando el predicado y =0 es verdadero, la funcion caso especial podrıa haber sido una constante cualquiera(a excepcion del cero).

Es importante destacar que las funciones han sido presentadas informalmentepara no oscurecer la explicacion. Formalmente las funciones quedan definidas de lasiguiente forma:

Pred(x, y) = Iguales ◦ (Π22, 0)(x, y)

clasico(x, y, z) = difp ◦ (Π32, difp ◦ (pot ◦ (Π3

1, succ ◦ Π33,K

31))(x, y, z)

caso esp(x, y, z) = K13(x, y, z)

g(x, y, z) = suma◦ [prod ◦ (Pred ◦ (Π31,Π

32), caso esp),

prod ◦ (difp ◦ (K31,Pred ◦ (Π3

1,Π32)), clasico)](x, y, z)

Por ultimo la funcion f(x, y) =⌊xy

⌋queda definida formalmente de la siguiente

manera:

f(x, y) = µz[Iguales ◦ (g ◦ (Π31,Π

32,Π

33), cero)](x, y, z)

5.6.2. Estrategia Importante

Haciendo un analisis de la funcion clasico tenemos una aproximacion que sim-plifica la definicion de la funcion g bajo la metodologıa presentada en la subseccionanterior. Veamos cual es. Se puede observar que esa funcion en el caso del ejemploes:


.−1)

Es claro que siempre que y = 0 (independientemente de que composicion de fun-ciones estemos utilizando) la funcion clasico siempre tomra el valor cero, luego derealizar la diferencia primitiva. Este hecho es el que provoca que la definicion dela funcion mediante el metodo original no sea correcta en caso que la funcion quequeremos probar como recursiva parcial sea indefinida o devuelva un valor diferentede cero, en este caso particular. Puede tambien notarse que –como en el caso de lafuncion division– los casos indefinidos (exceptuando la division entre 0 y 0) quedancapturados por la funcion g tradicional.

–25–


La estrategia para simplificar la definicion de una funcion como recursiva parcialse basa en tomar como predicado el control sobre los parametros con respecto alvalor cero unicamente. Considerando el caso de la division, nuestro predicado deberıacontrolar que x e y sean ceros. Tambien podrıa considerarse solo el control sobre elhecho de si x es 0 o no, en cuyo caso la funcion caso esp debe garantizar encontrarz = 0 como respuesta siempre que y no sea 0. De ahı la restriccion que se impusosobre la funcion caso esp. En la mayorıa de los casos, no obstante, solo habrıa quegarantizar la devolucion de un valor cualquiera, situacion que implica una relajacionen las restricciones impuestas sobre la funcion.

Desde un punto de vista totalemente practico, la funcion caso caso esp, no resultanecesaria pudiendo definir la funcion g simplemente de la siguiente manera:

g(x, y, z) = clasico(x, y, z) ∗ desiguales(y, 0) + iguales(y, 0)

donde clasico(x, y, z) es por ejemplo la siguiente funcion:


.−1)

Claramente cuando el parametro y tiene el valor cero, la funcion g nunca tomaradicho valor (iguales(y, 0) siempre es igual a 1). De esta manera, se puede notar quela funcion esta correctamente definida aun sin el caso especial, antes mencionado.

6. Expresividad de las funciones recursivas par-

ciales: la nocion de cadena

Las funciones recursivas primitivas en particular (y las funciones recursivas par-ciales en general) tienen la caracterıstica de estar definidas sobre n-uplas (x1, x2, . . . , xn)de numeros naturales. Notese en tal sentido que un numero natural k cualquiera pue-de siempre codificarse en el sistema binario, y pensarse entonces como una secuenciaparticular de 1’s y 0’s. En consecuencia, una n-upla de numeros naturales puedeabstraerse a su vez como una secuencia de 1’s y 0’s, cuyo significado dependera dela interpretacion asociada a dichos dıgitos binarios.

Un caso distinguido en este sentido lo constituyen las cadenas de sımbolos, utili-zadas como datos de entrada para los distintos automatas de estados finitos presen-tados en capıtulos anteriores de la materia. Dado un alfabeto finito Σ, siempre esposible codificar cada uno de sus sımbolos como una serie de 0’s y 1’s (vease comoejemplo la tabla ASCII en la figura 4). Luego una cadena w ∈ Σ? sera tambien unasecuencia de 0’s y 1’s. Esta situacion motiva a pensar en que es factible definir fun-ciones recursivas parciales cuyo dominio no sean n-uplas de numeros naturales, sinon-uplas de cadenas. El dominio sera en tal caso (Σ?)n y el rango Σ?. En lo que siguese introduciran las definiciones que caracterizan a las funciones recursivas primitivaspara cadenas, asumiendo un alfabeto Σ = {a, b}, el cual puede ser cambiado segunse desee para cada problema particular.10

10La eleccion de un alfabeto reducido obedece a que las definiciones de funciones recursivasprimitivas sobre cadenas crecen rapidamente en complejidad en relacion con el tamano del alfabeto.

–26–


Sımbolo Codigo ASCII En BinarioA 65 01000001B 66 01000010C 67 01000011D 68 01000100...

Figura 4: Algunos caracteres de la tabla ASCII

Definicion 6.1 [Funciones recursivas primitivas sobre cadenas] Una funcion f sedira recursiva primitiva sobre Σ? si es f satisface alguno de los siguientes casos:

1. La funcion f es alguna de las siguientes funciones base o iniciales para cadenasdefinidas sobre Σ?, a saber:

Cadena vacıa: La funcion cadena vacıa lambda : (Σ?)n → {λ} definidapor: lambda(x1, . . . , xn) = λ

Concatenacion: Las funciones de concatenacion sucesorA : Σ? → Σ? ysucesorB : Σ? → Σ? definida para toda cadena x ∈ Σ? como:

sucesorA(x) = ax

sucesorB(x) = bx

Identidad Generalizada La funcion de identidad generalizada, definidacomo πn

i : (Σ?)n → Σ?. Para 1 ≤ i ≤ n, resulta πni (x1, . . . , xn) = xi donde

n indica el numero de argumentos e i indica que se selecciona el argumentoi-esimo de la n-upla.

2. La funcion f puede ser generada a partir de funciones iniciales sobre Σ? porla aplicacion de las siguientes funciones constructoras:

Composicion: La definicion de composicion es analoga a la dada parafunciones recursivas primitivas sobre naturales (def. 2.1).

Recursion primitiva: Sea n ≥ 0, y sea g una funcion total recursivaprimitiva n-aria. Sean h1, h2 dos funciones totales recursivas primitivas(n + 2)-arias.11 La funcion f estara definida por recursion primitiva apartir de g, h1 y h2 si es una funcion total (n+ 1)-aria tal que para todan-upla de (Σ?)n y w ∈ (Σ?), resulta

f(x1, x2, . . . , xn, λ) = g(x1, x2, . . . , xn)f(x1, x2, . . . , xn, aw) = h1(x1, x2, . . . , xn, w, f(x1, .., xn, w))f(x1, x2, . . . , xn, bw) = h2(x1, x2, . . . , xn, w, f(x1, .., xn, w))

11Notese que deben existir tantas hi como sımbolos en el alfabeto Σ.

–27–


Ninguna otra funcion excepto las funciones base y las construibles segun lasreglas anteriores son funciones recursivas primitivas sobre Σ?. 2

Nota: cabe observar que lambda es una funcion que, aplicada a cualquier argumentodevuelve la cadena vacıa λ. La funcion lambda para cadenas cumple un rol analogoa la funcion cero para naturales. Similarmente, la funcion equivalente a sucesorAo sucesorB en la definicion de funcion recursiva primitiva sobre naturales es suc.Notemos que en el caso de cadenas de caracteres es necesario definir una funcionsucesor particular para cada sımbolo del alfabeto sobre el que esta definido Σ?.Ası, por caso, si el alfabeto en cuestion fuera Σ = {c, d, e}, serıa necesario definirfunciones sucesor sucesorC, sucesorD y sucesorE.

Ejemplo 6.1 Dar una funcion recursiva primitiva cabeza que obtenga el primersımbolo de una cadena. Ası, por caso, cabeza(abb) = a, y cabeza(bbaa) = b. Lafuncion buscada puede definirse como sigue:

cabeza(λ) = lambda()cabeza(aw) = (sucesorA ◦ lambda)(w, cabeza(w))cabeza(bw) = (sucesorB ◦ lambda)(w, cabeza(w))

2

Ejemplo 6.2 [Concatenacion de cadenas (adaptado de [Aug95])] Supongase quequiere definirse una funcion recursiva primitiva concat que concatene dos cadenasx e y. Ası, por caso, concat(ab, bb) = abbb. La funcion concat puede definirse comosigue:

concat(x, y) = concatenar(y, x)

concatenar(z, λ) = π11(z)

concatenar(z, aw) = (sucesorA ◦ π33)(z, w, concatenar(z, w))

concatenar(z, bw) = (sucesorB ◦ π33)(z, w, concatenar(z, w))

La figura 5 ilustra los sucesivos pasos requeridos para computar el valor deconcat(ab, bb) . 2

7. Aplicaciones de la teorıa de funciones recursi-

vas

Las funciones recursivas constituyen un importante elemento de referencia co-mo modelo formal de la computacion. Las investigaciones realizadas en el area defunciones recursivas dieron lugar a una vertiente de esta teorıa, denominada calculolambda, elaborado por Alonzo Church.

La teorıa de las funciones recursivas parciales muestra como una abstraccionmatematica de larga tradicion (como la nocion de funcion) pudo utilizarse paraformalizar la nocion de procedimiento efectivo. Es importante notar en tal sentido

–28–


La funcion esta definida como:

concat(x, y) = concatenar(y, x) (1)

concatenar(z, λ) = π11(z) (2)

concatenar(z, aw) = (sucesorA ◦ π33)(z, w, concatenar(z, w)) (3)

concatenar(z, bw) = (sucesorB ◦ π33)(z, w, concatenar(z, w)) (4)

Veamos como se computa concat(ab, bb)

concat(ab, bb) = concatenar(bb, ab) por (1)concatenar(bb, ab) = (sucesorA ◦ π3

3)(bb, b, concatenar(bb, b)︸︷︷︸bbb

) por (3)

= sucesorA ◦ π33(bb, b, bbb)︸︷︷︸

bbb︸︷︷︸abbb

concatenar(bb, b) = (sucesorB ◦ π33)(bb, λ, concatenar(bb, λ)︸︷︷︸

bb

) por (4)

= sucesorB ◦ π33(bb, λ, bb)︸︷︷︸

bb︸︷︷︸bbb

concatenar(bb, λ) = π11(bb)︸︷︷︸bb

por (2)

Figura 5: Computacion de concat(ab, bb)

que la definicion de una funcion matematica es estatica, y que corresponde a lo que sedenomina especificacion de un algoritmo en la teorıa de la programacion. El calculode la funcion, por otra parte, representa el aspecto dinamico de un procedimientoefectivo (la ejecucion de un algoritmo).

Un aspecto interesante que brinda la teorıa de funciones es la equiparacion delas nociones de dato y programa. Si se considera la funcion f(x) = x2, f : Nat→Nat,puede verse a f(x) como un algoritmo cuyo dato de entrada es un numero naturala y su dato de salida es otro numero natural (el cuadrado de a). Sin embargo, lateorıa de funciones recursivas primitivas permite definir una nueva funcion g porcomposicion a partir de f (como por ejemplo g(f(x))). Notese que en este caso lafuncion f es usada como dato de entrada para g.

Las funciones recursivas sirven de modelo formal para un paradigma de pro-gramacion denominado paradigma funcional.12 Algunos lenguajes que pertenecenal paradigma funcional son Haskell, ML, Scheme y Lisp. El lenguaje Lisp fuedesarrollado por John McCarthy y es uno de los lenguajes de programacion masantiguos, estando orientado a problemas de Inteligencia Artificial. Por otro lado, enmuchas universidades del mundo se utilizan los lenguajes lenguajes ML y Schemecomo los primeros lenguajes para aprender a programar.

12El estudio detallado de este paradigma se vera en la materia “Lenguajes de Programacion”.

–29–


8. Notas biograficas

Figura 6: Stephen Cole Kleene (izq.) y Kurt Godel (der.)

Stephen Cole Kleene (1909-1994)

Stephen Cole Kleene13 nacio el 5 de enero de 1909 en Hartford (Connecticut,EE.UU) y murio el 25 de enero de 1994 en Madison, (Wisconsin, EE.UU). Realizosus primeros estudios de grado en Amherst College. Luego prosiguio con estudiosde doctorado en la Universidad de Princeton, culminandolos en 1934, supervisadopor Alonzo Church. Su tesis se titulaba “A Theory of Positive Integers in FormalLogic”. Luego Kleene continuo dando clases en Princeton hasta que se traslado ala Universidad de Wisconsin en Madison en 1935. Paso a ser profesor de tiempocompleto en esa Universidad en 1948 y permanecio como parte del cuerpo docentehasta que se jubilo en 1979.

La investigacion de Kleene se centro en la teorıa de algoritmos y funciones recur-sivas. Fue el quien desarrollo el campo de la teorıa de la recursion junto con Church,Godel, Turing y otros. Contribuyo al denominado intuicionismo matematico quehabıa sido fundado por Brouwer.

Su trabajo en la teorıa de la recursion ayudo a sentar las bases teoricas de lasciencias de la computacion. A partir de proveer metodos para determinar que pro-blemas son solubles, el trabajo de Kleene llevo al estudio de que funciones puedencomputarse.

En una conferencia en la Universidad de Chicago en 1995, Robert Soare describioel trabajo de Kleene con estas palabras:

La formulacion de Kleene de lo que es una funcion computable a travesde seis esquemas es una de las mas sucintas y utiles que existen. Sutrabajo previo en funciones lambda jugo un rol central en convalidar latesis de Church de que estas clases coinciden con las funciones calculablesintuitivamente.

Desde 1930 en adelante, Kleene fue mas alla que cualquier otro matema-tico en el desarrollo de las nociones de computabilidad y proceso efectivo

13Adaptado a partir de un artıculo de J. J. O’Connor y E. F. Robertson publicado enhttp://www-groups.dcs.st-and.ac.uk/ history/Mathematicians/.

–30–


en todas sus formas, tanto abstractas como concretas, tanto matematicascomo filosoficas. Ayudo a poner los cimientos de un area para luego mo-verse a la siguiente, haciendo que cada uno de los campos que investigarase transformaran en un nuevo area de investigacion.

Kleene desarrollo un amplio numero de topicos en computabilidad: lajerarquıa aritmetica, grados de computabilidad, ordinales computables yteorıa hiperaritmetica, automatas finitos y conjuntos regulares –con enor-mes consecuencias para las ciencias de la computacion–, computabilidadde tipos superiores, realizabilidad recursiva para aritmetica intuicionistacon consecuencias para la filosofıa y para la correctitud de programas encomputacion.

Los libros mas conocidos de Kleene son Introduction to Metamathematics (1952)y Mathematical Logic (1967).

Kurt Godel (1906-1978)

Kurt Godel14 nacio el 28 de abril de 1906 en Brunn, Imperio Austrohungaro(actualmente Brno, Republica Checa), murio el 14 de enero de 1978 en Princeton,New Jersey, EE.UU. Asistio a la escuela en Brunn, completando sus estudios en1923. En la escuela secundaria, segun cuenta su hermano Rudolf Godel, era unestudiante destacado. Para el asombro de sus profesores y companeros dominaba lasmatematicas de nivel universitario en los ultimos anos del secundario. Segun cuentanquienes lo conocieron, se rumoreaba que su nivel en matematica y lengua era muchomejor que en literatura e historia. En latın tuvo tambien un excelente desempeno.

Kurt entro a la Universidad de Viena en 1923. Sus profesores fueron Furtwangler,Hahn, Wirtinger, Menger, y Helly, entre otros. Como estudiante tomo un seminariodirigido por el profesor Schlick en donde se estudiaba el libro de Bertrand Russell“Introduction to mathematical philosophy”. Olga Tausky-Todd, una companera deestudios de Godel, escribio: “Lentamente se hizo obvio que el estaba atado a lalogica, que iba a ser un estudiante de Hahn y no de Schlick, y que tenıa un talentoincreıble”. Termino su trabajo doctoral bajo la supervision de Hahn en 1929 y sehizo miembro de la facultad de la Universidad de Viena en 1930. Pertencio a laescuela de positivismo logico hasta 1938.

Godel se volvio especialmente conocido a partir de la demostracion de sus teo-remas de incompletitud. En 1931 publico estos resultados en la publicacion “Uberformal unentscheidbare Satze der Principia Mathematica und verwandter Systeme”.Demostro resultados fundamentales sobre sistemas axiomaticos, demostrando queen cualquier sistema matematico axiomatico hay proposiciones que no pueden serdemostradas (o refutadas) a partir de los axiomas del sistema. En particular, nopuede demostrarse la consistencia logica de esos axiomas.

Esto significo el fin de cien anos de intentos de establecer axiomas para fundar atodo el cuerpo de conocimiento de las matematicas sobre una base axiomatica. Unintento importante habıa sido el realizado por Bertrand Russell con sus “Principia

14Transcripcion adaptada a partir de un artıculo de J. J. O’Connor y E. F. Robertson publicadoen http://www-groups.dcs.st-and.ac.uk/ history/Mathematicians/.

–31–


Mathematica” (1910-13). Otro fue el formalismo de Hilbert que recibio un severoreves a partir de los resultados de Godel. El teorema no destruyo la idea fundamentaldel formalismo, pero demostro que cualquier sistema alternativo deberıa ser masabarcativo que aquel desarrollado por Hilbert.

Los resultados de Godel fueron un hito en las matematicas del siglo xx, mos-trando que las matematicas no son un objeto finito y totalmente terminado, comose creyo mucho tiempo. Tambien implicaron que una computadora nunca puede serprogramada de tal manera que pueda dar una respuesta a todas las preguntas de lasmatematicas.

En 1933 Hitler llego al poder. En los comienzos esto no tuvo efecto en la vida deGodel en Viena. Tenıa poco interes en temas polıticos. No obstante, tras la muerte delSchlick en manos de un estudiante nacionalsocialista, Godel se sintio profundamenteafectado, y tuvo una etapa depresiva (debe recordarse que fue un seminario deSchlick el que motivo a Godel a iniciarse en la logica). Su hermano Rudolf escribio alrespecto: “Este evento fue seguramente la razon de porque mi hermano atraveso unasevera crisis nerviosa por algun tiempo, lo que por supuesto fue de gran preocupacion,sobre todo para mi madre.”.

Poco despues de su recuperacion recibio la primer convocatoria al cargo de Pro-fesor Invitado en los EE.UU. En 1934 Godel dio una serie de presentaciones en laUniversidad de Princeton tituladas “On undecidable propositions of formal mathe-matical systems”. Por sugerencia de Veblen, quien acababa de completar su Tesisde Ph.D. en Princeton, tomo notas de estas presentaciones que fueron publicadasposteriormente.

Volvio a Viena, y se caso con Adele Porkert en 1938, pero cuando estallo la guerratuvo la fortuna de poder retornar a los EE.UU. aunque tuvo que viajar via Rusia yJapon. En 1940 Godel emigro a los EE.UU. y mantuvo un cargo en el Instituto paraEstudios Avanzados de Princeton, desde 1953 hasta su muerte. Recibio la MedallaNacional de Ciencia en 1974. Su trabajo sobre la consistencia del axioma de elecciony de la hipotesis del continuo generalizada con los axiomas de la teorıa de conjuntos(1940) es un clasico de la matematica moderna.

Su hermano Rudolf, quien era medico, escribio: “Mi hermano tenıa una opinionfija y muy individual acerca de todo, y muy difıcilmente podıa hacerselo canmbiarde opinion. Por desgracia el creyo toda su vida que tenıa siempre razon no solo enmatematicas, sino tambien en medicina, por lo que era un paciente muy difıcil detratar.”. Despues de sufrir una importante perdida de sangre por una ulcera delduodeno, Godel empezo a seguir hasta el final de su vida una dieta extremadamenteestricta, que le hizo perder peso gradualmente. Hacia el final de su vida Godel llegoa estar convencido de que querıan envenenarlo, y comenzo a rechazar la comida paraevitar ser envenenado, lo que le ocasiono la muerte por inanicion.

Wilhelm Ackermann (1896-1962)

Wilhelm Ackermann15 nacio el 29 de marzo de 1896 en Schoenebeck (Altena, Ale-mania) y murio el 24 de diciembre de 1962 en Luedenscheid (Alemania). Ackermann

15Transcripcion adaptada a partir de un artıculo de Walter Felscher (Tubingen). Publicado enhttp://www-groups.dcs.st-and.ac.uk/ history/Mathematicians/.

–32–


fue un logico y matematico que trabajo con Hilbert Hilbert en Gottingen. Acker-mann recibio su grado doctoral en 1925 con su Tesis “Begrundung des ‘tertium nondatur’ mittels der Hilbertschen Theorie der Widerspruchsfreihei”,16 la cual fue dirigi-da por Hilbert. Su contenido involucraba una prueba de consistencia de la aritmeticasin utilizar induccion. Desde 1927 hasta 1961 Ackermann fue profesor en escuelassecundarias en Burgsteinfeld y posteriormente en Luedenscheid. Fue miembro dela Academia de las Ciencias en Gottingen, y profesor honorario de la Universidadde Munster. En 1928, Ackermann observo que A(x, y, z), la z-esima exponenciacioniterada de x con y, era un ejemplo de una funcion recursiva que no es recursiva pri-mitiva. La funcion A(x, y, z) fue simplificada a una funcion de dos variables P (x, y)por Rosza Peter. En 1928 aparecio un libro que se reimprimio varias veces, titulado“Grundzuge der Theoretischen Logik” escrito por Hilbert y Ackermann. Entre lostrabajos posteriores de Ackermann pueden mencionarse pruebas de consistencia parateorıas de conjuntos (1937), aritmetica completa (1940), logica libre de tipos (1952),una nueva axiomatizacion de la teorıa de conjuntos (1956), y un libro “Solvable casesof the decision problem” (North Holland, 1954).

Referencias

[Aug95] Augusto, J. C. Fundamentos de Ciencias de la Computacion - Notas deCurso. Universidad Nacional del Sur, Bahıa Blanca, Argentina, 1995.

[LP98] Lewis, H., y Papadimitriou, C. Elements of the Theory of Computation(2nd. Edition). Prentice Hall, 1998.

16En castellano: “Fundamentacion del ‘tertium non datur’ por medio de la teorıa de Hilbert dela libertad de contradiccion”.

–33–

Documents

Funciones Recursivas Parciales - Universidad Nacional del Surcs.uns.edu.ar/materias/tc2do/downloads/Apuntes/Funciones... · 2019-09-27 · 2. Funciones Recursivas Primitivas Las funciones