Redes Neuronales Recurrentes An´alogas con Pesos Racionales Andr´es Sicard Ram´ırez

Juan C. Agudelo Agudelo

Mario E. V´elez Ruiz

[email protected]

[email protected]

[email protected]

Grupo de L´ogica y Computaci´on Escuela de Ciencias y Humanidades Universidad EAFIT; Medell´ın, Colombia Resumen Se definen las redes neuronales recurrentes an´ alogas (ARNNs) y las funciones recursivas y se demuestra la equivalencia computacional entre las ARNNs con pesos racionales y las m´ aquinas de Turing por medio de la equivalencia computacional entre las ARNNs con pesos racionales y las funciones recursivas. Abstract We define analog recurrent neural networks (ARNN) and recursive functions then we demonstrate computational equivalence between ARNNs with rational weights and Turing machines mediating computational equivalence between ARNNs with rational weights and recursive functions.

1

Redes Neuronales Recurrentes An´ alogas

Definici´ on 1 (Red Neuronal Recurrente An´aloga). Una ARNN (Analog Recurrent Neural Network) [11] es una red neuronal compuesta por N procesadores elementales llamados neuronas, cada neurona tiene asociado un valor de activaci´ on xi (t), en cada instante discreto de tiempo t la red neuronal recibe M entradas binarias uj (t). La din´ amica de la red consiste en calcular los valores de activaci´ on de las neuronas de acuerdo a las entradas y los valores de activaci´ on de las neuronas en el instante de tiempo anterior. Cada neurona calcula su valor de activaci´ on de acuerdo a la ecuaci´ on: xi (t + 1) = σ

X N

 X   M aij · xj (t) + bij · uj (t) + ci ,

j=1

(1)

j=1

donde aij es el peso del enlace entre la neurona xj y la neurona xi , bij es el peso del enlace entre la neurona uj y la neurona xi y ci es el peso constante asociado a la neurona xi . La funci´ on σ es llamada “funci´ on de activaci´ on” o “funci´ on de respuesta” y el argumento que recibe es una funci´ on de las entradas a la neurona llamada “funci´ on de red”. En cada instante de tiempo la salida de la red es el valor de activaci´ on de un subconjunto de ` neuronas y1 (t), . . . , y` (t). Los valores de activaci´ on de las neuronas son representados por un vector X(t) de dimensi´ on N × 1, las entradas por un vector U(t) de dimensi´ on M × 1, los pesos de los enlaces entre las neuronas por una matriz A de dimensi´ on N × N , los pesos de los enlaces entre las entradas y las neuronas por una matriz 1

B de dimensi´ on N × M y los pesos constantes por un vector C de dimensi´ on N × 1. De esta forma se representa la din´ amica total de la red por la ecuaci´ on matricial: X(t + 1) = σ(A · X(t) + B · U(t) + C).

(2)

