Как модели гиперкомпьютеров преодолевают проблему остановки?

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

Какие виды «суперспособностей» используют гиперкомпьютеры?

Тезис Эда Блэки устанавливает формальную структуру для классификации некоторых основных видов ресурсов, используемых в гиперкомпьютерах, но он не пытается дать всесторонний обзор супердержав. Я не заинтересован в списке гиперкомпьютеров (есть хороший список в статье в Википедии), но в понимании того, какой «особый соус» использует каждая модель, возможно, рассматриваемый как уникальный вид ресурса.

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

В статье « О силе умножения в машинах с произвольным доступом » Хартманис доказал, что если мы добавим инструкцию умножения удельных затрат в ОЗУ (называемую MRAM), то для этой модели P = NP. Кроме того, языки, выбранные за полиномиальное время в модели MRAM, в точности совпадают с языками в PSPACE.

Как указано в статье, эти результаты показывают, что умножение имеет ту же сложность, что и сложение, если P = PSPACE.

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

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

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

• Манипулирование временем и пространством

$NP$Физики-теоретики считают, что эти условия выполняются вблизи края черных дыр. Для этого у вас должна быть вычислительная машина, расположенная очень близко к черной дыре, но не на горизонте событий (чтобы она не втягивалась). Затем вы погружаетесь в черную дыру и можете просмотреть всю бесконечную временную шкалу вашей машины за конечное время. Это, вероятно, означает, что вы оказались втянуты в черную дыру, поэтому я думаю, что она не будет реализована и протестирована, даже если мы сможем добраться до черной дыры. Это все неформально, вы начинаете читать более теоретический физический подход из статьи в Википедии о Malament-Hogarth_spacetime . Полезной цитатой также является статья. Позволяет ли общая теория относительности наблюдать вечность за конечное время?

• Машина Зенона может решить любую проблему за 2 секунды, но это математическая гипотетическая конструкция, где каждый шаг занимает половину времени перед этим, а первый раз - 1 секунду. Он не предоставляет реального решения, которое вы могли бы реализовать.

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

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