Введение

Бесконечное количество задач за конечное время – термин в информатике.

В философии, суперзадача — это счётная бесконечная последовательность операций, происходящих последовательно в пределах конечного интервала времени. Когда количество операций становится несчётной бесконечностью, суперзадачи называются гиперзадачами. Гиперзадача, включающая в себя задачу для каждого ординального числа, называется ультразадачей. Термин "суперзадача" был предложен философом Джеймсом Ф. Томсоном, который разработал лампу Томсона. Термин "гиперзадача" происходит от работы Кларка и Рида с одноимённым названием.

Ахиллес и черепаха

Сам Зенон также обсуждает понятие того, что он называет "Ахиллес и черепаха". Предположим, что Ахиллес – самый быстрый бегун и движется со скоростью 1 м/с. Ахиллес преследует черепаху, животное, известное своей медлительностью, которая движется со скоростью 0,1 м/с. Однако черепаха стартует на 0,9 метра впереди. Здравый смысл подсказывает, что Ахиллес догонит черепаху ровно через 1 секунду, но Зенон утверждает обратное. Он предполагает, что Ахиллес неизбежно должен достичь точки, с которой начала движение черепаха, но к тому моменту, как он это сделает, черепаха уже продвинется дальше. Этот процесс повторяется: каждый раз, когда Ахиллес достигает места, где была черепаха, она уже переместится в новую точку, которую ему предстоит догнать. Изначально это 0,9 метра, затем 0,09 метра, потом 0,009 метра и так далее, до бесконечности. Хотя эти расстояния становятся всё меньше, они остаются конечными, а преследование Ахиллесом черепахи превращается в бесконечную задачу. Этому парадоксу посвящено множество комментариев; многие считают, что он выявляет противоречие в здравом смысле.

Томсон

Джеймс Ф. Томсон полагал, что движение не является суперзадачей, и он решительно отрицал возможность существования суперзадач. Он рассматривал лампу, которая может быть либо включена, либо выключена. В момент времени t = 0 лампа выключена, а переключатель включается в момент времени t = 1/2; после этого переключатель переключается после ожидания времени, равного половине предыдущего интервала. Томсон спрашивает, каким будет состояние лампы в момент времени t = 1, когда переключатель был переключен бесконечное число раз. Он рассуждает, что лампа не может быть включена, поскольку не было ни одного момента времени, когда бы она не была впоследствии выключена, и наоборот, что приводит к противоречию. Он заключает, что суперзадачи невозможны.

Бенасерраф

Пол Бенасерраф полагает, что суперзадачи, по крайней мере, логически возможны, несмотря на кажущееся противоречие, указанное Томсоном. Бенасерраф согласен с Томсоном в том, что описанный им эксперимент не устанавливает состояние лампы в момент t = 1. Однако он не согласен с Томсоном в том, что из этого можно вывести противоречие, поскольку состояние лампы в момент t = 1 не может быть логически определено предшествующими состояниями.

Современная литература

Большая часть современной литературы исходит от последователей Бенасеррафа, тех, кто неявно допускает возможность суперзадач. Философы, отвергающие их возможность, как правило, не делают этого по причинам, подобным аргументам Томсона, а из-за сомнений в самом понятии бесконечности. Разумеется, существуют исключения. Например, Маклафлин утверждает, что лампа Томсона оказывается противоречивой, если её анализировать с использованием внутренней теории множеств, разновидности вещественного анализа.

Философия математики

Если суперзадачи возможны, то истинность или ложность неизвестных утверждений теории чисел, таких как гипотеза Гольдбаха, или даже неразрешимых утверждений, могла бы быть установлена за конечное время путем полного перебора множества всех натуральных чисел. Однако это противоречило бы тезису Черча-Тьюринга. Некоторые утверждают, что это представляет проблему для интуиционизма, поскольку интуиционист должен проводить различие между тем, что на самом деле не может быть доказано (потому что это слишком долго или сложно; например, "Любопытный вывод" Булоса), но при этом считается "доказуемым", и тем, что может быть доказано бесконечным полным перебором в указанном выше смысле.

Физическая возможность

