MODELOS FÍSICOS EN COMPUTACIÓN AVANZADA - dc.fi… · 10 CONCEPTOS FÍSICOS E INFORMACIÓN ... • Sobre algunos de los bits no tenemos conocimiento previo

Modelos Físicos en Computación Avanzada

1

MODELOS FÍSICOS EN COMPUTACIÓN AVANZADA

• Física de la Información• Termodinámica de la Computación• Computación Reversible• Energía y Velocidad de la Computación• El Computador General Reversible• El Computador de la Bola de Billar• Fundamentos de Computación Cuántica


2

CONCEPTOS FÍSICOS E INFORMACIÓN

• Física de la Información–Hablemos de Energía… ¿Cuánta hace falta para llevar a cabo una computación? ¿Es éste un tema académico?–Es claro que a mayor velocidad de computación hay un consumo mayor de energía: ∆v → ∆E … que se disipa en forma de calor.–Pero la pregunta es otra… ¿Cuál es la mínima energía necesaria para llevar a cabo una computación? → Ahora la cuestión es estríctamente académica.–Shannon pretendía resolver el problema de la transmisión de mensajes a través de cables reales → interferencias con el mundo físico →posibilidad de abordar el problema de la computación desde la física.


3


• Un modelo sencillo de mensaje enviado

–Supóngase un número no determinado de cajas pegadas entre si. –En cada caja hay una partícula.–Cada partícula puede estar:

•A la derecha de la caja•A la izquierda de la caja

–Si una partícula está a la derecha es un bit 1–Si una partícula está a la izquierda es un bit 0


4


. . . . . .1 1 100 0

• La Física de los gases ayuda a entender este modelo de información.

• Gas. N partículas. Volumen V1. Las partículas no interaccionan → El tamaño de las partículas es muy pequeño si lo comparamos con las distancias a que se encuentran unas de otras. Cada partícula es esencialmente libre (cierto si P↓)

• ¿Qué tiene esto que ver con la información?


5


• Sometemos el gas anterior a una compresión isoterma:

• V1 → V2 T = cte

•¿Cuánto trabajo se necesita para comprimir el gas?

V1 V2

Baño a Temperatura Constante


6


• ∂W = F ∂x

• Si p = presión, y A = sección del pistón, dado que F = p A → ∂W = p A ∂x

• Pero A ∂x = ∂V → ∂W = p ∂V

• Pero además, según la teoría cinética de los gases: p V = NkT

• N = Número de partículas del gas

• k = cte de Boltzmann

• T = Temperatura constante

• p = NkT/V → ∂W = NkT ∂V/V → W = ∫V1 → V2 [NkT(∂V/V)] = NkT Ln(V2/V1)

• Como V2 < V1 → W < 0 … El trabajo realizado sobre un gas lo pierde el sistema


7


• ¿Dónde ha ido a parar W? … Recordamos que T = cte

• ¿Cómo se puede hacer esto? … Realizando la compresión a velocidad infinitamente lenta → Asegurando que el sistema está siempre en equilibrio térmico

• Cambio de estado de un gas de V1 a V2

• U = Energía Interna = ∑Ui = cte

• Magnitudes termodinámicas que definen los cambios de estado:

• U = Energía interna

• F = Energía libre

• S = Entropía


8


• F = U - TS

• Si T = cte → ∂F = ∂U - T ∂S

• Como ∂U = 0 → ∂F = -T ∂S

• Pero ∂F es la energía absorbida por el baño durante el proceso (perdida)

• Por lo que: ∂F = -∂W = - NkT(∂V/V) = -T ∂S → ∂S = Nk (∂V/V)

• ∆S = NkLn(V2/V1) → expresión del proceso reversible

• ∆S ≥ NkLn(V2/V1) → expresión del proceso irreversible (2º ppio TDQ)


9


• Sea ahora una única partícula: N = 1

• T, p, V, F, S, … tienen sentido considerando tiempos largos y promediando

• Consideremos además que V2 = (V1)/2… en este caso:

• ∆F = - kT Ln(V1/2V1) = kT Ln(2)

•∆S = k Ln(V1/2V1) = - k Ln(2)

V1 V2 = V1/2


10


• El estado físico de la partícula antes y después de la compresión es el mismo

• Sin embargo hay cambios en F y S, como acabamos de comprobar

• ¿Qué ha pasado?

• Nuestro “conocimiento” de las posiciones posibles de la partícula ha cambiado

