Бесконечные вычисления за конечное время

Это, вероятно , глупая мысль, но предположим , что у нас есть компьютер , который запрограммирован для выполнения бесконечную последовательность расчетов и предположим , что расчет занимает 1 / 2 я секунд. Тогда этот компьютер может выполнять бесконечное количество вычислений за конечное время.$i^\text{th}$$1/2^i$

Почему это невозможно? Существует ли нижняя граница того, сколько времени потребуется для выполнения нетривиального вычисления?

Этот «вид» компьютера известен как Zeno Machine . Его вычислительная модель попадает в категорию под названием Гиперкомпьютер . Гиперкомпьютерные модели являются математическими абстракциями, и из-за того, как они определены для работы, они физически невозможны.

Возьмите свою машину Zeno, например. Если мы представим, что Zeno Machine является вычислительной машиной любого типа, не имеет значения, использует ли она счет или интегральную схему. Скажем, данные программы, используемые машиной, передаются на нее бесконечно длинной лентой символов (как машина Тьюринга).

Конечно, мы знаем из математики, что:

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

который мы говорим, равен . Таким образом, вычисление должно завершиться за 1 секунду, потому что сумма абсолютно сходится.$1$

Но эта сходимость, конечно, зависит от того, что стремится к бесконечности (и достигает ее). В физическом смысле это означает, что по мере того, как время, необходимое для каждого вычисления, уменьшается, «считывающая головка» вычислительной машины будет все быстрее и быстрее перемещаться по символам на ленте. В какой-то момент эта скорость превысит скорость света.$n$

Таким образом, отвечая на ваш второй вопрос, абсолютная наименьшая возможная граница для расчета, вероятно, будет порядка планковского времени, учитывая скорость света как основной ограничивающий фактор в теоретических, но физически вероятных моделях вычислений.

Время, затрачиваемое на примитивные вычисления, ограничено скоростью света и размерами атомов, насколько мы понимаем физику в тот же день, 15 сентября 2015 года.

Вычислительная единица должна быть построена из чего-то ненулевого размера (атомов), и для того, чтобы вычисления работали, электричество или свет должны будут проноситься через него, что будет ограничено тем, как долго свет проникает через нулевое расстояние.

$\Sigma_{n=1}^\infty (\frac{1}{2})^n$$1$

$\frac{1}{2}$$\frac{1}{4}$$\frac{3}{4}$ литра в красном. Теперь продолжайте, всегда выливая половину того, что находится в синем ведре, в красное ведро. Ясно, что вы никогда не получите больше одного литра в красное ведро, и точно так же у вас всегда будет больше воды в голубом ведре для переливания.

$c_1$$c_1$

Изменить : Как отметил @aroth, эта аналогия предполагает, что мы можем продолжать делить воду навсегда; что нет наименьшего неделимого атома. Это поднимает интересный (я думаю) момент, что мы должны также предположить, что время должно быть произвольно делимым, чтобы вычисление завершилось за конечное время.