Никаких супер-машин Тьюринга

Время от времени вы будете читать о прорыве, в котором утверждается, что какой-то странный компьютер может решить NP-задачи на P. Иными словами, нам представлена супер-машина Тьюринга, способная вычислять что-то, что не является вычислимым. Обычно это оказывается сложнее, чем предполагают заголовки.

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

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

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

Исследователи говорят:

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

Что общего у этих машин, так это то, что они находят способ постичь бесконечность. Например, если у вас есть компьютер, которому требуется 1/2n единиц времени для выполнения n-го шага программы, то он выполнит счетное бесконечное количество шагов за одну единицу времени. С такой машиной проблема остановки не проблема.

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

Существуют различные модели, которые используют общие релятивистские эффекты, чтобы позволить компьютеру испытать отличное (и бесконечное) собственное время от (конечного) времени, которое испытывает наблюдатель. Самая известная из них — модель пространства-времени Маламента – Хогарта (Этеси и Нэмети; 2002; Хогарт; 1992). Основная концепция заключается в том, что компьютер попадает в одно из этих пространств-времени, где его можно наблюдать извне. Если вычисление не останавливается, это может быть определено за конечное время наблюдателем во внешней системе отсчета, и, таким образом, установка решает проблему остановки.

Это, вероятно, нравится физику, но математик, вероятно, предпочитает машину с действительными числами, которая, по сути, представляет собой любой вычислительный процесс, работающий с точными действительными числами. Это приводит к разного рода ошибкам в мышлении. Недавно было заявлено, что мемрезисторная машина решает проблемы NP в P, но это возможно только в том случае, если вы можете проводить измерения с бесконечной точностью, что, конечно, невозможно. То же верно и для многих традиционных «вычислений». Возьмем конструкцию линейки и компаса. Они способны вычислить точное представление, скажем, квадратного корня из двух, но, конечно, в этом нет ничего точного, если только линия, которую вы рисуете, не является бесконечно узкой.

Прочтите оставшуюся часть статьи. Существует много информации о квантовых вычислениях, вычислениях ДНК, эволюционных процессорах, оптических вычислениях, вычислениях памяти и, что самое удивительное, вычислениях мозга.

Перед тем, как увлечься, стоит изложить часть заключения:

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

В конце статьи авторы предлагают три закона вычислений. Они делают это «слегка иронично», но я думаю, что они, вероятно, правы:

1-й закон вычислений: вы не можете эффективно решать невычислимые или N P-трудные задачи, если у вас нет физической бесконечности или эффективного оракула.

2-й закон вычислений: нет физических бесконечностей или эффективных оракулов.

3-й закон вычислений: природа физична и не решает невычислимые или непростые задачи эффективно.

Следствие: Природа обязательно решает невычислимые или N P-трудные задачи только приблизительно.

Пока все разумно, но подождите:

Возникает вопрос: что умеет UCOMP? Учитывая, что UCOMP не решает невычислимых или даже N P-сложных проблем (и это также относится к квантовым вычислениям), каково будущее UCOMP?

Обратите внимание на то, что три закона вычислений распространяются не только на классические, но и на квантовые вычисления!