• V1 es mucho mayor que V2, por lo tanto en V2 hay menos lugares donde la partícula puede estar

• La entropía, en este caso, está relacionada directamente con la probabilidad de que el gas se encuentre en la configuración en la que se encuentra. Configuración = orden concreto para cada partícula

• Si w es la probabilidad de una configuración → S ≈ k Ln w

• Cuanto menos sabemos de la configuración de un gas en más estados puede estar, mayor es w, y mayor es S → Cuanta menos información tenemos sobre un estado, mayor es su entropía: ∂S = k (∂w/w) ≥ 0


11


. . . . . .1 1 100 0

• Por definición, la información de un mensaje será proporcional a la energía libre para reiniciar la cinta a cero → comprimir cada celda de la cinta para llevar a su partícula a la posición cero


12


• Dado un mensaje típico:

• Sobre algunos de los bits no tenemos conocimiento previo

• Sobre algunos de los bits si tenemos conocimiento previo

• Casos:

• Si el bit es cero no hay que hacer nada para reiniciar → ∆F = 0

• Si el bit es uno hay que hacer trabajo para desplazarlo a cero → ∆F ≠ 0

• Peculiaridad: ¿No podría hacerse lo mismo para reiniciar a uno? → simetría

• Esta simetría produce el mismo resultado sólo si el mensaje contiene el mismo número de ceros que de unos.

• Sutileza: Sólo gastamos energía libre si no sabemos dónde está la partícula


13


• Si sabemos la posición de la partícula no gastamos energía en reiniciar → La información del mensaje está contenida en los bits que desconocemos

• Si I = Cantidad de Información de un mensaje:

• I α ∆F(x, y,…, t → 0, 0,…, 0)

• I α ∆F(x, y,…, t → 1, 1,…, 1)

• ∆F(x, y,…, t → 0, 0,…, 0) ≠ ∆F(x, y,…, t → 1, 1,…, 1) -en general-

• ∆F(x, y,…, t → 0, 0,…, 0) = ∆F(x, y,…, t → 1, 1,…, 1) - si nº0s = nº1s-

• Pero la cantidad de información del mensaje es la misma, independientemente de cómo reiniciemos → Inconsistencia

• Solución: La información del mensaje está en lo que desconocemos


14


• ¿Por qué la energía necesaria para (1 → 0) = (0 → 0) = 0?

•Abstracción:

• Cajas ideales → No consideramos aspectos mecánicos

• La energía se refiere sólo a la del contenido del mensaje

• Esta energía está relacionada con lo que sabemos sobre el mensaje

• El contenido del mensaje depende de las posiciones de las partículas


15


• Otra forma de verlo…

• Como el trabajo sobre un lado se recupera por el otro, el saldo es cero, si el proceso se efectúa suficientemente despacio

• El único factor que interviene en F es S, que sólo varía si no sabemos en qué posición está la partícula


16


• ALGUNAS CONSECUENCIAS “PRÁCTICAS”: El Demonio de Maxwell y la Termodinámica de la Medida


17


• El demonio de Maxwell parece violar el 2º principio de la termodinámica

• Conjetura:

• En el proceso de buscar partículas de algún tipo, y dejarlas pasar por la rendija, se debe generar alguna entropía

• Esta entropía puede surgir como resultado de la medida del demonio de la posición y velocidad de la partícula (principio de indeterminación)

• El demonio de Maxwell puede realizar sus medidas con un coste energético nulo, siempre y cuando siga ciertas reglas para grabar y borrar la información que vaya obteniendo (Bennet)

• Íntima relación con la computación reversible, la energía de la computación, la relación entre información y entropía, y el concepto de medida


18


• Antes de medir el demonio está en un estado estándar S

• El estado S es un estado de incertidumbre (su ignorancia es total)

• Cuando mide la dirección del movimiento de una partícula, el estado del demonio cambia (se informa):

• S → L (la partícula se mueve hacia la izquierda)

• S → R (la partícula se mueve hacia la derecha)

• Sobreescritura de S con L o R

• El proceso se lleva a cabo sin coste energético alguno (Bennet)

• El coste energético se produce cuando el demonio debe prepararse para otra observación: (L o R) → S

• En un proceso computacional la entropía no se genera en la realización de la medida, sino al borrar la información


19

TEORÍA DE LA INFORMACIÓN

• N posibilidades equiprobables a priori, que puedo expresar con n símbolos