Definici´ on 2 (Computaci´ on en una ARNN). Una computaci´ on en una ARNN es una sucesi´ on de c´ alculos en instantes discretos de tiempo de los valores de activaci´ on X(t + 1) de las neuronas de acuerdo a los valores de activaci´ on X(t) y las entradas U(t) en el instante de tiempo anterior, teniendo en cuenta los enlaces y pesos de la red A, B y C, de acuerdo a la ecuaci´ on (2). Las salidas en cada iteraci´ on son un subconjunto de los valores de activaci´ on calculados y1 (t), . . . , y` (t). Al inicio de la computaci´ on, tiempo t = 0, cada neurona tiene un valor de activaci´ on inicial xi (0) (normalmente xi (0) = 0 para i = 1, 2, . . . , N ). La computaci´ on termina cuando no hay m´ as entradas. Hay que tener en cuenta que en la mayor´ıa de ARNNs se introduce un retardo r en la computaci´ on, es decir, los primeros r valores de activaci´ on de las neuronas de salida no deben ser tomados en cuenta como parte del c´ omputo, esto se debe a que las entradas por lo general no llegan directamente a las neuronas de salida y para llegar a afectarlas tienen primero que propagarse por otras neuronas de la red, este tiempo de retardo depende de la estructura espec´ıfica de la red.

2

Funciones Recursivas

Definici´ on 3 (Funci´ on Num´erico-Te´ orica). Se denomina funci´ on num´erico-te´ orica a toda funci´ on definida en k-tuplas de n´ umeros naturales Nk y evaluada en n´ umeros naturales N = {0, 1, 2, . . .} [6], es decir, f es una funci´ on n´ umerico-te´ orica ⇐⇒ f : Nk → N. Definici´ on 4 (Representaci´ on k-tuplas). Para efectos de simplificaci´ on en la notaci´ on se utilizar´ a el s´ımbolo ~xk para representar la tupla x1 , x2 , . . . , xk . Definici´ on 5 (Funci´ on Recursiva). Las funciones recursivas son un subconjunto de las funciones num´ericote´ oricas, se dice que una funci´ on f : Nk → N es recursiva si [8, 9, 3, 6]1 : 1. Es una de las siguientes funciones: • Z(x) = 0, funci´ on constante cero. • S(x) = x + 1, funci´ on sucesor. • Pkn (~xn ) = xk , funci´ on k-´esima proyecci´ on en n variables, k ≤ n. Estas funciones son llamadas funciones recursivas b´ asicas y son los axiomas de la teor´ıa. 2. Puede obtenerse por sucesi´ on finita de aplicaciones de las siguientes reglas: • Esquema de composici´ on: Si f (~yn ) y g1 (~xk ), . . . , gn (~xk ) son funciones recursivas entonces h(~xk ) = f (g1 (~xk ), . . . , gn (~xk )) es una funci´ on recursiva. 1 En

[5] se da una presentaci´ on alternativa de las funciones recursivas

2

• Esquema de recurrencia primitiva: Si f (~xk ) y g(~xk , y, z) son funciones recursivas entonces h(~xk , y) definida por: h(~xk , 0) = f (~xk ), h(~xk , y + 1) = g(~xk , y, h(~xk , y)), es una funci´ on recursiva. • Esquema de minimizaci´ on: Si f (~xk , y) es una funci´ on recursiva, se puede construir la funci´ on h(~xk ) = µy (f (~xk , y) = 0) donde:  El menor y tal que f (~xk , z) est´e definida para todo z ≤ y    y f (~x , y) = 0, k µy (f (~xk , y) = 0) =     No est´ a definida si no existe tal y. Si la funci´ on µy (f (~xk , y) = 0) est´ a definida para todo ~xk entonces la funci´ on h(~xk ) es una funci´ on recursiva total, de otro modo, la funci´ on h(~xk ) es una funci´ on recursiva parcial. Es bien conocida la equivalencia entre las funciones recursivas parciales y las funciones que se pueden computar en una m´ aquina de Turing (funciones Turing-computables), es decir, toda funci´on Turing-computable puede ser expresada como una funci´ on recursiva parcial y para toda funci´on recursiva parcial se puede construir una m´ aquina de Turing que la compute. Esta equivalencia es presentada en [5, 9, 2, 3, 6].

3

Relaci´ on entre ARNN y M´ aquina de Turing

Al restringir algunos par´ ametros de las ARNNs, tales como los posibles valores que pueden tomar los pesos y las caracter´ısticas de la funci´ on de activaci´ on, se puede obtener modelos con diferente poder de computaci´ on. En particular, si se tiene una ARNN con funci´on de activaci´on σ definida por:   0 si x < 0, (3) σ(x) = x si 0 ≤ x ≤ 1,   1 si x > 0, y se restringen los posibles valores que pueden tomar los pesos (aij , bij y ci ) de la red a los n´ umeros racionales, los valores de activaci´ on de las neuronas ser´an valores racionales en el intervalo [0, 1] y el poder de computaci´ on de la ARNN es equivalente al de una m´aquina de Turing. Para demostrar tal equivalencia se aprovechar´ a la equivalencia entre las funciones recursivas parciales y las funciones Turing-computables, se demostrar´ a la equivalencia computacional entre las ARNNs con pesos racionales y las funciones recursivas parciales y a partir de este hecho se aceptar´a la equivalencia computacional entre las ARNNs con pesos racionales y las m´ aquinas de Turing. Antes de demostrar la equivalencia computacional entre las ARNNs con pesos racionales y las funciones recursivas parciales se presentar´ an algunas definiciones: Definici´ on 6 (Funci´ on i-´esimo Primo). Se denotar´ a por P n(i) a la funci´ on que calcula el i-´esimo n´ umero primo. Se puede demostrar que esta funci´ on es recursiva. 3

Definici´ on 7 (Codificaci´ on de G¨ odel). Sea Σ = {a1 , a2 , a3 , . . .} un alfabeto enumerable, y Σ∗ el conjunto de las palabras construibles sobre Σ. La codificaci´ on de G¨ odel permite dar una codificaci´ on num´erica N G: Σ∗ → ∗ N a las palabras de Σ , esta codificaci´ on se basa en el teorema fundamental de la aritm´etica y se obtiene aplicando los siguientes pasos: 1. A cada s´ımbolo del alfabeto Σ se le asigna un n´ umero natural, N (ai ) = i para todo ai ∈ Σ, i ∈ N. 2. El n´ umero de G¨ odel de una palabra α = s1 s2 . . . sn ∈ Σ∗ est´ a dado por: N G(α) = 2N (s1 ) · 3N (s2 ) · · · P n(n)N (sn ) =

n Y

P n(i)N (si ) .

(4)

i=1

Definici´ on 8 (Codificaci´ on de k-tuplas de Naturales en Naturales). Para codificar k-tuplas de naturales en naturales se utilizar´ a la codificaci´ on de G¨ odel de la siguiente manera: Sea (x1 , . . . , xk ) ∈ Nk entonces k definimos CK: N → N por: x1

CK(x1 , . . . , xk ) = 2

x2

·3

· · · P n(k)

xk

=

k Y

P n(i)xi .

(5)

i=1

Se puede demostar que CK es una funci´ on recursiva. Definici´ on 9 (Decodificaci´ on de k-tuplas de Naturales). Se puede obtener los elementos de las k-tuplas codificadas aplicando la codificaci´ on anterior (ec. 5) por: Ei (y) = m´ aximo w ≤ y tal que P n(i)w divide a y; w, y ∈ N.

(6)

on Ei es una funci´ on De este modo Ei (2x1 · 3x2 · · · P n(i)xi · · · P n(n)xn ) = xi . Se puede demostrar que la funci´ recursiva. Teorema 1. La computaci´ on de toda ARNN con pesos racionales puede ser expresada como una funci´ on recursiva. Demostraci´ on. La demostraci´ on se hace para aij , bij , ci ∈ Q+ ∪ {0}. 1. Se expresar´ a primero la funci´ on que calcula el valor de activaci´on para una neurona (ec. 1) como una funci´ on recursiva, esta ecuaci´ on se puede ver como una funci´on fi de la forma fi : QN × {0, 1}M → Q donde:  X   X N M
aij · xj (t) + bij · uj (t) + ci , con : (7) fi X(t), U(t) = σ j=1

j=1

X(t) = x1 (t), . . . , xn (t); 0 ≤ xi (t) ≤ 1 ∈ Q, vector de activaci´on. U(t) = u1 (t), . . . , um (t); ui (t) ∈ {0, 1}, vector de entradas. aij , bij , ci ∈ Q+ ∪ {0}, pesos de la red. Teniendo en cuenta que la teor´ıa de funciones recursivas est´a definida sobre funciones num´ericote´ oricas, para expresar fi como una funci´on recursiva se llevar´a fi a la funci´on fi0 de la forma 0 fi : N2N +M → N, dicha funci´ on calcular´a el valor de activaci´on de una neurona codificando el resultado en los n´ umeros naturales mediante la funci´on CK (ec. 5). 4

2. El argumento de la funci´ on σ (ec. 7), llamado funci´on de red, puede ser visto como la funci´on neti de la forma neti : QN × {0, 1}M → Q donde: X  X  N M
neti X(t), U(t) = aij · xj (t) + bij · uj (t) + ci . (8) j=1

j=1

3. Todo n´ umero racional positivo x ∈ Q+ puede ser expresado como la pareja ordenada de n´ umeros naturales (N x, Dx); N x, Dx ∈ N, N x simboliza el numerador de x y Dx simboliza el denominador de x. 0 se representa por la pareja (0, 1). 4. Con base en el numeral (3) se redefine la funci´on neti (ec. 8) por net0i : N2N +M → N2 donde:  X  X M N
N ci N bij N aij N xj (t) 0 0 · + · uj (t) + , con : neti X (t), U(t) = Daij Dxj (t) Dbij Dci j=1 j=1

(9)

X0 (t) = N x1 (t), Dx1 (t), . . . , N xn (t), Dxn (t); N xi (t), Dxi (t) ∈ N, vector de activaci´on expresado en parejas de n´ umeros naturales. U(t) = u1 (t), . . . , um (t); ui (t) ∈ {0, 1}, vector de entradas. N aij , Daij , N bij , Dbij , N ci , Dci ∈ N, pesos de la red expresados en parejas de n´ umeros naturales.
Por simplificaci´ on en la notaci´ on se escribir´a net0i en lugar de net0i X0 (t), U(t) . 5. La funci´ on net0i se puede partir en dos funciones: numi : N2N +M → N y deni : N2N +M → N, para calcular el primer elemento (numerador) de net0i y el segundo elemento (denominador) de net0i respectivamente, es decir, net0i = (numi , deni ). deni y numi se pueden expresar como funciones recursivas as´ı:

deni X0 (t), U(t) = mcm Dai1 · Dx1 (t), . . . , Dain · Dxn (t), Dbi1 , . . . , Dbim , Dci , (10) donde mcm es la funci´ on m´ınimo com´ un m´ ultiplo, mcm es
una funci´on recursiva. Por simplificaci´ on en la notaci´ on se escribir´ a deni en lugar de deni X0 (t), U(t) . ! N     X
0 numi X (t), U(t) = qt Daij · Dxj (t), deni · N aij · N xj (t) + (11) j=1

! M      X qt Dbij , deni · N bij · uj (t) + qt(Dci , deni ) · N ci . j=1

donde qt(x, y) es el cociente de dividir y por x, qt es una funci´on recursiva, adem´as, la suma, la multiplicaci´ on y deni son funciones recursivas, por lo tanto numi es una funci´on recursiva por ser composici´ on de funci´
ones recursiva. Por simplificaci´on en la notaci´on se escribir´a numi en lugar de numi X0 (t), U(t) . 6. Se redefine la funci´ on σ (ec. 3) por σ 0 para que opere sobre dos elementos codificando el resultado en los n´ umeros naturales mediante la funci´on CK (ec. 5): ( CK(1, 1) si x1 > x2 , 0 σ (x1 , x2 ) = (12) CK(x1 , x2 ) si x1 ≤ x2 . σ 0 (x1 , x2 ) es una funci´ on recursiva. 5

7. Luego fi0 de la forma fi0 : N2N +M → N donde:
fi0 X0 (t), U(t) = σ 0 (net0i ) = σ 0 (numi , deni ),

(13)

calcula el valor de activaci´ on de una neurona codificando el resultado en los n´ umeros naturales mediante la funci´ on CK (ec. 5) y es una funci´ on recursiva. 8. Teniendo ya expresada la funci´ on de activaci´on para una neurona como una funci´on recursiva, se expresar´ a la funci´ on de activaci´ on o de din´amica de la red para todas las neuronas como una funci´ on recursiva, dicha funci´ on se puede ver como una funci´on de la forma f : QN × {0, 1}M → QN . Para definir f con base en fi0 se redefine f por f 0 de la forma f 0 : N2N +M → N2N donde:

f 0 X0 (t), U(t) = E1 (f10 ), E2 (f10 ), . . . , E1 (fn0 ), E2 (fn0 ) , (14) donde Ei es la funci´ on de decodificaci´on dada por la ecuaci´on (6). Para expresar f 0 como una funci´ on recursiva se redefine f 0 por f 00 de la forma f 00 : N2N +M → N donde: 

 f 00 X0 (t), U(t) = CK f 0 X0 (t), U(t) . (15) La funci´ on f 00 calcula el valor de activaci´on de todas las neuronas y los codifica en los n´ umeros naturales mediante la funci´ on CK (ec. 5). f 00 es una funci´on recursiva debido a que fi0 , Ei y CK son funciones recursivas. 9. Para simular el comportamiento de una computaci´on en una ARNN en t instantes discretos de tiempo, se debe realizar una sucesi´ on de t c´ alculos de los valores de activaci´on de las neuronas, comenzando con valores de activaci´ on xi (0) = 0 para todas las neuronas 1 ≤ i ≤ N y recibiendo en cada instante de tiempo t0 , 0 ≤ t0 ≤ t − 1, el vector de entradas U(t0 ). Esto se puede expresar mediante la funci´ on:
cmp U(0), . . . , U(t − 1), 0 =20 · 31 · · · P n(2n − 1)0 · P n(2n)1 , (16) cmp U(0), . . . , U(t − 1), t + 1) =f 00 (E1 (cmp(U(0), . . . , U(t − 1), t)), E2 (cmp(U(0), . . . , U(t − 1), t)), . . . , E2n−1 (cmp(U(0), . . . , U(t − 1), t)), E2n (cmp(U(0), . . . , U(t − 1), t)), U(t)). La funci´ on cmp es una funci´ on recursiva y simula la computaci´on de una ARN N en t instantes discretos de tiempo, luego la computaci´on de toda ARNN con pesos racionales enteros se puede expresar como una funci´ on recursiva. El valor de activaci´ on de la neurona i en el instante de tiempo t se puede calcular aplicando la funci´ on: 
 E2i−1 cmp U(0), . . . , U(t − 1), t  (17) xi (t) =
 , E2i cmp U(0), . . . , U(t − 1), t aplicando esta funci´ on a las neuronas de salida se obtienen los valores de salida de la ARN N en el instante de tiemp t. 6

La demostraci´ on se puede extender a Q = Q− ∪ {0} ∪ Q+ codificando cada racional x ∈ Q por la tripleta (Sx, N x, Dx), donde Sx ∈ {0, 1} determina el s´ımbolo del n´ umero racional (0 = +, 1 = −) y N x, Dx ∈ N representan el numerador y denominador respectivamente. El 0 se representa por (0, 0, 1). Adem´as, se debe tener en cuenta el signo en las sumatorias de la siguiente manera:   (0, N1 · D2 + D1 · N2 , D1 · D2 ) si S1 = S2 = 0,      (1, N · D + D · N , D · D ) si S1 = S2 = 1, 1 2 1 2 1 2  (S1 , N1 , D1 ) + (S2 , N2 , D2 ) = (0, |N1 · D2 − D1 · N2 |, D1 · D2 ) si S1 = 0, S2 = 1 y N1 · D2 > D1 · N2 ,    ´o S1 = 1, S2 = 0 y N1 · D2 < D1 · N2 ,    (1, |N · D − D · N |, D · D ) de otro modo. 1 2 1 2 1 2 (18) La definici´ on de computaci´ on presentada en [11] se enfoca en redes con un protocolo de entrada-salida en la que se tienen solo dos l´ıneas de entrada D(t) y V (t), D(t) es la entrada por donde se ingresan los datos a computar y V (t) sirve de l´ınea de validaci´ on de la entrada indicando cuando D(t) est´a activa o no. De forma similar, solo se tienen dos l´ıneas de salida, una para la salida de datos y otra para la validaci´on de la salida, denotadas por G(t) y H(t) respectivamente. Teniendo en cuenta este protocolo, para computar funciones parciales de la forma f : {0, 1}+ → {0, 1}+ , donde + representa la cerradura positiva de Kleene [1, 4], se tiene que las entradas a la ARNN para el valor w = w1 . . . wk a computar son: ( wt si 1 ≤ t ≤ k, D(t) = (19) 0 si t > k, ( V (t) =

1 0

si 1 ≤ t ≤ k, si t > k.

Se dice que la ARNN computa f (w) si existe r ∈ N tal que: ( f (w)[t−r+1] si r ≤ t ≤ r + |f (w)| − 1, donde |f (w)| = longitud de f (w), G(t) = 0 de otro modo,

(20)

(21)

y ( H(t) =

1 0

si r ≤ t ≤ r + |f (w)| − 1, de otro modo,

(22)

Si H(t) = 0 para todo t o H(t) = 1 para todo t ≥ r se dice que f (w) no est´a definida. Teniendo en cuenta esta definici´ on de computaci´on se puede redefinir la funci´on cmp (ec. 16) con base en las entradas D(t), V (t) y se puede minimizar la funci´on con base en la salida H(t) para obtener r y r + |f (w)| − 1, las salidas de la red ser´ an los valores de activaci´on de G(t) para los valores de cmp con r ≤ t ≤ r + |f (w)| − 1. Si la ARNN computa f (w) para todo w ∈ {0, 1}+ entonces r, r + |f (w)| − 1 y cmp ser´ an funciones recursivas totales, si f (w) no est´a defida para alg´ un w ∈ {0, 1}+ en la ARN N entonces r, r + |f (w)| − 1 y cmp ser´ an funciones recursivas parciales. Teorema 2. Para toda funci´ on recursiva existe una ARNN con pesos racionales que la computa. 7

La demostraci´ on a este teorema es presentada en [10], en esta demostraci´on se construyen las ARNNs con pesos racionales que computan las funciones b´asicas recursivas, luego se muestra como se pueden obtener los esquemas de composici´ on, recurrencia primitiva y minimizaci´on indicando como se deben interconectar las ARNNs que computan las funciones que se suponen recursivas en cada uno de los esquemas. En [11, 12] se hace una demostraci´ on alternativa de la equivalencia entre ARNNs con pesos racionales y m´aquinas de Turing, en esta demostraci´ on se prueba que toda p-stack machine [7] puede ser simulada por una ARNN con pesos racionales y como las p-stack machines con p ≥ 2 son equivalentes a una m´aquina de Turing [7] entonces las ARNNs con pesos racionales son equivalentes a las m´aquinas de Turing, en este trabajo no s´ olo se demuestra la equivalencia computacional entre los dos modelos sino tambi´en la equivalencia en complejidad algor´ıtmica.

4

Conclusiones

El resultado de restringir a los n´ umeros racionales los valores que pueden tomar los pesos en una ARNN con funci´ on de activaci´ on σ (ec. 3) es que las neuronas pueden tomar un n´ umero infinito contable de valores de activaci´ on (0 ≤ x ≤ 1 ∈ Q), esto hace que la ARNN pueda estar en un n´ umero finito, no acotado de ‘configuraciones’ debido a que el n´ umero de neuronas es finito, entendiendo por configuraci´ on una combinaci´ on de los valores de activaci´on de las neuronas. Esta es una situaci´on similar a la que se presenta en una m´ aquina de Turing, debido a que la cinta de la m´aquina tiene un n´ umero infinito contable de celdas, un n´ umero finito de estados y un alfabeto de entrada-salida finito; al entender una configuraci´ on en una m´ aquina de Turing como la combinaci´on del n´ umero de la celda que se est´a leyendo, el s´ımbolo que se est´ a leyendo y el estado de la m´ aquina tambi´en se tiene que la m´aquina de Turing puede est´ar en un n´ umero finito no acotado de configuraciones. El n´ umero de configuraciones que puede alcanzar una m´aquina tambi´en puede ser pensada como su capacidad de memoria, desde este punto de vista tanto las ARNNs con pesos racionales como las m´aquinas de Turing tienen una capacidad no acotada de memoria.

Agradecimientos Este art´ıculo fue financiado por la universidad EAFIT, bajo el proyecto de investigaci´on n´ umero 817424.

Referencias [1] Alfred V. Aho, Ravi Sethi y Jeffrey D. Ullman. “Compiladores: principios, t´ecnicas y herramientas”. Wilmington, Delaware: Addison-Wesley Iberoamericana (1990). [2] George Boolos y Richard Jeffrey. “Computability and logic”. Cambridge University Press, 3rd edici´ on (1989). [3] Xavier Caicedo. “Elementos de l´ ogica y calculabilidad”. Santaf´e de Bogot´a: Una empresa docente, U. de los Andes, 2a edici´ on (1990). [4] Decoroso Crespo. “Inform´ atica te´ orica. Primera parte”. Madrid: Departamento de Publicaciones de la Facultad de Inform´ atica, U. Politecnica de Madrid. (1983). 8

[5] Martin Davis. “Computability and unsolvability”. New York: Dover Publications, Inc. (1982). ´ l Go ´ mez Mar´ın y Andre ´s Sicard Ram´ırez. “Inform´atica te´orica: Elementos propede´ [6] Rau uticos”. Medell´ın: Fondo Editorial U. EAFIT (2001). [7] John Hopcroft y Jefferey Ullman. “Introducci´on a la teor´ıa de autom´atas, lenguajes y computaci´ on”. M´exico D.F.: Compa˜ nia Editorial Continental, S.A. (CECSA) (1997). [8] Stephen C. Kleene. “Introducci´ on a la metamatem´atica”. Colecci´on: Estructura y Funci´on. Madrid: Editorial Tecnos (1974). [9] Marvin L. Minsky. “Computation: finite and infinite machines”. Englewood Cliffs, N.J.: Prentice-Hall, Inc. (1967). [10] J. P. Neto, H. T. Siegelmann, J. F. Costa y C. P. Araujo. Turing universality of neural nets (revisited). Publicado en: Lecture notes in Computer Science: computer aided system theory. Edited by F. Pichler and R. Moreno Diaz. Eprint: www.cs.math.ist.utl.pt/cgi-bin/uncgi/bib2html.tcl? author=fgc (1977). [11] Hava T. Siegelmann. “Neural networks and analog computation. Beyond the Turing limit”. Progress in Theorical Computer Science. Boston: Birkh¨auser (1999). [12] Hava T. Siegelmann y Eduardo D. Sontag. On computational power of neural networks. Journal of Computer and System Sciences 50(1), 132–150 (1995).

9