Cálculos infinitos en tiempo finito

Este es probablemente un pensamiento tonto, pero supongamos que tenemos una computadora que está programada para realizar una secuencia infinita de cálculos y supongamos que el cálculo de tarda segundos en completarse. Entonces esta computadora puede hacer un número infinito de cálculos en un tiempo finito. $i^\text{th}$ $1/2^i$

¿Por qué es esto imposible? ¿Existe un límite inferior sobre cuánto tiempo lleva llevar a cabo un cálculo no trivial?

computability computation-models dsaxton
fuente

Concepto relacionado, cálculos infinitos utilizando energía finita: la inteligencia eterna de Dyson .

Peter

Respuestas:

Este "tipo" de computadora se conoce como Zeno Machine . Su modelo computacional cae en una categoría llamada hipercomputación . Los modelos hipercomputacionales son abstracciones matemáticas, y debido a las formas en que se definen para trabajar, no son físicamente posibles.

Tome su máquina Zeno por ejemplo. Si imaginamos que la máquina Zeno es una máquina calculadora de cualquier tipo, no importa si usa un ábaco o un circuito integrado. Digamos que los datos del programa utilizados por la máquina se le suministran mediante una cinta de símbolos infinitamente larga (como una máquina de Turing).

Por supuesto, sabemos por matemáticas que:

$\frac{1}{2}+\frac{1}{4}+\frac{1}{8}... = \sum_{n=1}^{\infty}(\frac{1}{2})^n$

que decimos es igual a . Por lo tanto, el cálculo debe completarse en 1 segundo porque la suma converge absolutamente. $1$

Pero, por supuesto, esta convergencia depende de que vaya al (y alcance) el infinito. En el sentido físico, esto significa que a medida que el tiempo requerido para cada cálculo se reduce, el "cabezal de lectura" de la máquina calculadora tendrá que desplazarse cada vez más rápido por los símbolos de la cinta. En algún momento, esta velocidad excederá la velocidad de la luz. $n$

Entonces, respondiendo a su segunda pregunta, el límite absoluto más bajo posible en un cálculo probablemente estaría en el orden del tiempo de Planck, dada la velocidad de la luz como el principal factor limitante en los modelos de cómputo teóricos, pero físicamente plausibles.

Teoría de todo
fuente

Hay también los requerimientos de energía para cada operación, volteando un poco los veces requiere varios órdenes de magnitud más energía que está en nuestro sol

2^{256}

$2^{256}$

monstruo de trinquete

¿Este programa: 10: GOTO 10 termina en la máquina Zeno?

Cano64

En términos más simples, las matemáticas presuponen que un "cálculo" tiene un alcance infinitamente divisible. Sin embargo, ese no es el caso con ninguna máquina física, ya que eventualmente llega a un punto en el que ha alcanzado la unidad de trabajo más pequeña que la máquina puede realizar. No es posible continuar subdividiendo el cálculo después de ese punto, aunque las matemáticas lo permitan. En otras palabras, la máquina falla mucho antes de que realmente te acerques al final de la serie infinita de cálculos. En algún momento, el tiempo por cálculo deja de disminuir y terminas necesitando tiempo infinito.

aroth

@ Cano64 No lo creo. Creo que el criterio para la capacidad de decisión en la hipercomputación es que la suma de tiempo del cálculo converge absolutamente.

Theory of Everything

El tiempo necesario para un cálculo primitivo está limitado por la velocidad de la luz y el tamaño de los átomos, hasta donde entendemos la física en este mismo día, 15 de septiembre de 2015.

La unidad de cálculo debe construirse a partir de algo de tamaño distinto de cero (átomos) y para que el cálculo funcione, la electricidad o la luz deberán atravesarla, lo que estará limitado por el tiempo que tarda la luz en atravesar -cero distancia.

Dave Clarke
fuente

Un ejemplo concreto en la historia reciente de la ciencia que está superando los límites es la magnetorresistencia gigante , un descubrimiento ganador del premio Nobel que permitió la densidad de datos en discos duros que antes se consideraba imposible. Hay muchos, muchos más si vuelves; trate de explicar la posibilidad de un "teléfono inteligente" a una persona desde 1500 AD. (Puede que te quemen como bruja, así que ten cuidado). Así que creo que no debemos suponer que nuestro conocimiento actual de la física induce límites duros en lo que es posible.

Raphael

-1