• Si N es grande, Info debe aumentar para pasar de N a 1• Definición: Cantidad de Información I=K Ln N• Contexto:

– La información es propiedad aditiva– Para 2 sistemas independientes con N1 y N2 sucesos equiprobables:– N = N1 · N2

• I = K ln (N1 N2) = K ln N1 + K ln N2 = I1 + I2• K está determinada por la unidad de información• Si yo tengo n símbolos, ¿cuántos estados equiproblables puedo

representar?

NInfo Info Info Info

“algo concreto”


20


• N = 2n -> si n=3, a, b,c →¬ a, ¬ b, ¬ c ¬ a, b, c¬ a, ¬ b, c a, ¬ b, c¬ a, b, ¬ c a, b, ¬ ca, ¬ b, ¬ c a, b, c

• I = K ln N = K ln 2n = K n ln 2• I = n (K ln 2)

• Si yo quiero que I=n -> K ln 2 = 1 -> K = 1 / (ln 2)• Entonces I= ln N/ln2 = log2 (N) = n (BIT)

• Ln(N)/Ln(2) = a → Ln(N) = a Ln(2) → N = 2∧a → Log2(N) = a


21

• Informacion E1 = K ln N1• Información E2 = K ln N2• ∆S = S2 - S1 = K ln (N2/N1) = K ln N2 - K ln N1• ∆ Información: I2 - I1 pero I2 = 0 -> - I1• ∆ Entropía: S2 - S1 = ∆S• ∆I = ∆S -> - I1 = S2 -S1 = ∆S

Estado 1 Estado 2



22

RNAS, TERMODINÁMICA ESTADÍSTICA Y APRENDIZAJE

• Entrenamiento neuronal de una red– Proceso que modifica los pesos sinápticos de forma que, al final, la

aplicación de una serie de entradas produce un conjunto de salidas esperado

i jWji

Si Sj


23

TEORÍA DE CONTROL

• Problemas – Caracterizar el sistema– Diseñar un algoritmo de control adecuado– Lograr la estabilidad del sistema ante cambios en la entrada

Control

Medidor

Sistemai e o

v

t

v1er orden

t

2º orden


24

MÉTODOS GENÉRICOS DE ENTRENAMIENTO• Determinístico:

– Procedimiento de ajuste de los pesos de la red, paso a paso, que considera:• Los correspondientes valores de los pesos en un momento dado• Los valores de las entradas• Los correspondientes valores de las salidas• Los valores deseados en las salidas• Ejemplo: el perceptrón

• Estadístico: – Procedimiento que consisten en efectuar cambios pseudoaleatorios en los pesos

sinápticos de la red y conservar aquellos cambios que resulten de una mejor estabilidad del sistemas.

• Aplicar un conjunto de entradas y encontrar las salidas correspondientes• Calcular el error obtenido: Función objetivo que hay que minimizar• Seleccionar un peso cualquiera y efectuar un cambio• Si el sistema se vuelve más estable acepta el cambio, de lo contrario

olvidalo• Repetir el proceso hasta minimizar la función objetivo


25

FUNCIÓN DE ENTRENAMIENTO NEURONAL DE BOLTZMANN (ALGORITMO)

• T ≡ Temperatura artificial del sistema• Iníciese el proceso con un valor alto de T• Aplíquese un conjunto de entradas a la red y calcúlense las salidas y la

función objetivo• Efectúese un cambio arbitrario en un peso sináptico y recalcúlese la salida

de la red y el correspondiente cambio en la función objetivo• Si la función objetivo mejora, consérvese el cambio efectuado sobre el

peso sináptico• Si la función objetivo empeora, calcúlese la probabilidad de aceptar el

cambio, de acuerdo con la ley de distribución de Boltzmann: – P(c) = exp (- c / kt) = e-c / kt

– P(c) es la probabilidad de un cambio “c” en la función objetivo– K ≡ constante de Boltzmann– T ≡ Temperatura artificial de la red


26

FUNCIÓN DE ENTRENAMIENTO NEURONAL DE BOLTZMANN (ALGORITMO)

• Seleccionar un número “r” al azar, de una distribución uniforme entre 0 y 1

• Si P(c) > r -> conserva el cambio• Si P(c) <= r -> descarta el cambio

• OBJETIVO: Permitir que el sistema escape de los mínimos locales.

f.o.

ba


27

FORMALIZACIÓN DE CONCEPTOS