Некоторые утверждают, что лампа Томсона физически невозможна, поскольку в ней должны быть части, движущиеся со скоростью, превышающей скорость света (например, выключатель лампы). Адольф Грунбаум предполагает, что лампа может иметь полоску проволоки, которая, при подъеме, разрывает цепь и выключает лампу; эту полоску можно поднимать на все меньшее расстояние каждый раз, когда лампу нужно выключить, поддерживая постоянную скорость. Однако такая конструкция в конечном итоге не сработает, поскольку в конечном счете расстояние между контактами станет настолько малым, что электроны смогут перескочить через зазор, полностью предотвратив разрыв цепи. Тем не менее, для того чтобы человек или любое устройство восприняло или отреагировало на состояние лампы, необходимо провести какое-либо измерение, например, свет от лампы должен достигнуть глаза или датчика. Любое такое измерение займет фиксированный промежуток времени, каким бы малым он ни был, и, следовательно, в какой-то момент измерение состояния станет невозможным. Поскольку состояние при t=1 нельзя определить даже в принципе, не имеет смысла говорить о том, что лампа включена или выключена. Были предложены и другие физически возможные суперзадачи. В одном предложении один человек (или субъект) считает от 1, затрачивая бесконечное время, в то время как другой наблюдает это из системы отсчета, где это происходит за конечное время. Для счетчика это не суперзадача, но для наблюдателя – да. (Это теоретически может произойти из-за замедления времени, например, если наблюдатель падает в черную дыру, наблюдая за счетчиком, положение которого фиксировано относительно сингулярности.) Густаво Э. Ромеро в статье «Крах суперзадач» утверждает, что любая попытка выполнить суперзадачу приведет к образованию черной дыры, что сделает суперзадачи физически невозможными.

Машины супер Тьюринга

Влияние суперзадач на теоретическую информатику стимулировало появление новых и интересных работ, например, работа Хамкинса и Льюиса "Машина Тьюринга с бесконечным временем".

Парадокс Росса и Литтлвуда

Предположим, что есть банка, способная вместить бесконечное количество шариков, и бесконечная коллекция шариков, пронумерованных 1, 2, 3 и так далее. В момент времени t = 0 шарики с 1 по 10 помещаются в банку, и шарик номер 1 извлекается. При t = 0.5 шарики с 11 по 20 помещаются в банку, и шарик номер 2 извлекается; при t = 0.75 шарики с 21 по 30 помещаются в банку, и шарик номер 3 извлекается; и в общем случае, в момент времени t = 1 − 0.5n, шарики с 10n + 1 по 10n + 10 помещаются в банку, и шарик номер n + 1 извлекается. Сколько шариков находится в банке в момент времени t = 1? Один из аргументов утверждает, что в банке должно быть бесконечно много шариков, поскольку на каждом шаге до t = 1 количество шариков увеличивается по сравнению с предыдущим шагом и делает это неограниченно. Однако второй аргумент показывает, что банка пуста. Рассмотрим следующий аргумент: если банка не пуста, то в ней должен находиться хотя бы один шарик. Предположим, что этот шарик пронумерован n. Но в момент времени t = 1 − 0.5n, n-й шарик был извлечен, следовательно, шарик номер n не может находиться в банке. Это противоречие, поэтому банка должна быть пуста. Парадокс Росса — Литтлвуда заключается в том, что у нас есть два, казалось бы, совершенно корректных аргумента, приводящих к полностью противоположным выводам.

Парадокс Бенардете

К работе Дж. А. Беннардетта «Парадокс богов» проявлен значительный интерес.

Парадокс Смерти

Вдохновленный парадоксом Дж. А. Бенардете относительно бесконечной цепочки убийц, Дэвид Чалмерс описывает этот парадокс следующим образом:

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

Супер-машина Дэвиса

Предложенная Э. Брайаном Дэвисом, эта машина способна за полчаса создать точную копию себя, вдвое меньшую по размеру и обладающую вдвое большей скоростью репликации. Эта копия, в свою очередь, создаст еще более быструю версию себя с теми же характеристиками, что приведет к выполнению сверхзадачи за один час. Если, кроме того, машины установят канал связи между родительской и дочерней машинами, обеспечивающий последовательно возрастающую пропускную способность, и будут способны к простым арифметическим операциям, их можно будет использовать для перебора вариантов при доказательстве неизвестных гипотез. Однако Дэвис также отмечает, что из-за фундаментальных свойств реальной вселенной, таких как квантовая механика, тепловой шум и теория информации, его машина не может быть реализована на практике.