La respuesta de "Teoría de todo" es buena, pero quiero agregar una intuición de por qué converge a , lo que podemos traducir en una respuesta a esta pregunta: $\Sigma_{n=1}^\infty (\frac{1}{2})^n$ $1$

Imagina que tienes un cubo rojo y uno azul; el cubo azul contiene un litro de agua y el cubo rojo está vacío. Vierte la mitad del agua del azul al rojo. Ahora ambos cubos tienen litro de agua en ellos. Vuelves a verter la mitad de lo que está en la cubeta azul en la roja, ahora hay litro de agua en la cubeta azul y litro en la roja. Ahora continúa, vertiendo siempre la mitad de lo que está en el cubo azul en el cubo rojo. Claramente, nunca obtendrá más de un litro en el cubo rojo, y con la misma claridad siempre tendrá más agua en el cubo azul para verter. $\frac{1}{2}$ $\frac{1}{4}$ $\frac{3}{4}$

Para completar la analogía; el cubo azul contiene tiempo, exactamente el doble de tiempo que el primer cálculo . Para cada paso del cálculo, usa la mitad del tiempo de cálculo restante y lo vierte en el cubo rojo del tiempo usado. Así como el cubo rojo de agua no puede contener más agua que el azul, el cubo rojo del tiempo utilizado no puede contener más del doble del tiempo de cálculo de . Y al igual que siempre quedaba agua en el cubo azul, siempre tendremos un poco de tiempo de cálculo para el próximo cálculo. $c_1$ $c_1$

Editar : Como señaló @aroth, esta analogía supone que podemos seguir dividiendo el agua para siempre; que no hay un átomo indivisible más pequeño. Lo que plantea el interesante punto (creo) de que también debemos suponer que el tiempo es arbitrariamente divisible para que el cálculo finalice en tiempo finito.

epa095
fuente

"y con la misma claridad siempre tendrás más agua en el cubo azul para verter" - No necesariamente. Con un aparato de vertido lo suficientemente preciso, eventualmente llegará a un punto donde hay 2 moléculas de agua en el cubo azul. Entonces 1 molécula. Luego viertes la última molécula o no. O lo descompone en sus átomos base, pero ya no es agua (o vertible en STP). El punto es que llegarás a la última molécula de agua mucho antes de llegar al final de la serie infinita, por lo que "no siempre" habrá agua en el cubo azul.

Aroth

@aroth: sí, es cierto, para que la analogía funcione, debes pensar en el agua como una "densidad" satisfactoria, una especie de "siempre divisibilidad". Su punto es interesante ya que resalta algo importante; Para que el cálculo finalice en tiempo finito, el tiempo también debe ser denso / siempre divisible. Si existe una cantidad de tiempo más corta, una unidad atómica no divisible de tiempo, entonces el cálculo infinito tomará tiempo infinito (o cada cálculo no debe tomar tiempo cada uno después de algún punto).

epa095

@ epa095 Si considera que el agua es infinitamente subdivisible, ya no está proporcionando intuición. Simplemente está replanteando el problema ("Computadora ") de una manera diferente, es decir, llamando a la cantidad una "cantidad de agua "en lugar de un" número racional ".

\sum_{i = 1}^{\infty} 2^{- i}

$\sum_{i=1}^\infty 2^{-i}$

2^{- i}

$2^{-i}$

David Richerby

@ david-richerby: ¿No es reafirmar el problema de una manera diferente, dando una manera más fácil de pensarlo, exactamente qué es proporcionar intuición? También tenga en cuenta que usted está también aposentado el problema, a partir cantidad de tiempo a la suma de los números racionales. Un paso (extremadamente) corto, sí, pero, sin embargo, una reformulación. Si conoce la convergencia de sumas de números racionales, ese replanteamiento hace que sea más fácil de entender, pero para algunos estoy seguro de que es más fácil de entender en términos de agua. Al menos así es como entendí por qué convergieron algunas sumas infinitas y otras no.

epa095

@ epa095 Brindar intuición implica explicar una situación desconocida haciendo referencia a una situación familiar y utilizando la familiaridad con una situación para ayudar a comprender la otra. No estás haciendo eso: estás tratando de explicar una situación desconocida (calculando una suma convergente infinita) por otra (vertiendo cubos de agua infinitamente divisible con perfecta precisión). Las personas que conocen la convergencia de sumas no necesitan la analogía; Para las personas que no saben sobre la convergencia de sumas, renombrar "número racional" a "cantidad de agua hipotética" no ayuda.

David Richerby