• La ley de distribución de Boltzmann es la base del aprendizaje estocástico o desordenado

• Una neurona es una estructura recurrente que opera de manera binaria “on = +1”, “off = -1”

• En el contexto de un sistema neuronal, una máquina de Boltzmann es una entidad caracterizada por una función de energía E, cuyo valor depende de los estados individuales de cada una de las neuronas de la RNA

• donde:– Si ≡ estado de la neurona “i”– Si ≡ estado de la neurona “j”– Wji ≡ peso sináptico de la conexión i => j

– Analogía con la expresión clásica de la energía cinética E = 1/2 mv2

∑∑≠

−=

jii j

ijji SSWE21


28

FORMALIZACIÓN DE CONCEPTOS

• Una sinápsis excitadora contribuye a disminuir la energía de la RNA• Una sinápsis inhibidora contribuye a aumentar la energía de la red• Consideremos la siguiente conexión neuronal

• Un par de neuronas conectadas están en sintonía si ambas están en el mismo estado (SiSj > 0)

• Un par de neuronas conectadas están en disonancia si sus estadosindividuales son diferentes (SiSj < 0)

j iWji

Sj(+1 ó -1)

Si(+1 ó -1)


29

FORMALIZACIÓN DE CONCEPTOS• Nivel de activación elemental de un par de neuronas conectadas

• αji = WjiSjSi

• αji es una excitación neta cuando:– El par de neuronas conectadas está en sintonía y la sinápsis es

excitatoria– El par de neuronas conectadas está en disonancia y la sinápsis es

inhibidora

• αji es una inhibición neta cuando:– El par de neuronas conectadas está en sintonía y la sinápsis es

inhibitoria– El par de neuronas conectadas está en disonancia y la sinápsis es

excitadora


30

• Sea una red en fase de aprendizaje– Seleccionar arbitrariamente una neurona j– Invertir el estado de la neurona j: Sj => -Sj– Envaluar la probabilidad de cambio de la red conectada por el cambio de estado de la neurona j

de acuerdo con:

– donde• ∆Ej ≡ variación energética asociada al cambio de estado• T ≡ temperatura de la RNA

– repetir hasta alcanzar un estado de equilibrio térmico, es decir:• Una nueva modificación (iteración) no produce una modificación en la probabilidad de

cambio de la RNA • El sistema no mejora• La probabilidad de cambio está minimizada

W(Sj → −Sj ) =1

1 + exp−∆Ej

T⎛

⎝ ⎜

⎞

⎠ ⎟

MÁQUINA DE BOLTZMANN Y APRENDIZAJE DE RNAS


31

MÁQUINA DE BOLTZMANN Y APRENDIZAJE DE RNAS

• Preguntas:

– ¿Qué es la energía de una RNA?– ¿Qué es la temperatura de una RNA?– ¿Qué es una situación de equilibrio térmico?– ¿Qué quiere decir “minimizar la probabilidad de cambio”?– ¿Podemos cuantificar la magnitud de una variación estocástica?– ¿Cómo evoluciona “siempre” cualquier sistema físico?

• Mejor: ¿Cómo tiende a evolucionar?– En definitiva ... ¿qué es el aprendizaje?– ¿Cuáles son los límites del aprendizaje?


32

TERMODINÁMICA

• La teoría cinética de los gases establece que: la temperatura es una medida de la energía cinética de las partículas de un gas

• Dos sistemas están en equilibrio térmico cuando tienen la misma temperatura

• Como cada partícula de un gas se mueve con una velocidad propia, cada una está en un nivel energético diferente

• A nivel macroscópico, la energía del sistema es el valor medio de las energías individuales

• La temperatura es, pues, un valor medio de energía


33

TERMODINÁMICA

• Interacción térmica. A tiene menos grados de libertad que A’ (o menos partículas)• ¿Cuál es la probabilidad Pα de que el sistema A esté en un estado energético

particular Eα?

• Función de distribución de probabilidad– K = cte de Boltzmann– T = Temperatura absoluta del sistema– Z = cte, independiente de α

A A’

⎟⎠⎞

⎜⎝⎛−=

KTE

zP α

α exp1


34

TERMODINÁMICA

• Dado que: Pα = 1→α∑ Pα =

1z

exp −Eα

KT⎛ ⎝ ⎜

⎞ ⎠ ⎟

α∑ →

α∑

→ 1 =1z

exp −Eα

KT⎛ ⎝ ⎜

⎞ ⎠ ⎟

α∑ → z = exp −

Eα

KT⎛ ⎝ ⎜

⎞ ⎠ ⎟

α∑ →

∑ ⎟⎠⎞

⎜⎝⎛−

⎟⎠⎞

⎜⎝⎛−

=⇒

α

α

α

α

KTE

KTE

Pexp

exp

, y para otro estado energético cualquiera:

∑ ⎟⎟⎠

⎞⎜⎜⎝

⎛−

⎟⎟⎠

⎞⎜⎜⎝

⎛−

=⇒

β

β

β

β

KTE

KTE

Pexp

exp


35

TERMODINÁMICA

• Si el sistema está en equilibrio térmico => T = cte

• ya que la suma se extiende a todos los posibles estados de energía

• Recordando que: (aprendizaje neuronal)– c = ∆Eα

– T = parámetro ajustable, sin ningún sentido físico– K = constante parecida a la de Boltzmann (dimensionalidad)

( )⎭⎬⎫

⎩⎨⎧ ∆

−=⎭⎬⎫

⎩⎨⎧ −

−=KTE

KTEE

PP αβα

β

α expexp

∑∑ ⎟⎟⎠

⎞⎜⎜⎝

⎛−=⎟

⎠⎞

⎜⎝⎛−

β

β

α

α

KTE

KTE expexp

KTc

ecP −=)(


36

TERMODINÁMICA

• Usando el resultado obtenido en la expresión de la máquina de Boltzmann:

• Evidentemente, la probabilidad de un cambio es un concepto probabilístico

( )⎟⎟⎠

⎞⎜⎜⎝

⎛+

=→

β

α

PP

SSW ij

1

1


37

CONSIDERACIONES DINÁMICAS SOBRE LA ENERGÍA

• Definimos la energía libre de un sistema termodinámico como:

• Consideramos los dos sistemas anteriores A y A’, que están intercambiando energía en forma de calor. Por la segunda ley de la termodinámica sabemos que:

• Donde– S es la entropía del sistema– es la energía media del sistema, calculada sobre todos los

estados energéticos posibles

∑ ⎟⎠⎞

⎜⎝⎛−−=−=

α

α

KTEKTzKTF explnln

TE

KTEK

TEzKS +⎟

⎠⎞

⎜⎝⎛−=+= ∑

α

αexplnln

E

∑=α

αα EP


38


• Claramente:

• Importante expresión que relaciona macroscópicamente la energía media de un sistema con la entropía (1º y 2º principio de la termodinámica).– Un sistema tiende espontáneamente al mínimo de energía– Un sistema tiende espontáneamente al máximo de entropía– Un sistema debe evolucionar hacia el mínimo de F

→−=→−=→+= FETSFzKTEzKTTS ln pero ln

TSEF −=


39


• Recordemos además que:

• ¿Qué tipo de variable es S?• ¿Cuál es su naturaleza?

⎟⎠⎞

⎜⎝⎛−=→⎟

⎠⎞

⎜⎝⎛−=

KTE

zP

KTE

Pz α

αα

α

exp1exp1

∑=α

αα EPE

TEzKS += ln


40


• Calculando un poco:

• Por otra parte

• La entropía es una magnitud estrictamente probabilística

)ln(1ln1ln1ln)ln( ααα

α

α

PzKT

EKTE

ze

zP KT

E

−⎟⎠⎞

⎜⎝⎛=→−⎟

⎠⎞

⎜⎝⎛=

⎭⎬⎫

⎩⎨⎧

=−

∑∑ →+=→+=+=α

αα

ααα KT

EPzksEP

TzK

TEzKS ln1lnln

( ) ∑∑∑∑ −⎟⎠⎞

⎜⎝⎛=−⎟

⎠⎞

⎜⎝⎛+=

⎭⎬⎫

⎩⎨⎧

−⎟⎠⎞

⎜⎝⎛+→

αααα

αα

αα

ααα )ln(ln)ln(1lnlnln1lnln PP

zzPPP

zzP

zPz

0,0ln enteInmediatam ≠>⇔−=⇒ ∑ zzPPKSα

αα


41


• Además, z no puede ser cero

• Pero... – ¿podemos predecir el cambio producido por un proceso

estocástico?– ¿Cómo cuantificamos la magnitud de una variación

estocástica?– => Ley del caos o del comportamiento estadístico

⎪⎩

⎪⎨

⎧

≥≥=∀≥

00

0

Tctek

E αα

∞=→∞=→=→∀=⇔=−

α

α

α

α

α Eee

ez KTE

KTE

KTE

0100


42

LEY DEL CAOS O DEL COMPORTAMIENTO ESTADÍSTICO

• Después de un número dado de pasos, ¿a que distancia está el borrachín del farol?

• R = distancia del borrachín al farol después de N pasos zigzagueantes

• Teorema de Pitágoras: R2=(x1+x2+...+xn)2+(y1+y2+...+yn)2

• Si la farola tiene de coordenadas (0,0), en un instante “i” la posición del borrachín es (xi, yi), con xi, yi <> 0

y

x


43


• Aritmética– A=(x1+x2+...+xn)2 = x1

2+ x1 x2+...+x22+ x2+x1+...+xn

2

– B=(y1+y2+...+yn)2 = y12+ y1 y2+...+y2

2+ y2+y1+...+yn2

• Estadística: – Si N es grande, los productos mixtos dado que el proceso es

estocástico, tienen la misma probabilidad de ser positivos que negativos,

– además la longitud del paso del borrachín es más o menos constante (en todo caso, si N es grande, daría igual),

– => todos los productos mixtos tienden a anularse =>– A= x1

2+x22+...+xn

2 = – B= y1

2+y22+...+yn

2 =

– Por lo tanto:

2xN

2yN

( ) ( ) 2122222 yxNyxNR +→+=


44


• Pero, ¿Cuál es la proyección media de los pasos del borrachín sobre los ejes correspondientes?

• Dado que el sistema es ortogonal, y como el movimiento es estocástico, los valores medios son precisamente 45º en cualquier dirección.

• Proyección sobre el eje x• Proyección sobre el eje y

• El paso normal de una persona es 70 cms - 80 cms =>

• La distancia a la que se encuentra el borrachín de la farola, en un proceso estocástico, es independiente de la dirección: sólo depende del número de pasos (interacciones)

RRRx 22cos == α

RRRy 22sen == α

( ) NRyx ≈≈+ y ,12122


45

APRENDIZAJE Y CLASIFICACIÓN

• Clasificar => minimizar la entropía de un sistema, ya que la probabilidad de la situación A es mucho mayor que la probabilidad de la situación B

α

β

A B


46

APRENDIZAJE Y CLASIFICACIÓN

• Sea una habitación de 5m x 4m x 2.5m = 50 m3 = 5·107 cm3

• A T=“normal”, esta habitación contiene 5·104 g de aire, lo que significa que contiene unas 1027 moléculas de aire.

• ¿Cuál es la probabilidad de que espontáneamente, todas estas moléculas se sitúen en la parte de arriba de la habitación, haciendo que - indefectiblemente - nos muramos asfixiados?

nula no1021 26

27

10·310

→=⎟⎠⎞

⎜⎝⎛= −

αP

tα = 10299999999999999999999999998

1710 Universodel Edad =


47

LÍMITE TEÓRICO DEL APRENDIZAJE

• El aprendizaje espontáneo está casi prohibido por la termodinámica... Pero ¿cuál es el límite teórico del aprendizaje?

• La respuesta está en la mecánica cuántica:– Indeterminaciones cuánticas:

• ∆p· ∆s ≈ 10-34

• ∆E· ∆t ≈ 10-34

• Un clasificador simple:h

l


48

LA MÁQUINA DE BENNET

• HIPÓTESIS: La cinta de un mensaje puede ser utilizada como “combustible”

• LA INFORMACIÓN DE LA CINTA PUEDE RELACIONARSE CON EL PODER CALORÍFICO

• EL PODER CALORÍFICO ES LA CANTIDAD DE ENERGÍA QUE PODEMOS OBTENER DE LA CINTA

Baño Térmico: T = cte

0

1


49

LA MÁQUINA DE BENNET

• ESTADO INICIAL: TODOS LOS BITS A CERO (Partículas en su posición inicial)

• PISTÓN: Cada vez que llega una nueva celda se mueve hasta la mitad de la posición de la caja

• El baño térmico calienta la celda → La partícula empuja isotérmicamente al pistón hacia fuera → Proceso inverso al de compresión isoterma

• Sobre el pistón se efectúa un trabajo que pude ser empleado para mover el motor

• Si hay “n” bits → W = nKT Ln(2) = F

• Consecuencia: La cinta saliente ha sido aleatorizada → No sabemos dónde está la partícula → Para saberlo tenemos que efectuar una medida


50

COMPUTACIÓN REVERSIBLE

• CUALQUIER PASO COMPUTACIONAL… ¿Requiere energía?

• SUPOSICIÓN: Se requiere una cantidadmínima de energía para cada paso lógico que realiza una máquina

Estado Lógico Estado Físico

DISPOSITIVO


51


• SIGUIENDO CON LA SUPOSICIÓN:

– Siempre que hay un cambio de estado lógico del dispositivo, desde un estado inicial desconocido hasta otro determinado, hay una compresión del estado de fases, de 2 a 1 → Se divide por la mitad el volumen del espacio de fases.

– El mínimo teórico de energía libre necesario es: Fmin = kT Ln(2)

– Si consideramos la fiabilidad del dispositivo e introducimos la probabilidad “q” de un error, entonces: Fmin = kT Ln(q)

• … Pero esto no tiene por qué ser cierto, de hecho:

– Fmin/paso < kT Ln(2)

– Fmin/paso < kT Ln(q)

– Fmin/paso < … cualquier mínimo que se proponga


52


• CONDICIONES:

– LA COMPUTACIÓN DEBE REALIZARSE MUY DESPACIO

– IDEALMENTE UNA COMPUTACIÓN PUEDE REALIZARSE SIN PÉRDIDA MÍNIMA DE ENERGÍA

– ANALOGÍA CON LAS MÁQUINAS DE CARNOT

– ELLO NOS LLEVA A LA COMPUTACIÓN REVERSIBLE

– IMPORTANTE CUANDO SEAMOS CAPACES DE DISEÑAR ORDENADORES DE TAMAÑO “ATÓMICO”

W = 0


53


PROCESADOR

INPUT OUTPUT

Línea (IN) → Línea (OUT) -una y sólo una-

Info(OUT) ≡ Info (IN)


54


• PROPIEDADES:– (1) SI CONOCEMOS LA ENTRADA PODEMOS CALCULAR LA

SALIDA– (2) LA COMPUTACIÓN ANTERIOR ES “REVERSIBLE”

A

BCAND

- 2 ENTRADAS, 1 SALIDA

- 3 ESTADOS POSIBLES A LA ENTRADA QUE PRODUCEN SALIDA CERO

- PÉRDIDA DE INFORMACIÓN

- LA PUERTA “AND” ES IRREVERSIBLE


55


Puerta NOT: Claramente reversible: NOT (NOT A) = APuerta CN o “Controlled NOT”2 entradas -A y B- y 2 salidas –A’ y B’-Línea superior = línea de control tal que A = A’ siempreLínea inferior = operación NOT controlada por la línea superior, de forma que:Si A = A’ = 0 : B’ = BSi A = A’ = 1 : B’ = NOT B

A A’

B B’


56


• TABLA DE VERDAD DE LA PUERTA C-N

0111110110100000

B’A’BA


57


• La salida B’ es la salida que tendríamos a partir de una puerta XOR alimentada con A y B

• El dispositivo no es el mismo puesto que la puerta C-N produce realmente dos salidas

• Esta puerta es perfectamente reversible ya que, una vez conocida la salida, siempre podemos reproducir la entrada

110111011101101010000000

B’’A’’B’A’BA


58


PUERTA C-N-NLas dos líneas superiores son las líneas de control: A = A’ y B = B’La línea inferior es un NOT controlado por las dos líneas superiores:C’ = NOT C Si A = 1 y B = 1

A A’

B B’

C C’


59


TABLA DE VERDAD DE LA PUERTA C-N-N

011111

111011

101101

110110

001001

010010

100100

000000

C’B’A’CBA


60


REVERSIBILIDAD DE LA PUERTA C-N-N

111011111

011111011

101101101

110110110

001001001

010010010

100100100

000000000

C’’B’’A’’C’B’A’CBA


61


La puerta CNN es por sí misma un conjunto completo de operadoresAND se construye fijando C = 0 y alimentando la puerta con A y B según:

111011

001001

010010

000000

C’B’A’CBA


62


La puerta CNN es por sí misma un conjunto completo de operadoresNAND se construye fijando C = 1 y alimentando la puerta con A y B:

011111

101101

110110

100100

C’B’A’CBA


63


La puerta CNN es por sí misma un conjunto completo de operadoresXOR se construye fijando A ó B = 1 :

011111

101101

111011

001001

C’B’A’CBA


64


• Análisis:– La puerta NOT acepta 1 entrada y devuelve 1 salida– La puerta CN acepta 2 entradas y devuelve 2 salidas– La puerta CNN acepta 3 entradas y devuelve 3 salidas– Las tres puertas son reversibles– Para construir una puerta reversible:

• ¿Es imprescindible que el número de entradas coincida con el número de salidas?

• Pregunta de discusión y debate:– ¿Por qué podemos decir –y por qué esto es importante-

que una computación reversible se efectúa con coste cero de energía?


65

ENERGÍA Y VELOCIDAD DE UNA COMPUTACIÓN

• El coste computacional cero requiere que la computación se haga infinitamente despacio

• Restricción:– Queremos que nuestra computación se realice en un

tiempo finito• Pregunta:

– ¿Cuánta energía libre se necesita para lograr una computación en un tiempo finito?

• Punto de partida:)(νkTLn

pasoF

=


66


• Dispositivo en un estado particular con una energía asociada• El sistema puede avanzar o retroceder a un nuevo estado• Cada proceso de avance o retroceso implica una computación• En términos de diagrama de niveles de energía:

E1

A

E2

Avance


67


• La mecánica estadística predice que la probabilidad de una transición entre dos estados de energía Ea y Eb es:

• C es un factor relacionado con las fluctuaciones térmicas

⎟⎠⎞

⎜⎝⎛ ∂

−=→kTECP EbEa exp


68


• En términos absolutos, para calcular las tasas de avance y retroceso hay que incluir un nuevo factor –X- que depende de ciertas propiedades moleculares, de forma que:

⎥⎦⎤

⎢⎣⎡ −−=

⎥⎦⎤

⎢⎣⎡ −−=

kTEACXretrocesoTasa

kTEACXavanceTasa

)(exp)(

)(exp)(

1

1


69


• Como C y X no nos interesan demasiado en nuestra discusión, y puesto que lo que sí nos interesa es averiguar cómo evoluciona nuestra computación, podemos expresar lo anterior como una relación según la expresión:

• Si recordamos ahora la expresión general:

⎥⎦⎤

⎢⎣⎡ −

=kT

EEretrocesoTasaavanceTasa 21exp

)()(

)(νkTLnpasoF

=


70


2121

)()(

)()( EE

retrocesoTasaavanceTasakTLn

kTEE

retrocesoTasaavanceTasaLn −=⎥

⎦

⎤⎢⎣

⎡→

−=⎥

⎦

⎤⎢⎣

⎡

21

)()(

EEpasoF

retrocesoTasaavanceTasa

−=

=ν


71


• Supongamos que durante un proceso computacional nos encontramos con n1 estados energéticamente equivalentes entre sí, desde los que podemos acceder en un solo paso a n2 nuevos estados –también energéticamente equivalentes entre sí-, con las siguientes restricciones:

2121 :)()( nnnEnE <>

1

2

)()(

nn

retrocesoTasaavanceTasa

==ν


72


• Necesitamos ahora volver a un viejo concepto ya casi olvidado, la entropía S = k Ln ω en la cual ω es la probabilidad de una configuración. Por lo tanto, desarrollando la expresión definida para ν, obtenemos que:

• Es evidente que, de acuerdo con esta expresión, el gasto de energía libre en cada paso computacional equivale a la entropía generada en ese paso multiplicada por la temperatura.

TSSnLnnLnkTkTLnpasoF )()()([)( 1212 −=−== ν


73

Conclusiones• La tecnología de la computación es una disciplina de carácter práctico• La lógica es … eso, lógica• Ambas, desde la perspectiva de las ciencias de la computación, se

utilizan para construir ordenadores• El comportamiento de los ordenadores puede ser explicado desde la

física• Hasta ahora hemos hablado de ordenadores clásicos, por ello hemos

empleado la física clásica• ¿Qué pasará cuando el tamaño de los ordenadores sea tan pequeño que

las leyes de la física de lo muy pequeño tengan una importancia grande?

• ¿Cuáles serán las limitaciones que la física cuántica impondrá a la computación?

• Este último objetivo será tratado en la segunda parte de este curso

Documents

MODELOS FÍSICOS EN COMPUTACIÓN AVANZADA - dc.fi… · 10 CONCEPTOS FÍSICOS E INFORMACIÓN ... • Sobre algunos de los bits no tenemos conocimiento previo