Редактирование: Сверхтьюринговые вычисления (гипервычисления)
Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.
Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия | Ваш текст | ||
Строка 1: | Строка 1: | ||
== Сверхтьюринговые вычисления == | == Сверхтьюринговые вычисления == | ||
− | + | {{Определение | |
− | '''Сверхтьюринговыми вычислениями''' (или '''гипервычислениями''' (англ. | + | |definition = |
+ | '''Сверхтьюринговыми вычислениями''' (или '''гипервычислениями''' (англ. hypercomputation)) называются такие вычисления, которые не могут быть проделаны на машине Тьюринга | ||
, а следовательно не исчислимы в рамках тезисов Черча-Тьюринга. | , а следовательно не исчислимы в рамках тезисов Черча-Тьюринга. | ||
+ | }} | ||
Такие гипотетические устройства Тьюрингом были рассмотрены еще в 1939 году. | Такие гипотетические устройства Тьюрингом были рассмотрены еще в 1939 году. | ||
− | Это машины | + | Это машины с оракулом. Под оракулом понимается некая сущность, |
− | способная «вычислять» | + | способная «вычислять» невычислимые функции или решать алгоритмически неразрешимые проблемы. |
Тьюринг показал, что для таких машин проблемы, сформулированные относительно них самих (например, проблема останова машины с оракулом) | Тьюринг показал, что для таких машин проблемы, сформулированные относительно них самих (например, проблема останова машины с оракулом) | ||
ими же являются неразрешимыми. Это напоминает древний парадокс: может ли всемогущий бог создать камень, | ими же являются неразрешимыми. Это напоминает древний парадокс: может ли всемогущий бог создать камень, | ||
который сам не сможет поднять?.. Поэтому даже если сверхтьюринговые вычисления физически реализуемы, | который сам не сможет поднять?.. Поэтому даже если сверхтьюринговые вычисления физически реализуемы, | ||
− | для них также найдутся неразрешимые проблемы. | + | для них также найдутся неразрешимые проблемы. Видимо, что-то не так с самой формой постановки этих проблем, |
+ | неразрешимых ни алгоритмически, ни божественно. | ||
+ | |||
+ | |||
+ | |||
+ | |||
== Предполагаемые способы сверхтьюринговых вычислений: == | == Предполагаемые способы сверхтьюринговых вычислений: == | ||
− | |||
− | |||
− | |||
− | * | + | * Машина тьюринга которая может выполнить бесконечное число шагов. |
− | + | Один из математических способов - Машина Зенона. | |
− | + | Машина Зенона выполняет свой первый шаг за <tex>1</tex> минуту, следующий шаг за <tex>1/2</tex> минуты, следующий за <tex>1/4</tex> и т.д. | |
+ | Суммируя <tex>1+1/2+1/4</tex> (геометрическая прогрессия) мы видим, что машина выполняет бесконечно количество шагов за 2 минуты. | ||
− | * | + | * Вечная машина Тьюринга это обобщение машина Зенона, которая может выполнить неопределенно продолжительное вычисление, |
− | + | шаги в котором перенумерованы потенциально трансфинитными ординальными числами. | |
− | |||
− | |||
− | |||
− | + | * В 1994 Хава Сигельманн доказала, что ее новая вычислительная модель the Artificial Recurrent Neural Network (ARNN), может выполнить | |
− | + | гипервычисления, используя бесконечную точность. | |
− | + | Также она предложила модель, основанную на бесконечной эволюции нейронных сетей, способную проводить гипервычисления. | |
− | |||
− | |||
− | |||
− | + | *Техника, известная как неограниченный детерминизм, может позволять вычисление невычислимых функций. Это вопрос является предметом обсуждения в литературе. | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | + | *Использование замкнутых времениподобных кривых, вопреки распространённому мнению, не позволяет выполнять сверхтьюринговые вычисления, так как отсутствует бесконечный объём памяти. | |
− | |||
− | |||
− | |||
− | |||
− | |||
== Возможность супертьюринговых машин == | == Возможность супертьюринговых машин == | ||
− | + | Множится число исследователей, полагающих, что существуют процессы, требующие методов, которые не охвачены теорией Тьюринга. | |
+ | Такова, в частности, позиция сторонников теории гиперкомпьютинга и, соответственно, гипервычислений, понимаемых как сверхтьюринговых. | ||
+ | |||
+ | Теоретическая разработка | ||
+ | |||
* Процесс может быть использован в математических целях, если и только если его поведение на входе/выходе: | * Процесс может быть использован в математических целях, если и только если его поведение на входе/выходе: | ||
** либо детерминистично, либо приблизительно детерминистично и вызываемая им ошибка может быть сведена к произвольно малой величине; | ** либо детерминистично, либо приблизительно детерминистично и вызываемая им ошибка может быть сведена к произвольно малой величине; | ||
** определяется за конечное число шагов. | ** определяется за конечное число шагов. | ||
− | * Процесс может быть использован в его физических качествах, если и только если его поведение на входе/выходе в соответствии с научными данными может быть использовано для моделирования других специфических процессов | + | * Процесс Р может быть использован в его физических качествах, если и только если его поведение на входе/выходе в соответствии с научными данными может быть использовано для моделирования других специфических процессов. |
− | |||
− | |||
− | |||
− | |||
− | |||
− | + | Смысл двух приведенных выше тезисов состоит в обосновании возможности сверхтьюринговых машин, способных осуществлять гипервычисления. | |
− | |||
− | |||
− | |||
− | == | + | == Проекты супертьюринговых машин == |
− | + | Существует несколько десятков проектов супертьюринговых машин. | |
+ | * Ввод информации еще на стадии выполнения программы, | ||
+ | * Попытка отказаться от линейности времени: оно замедляется, ускоряется, замыкается. Как известно из физики, такие процессы действительно существуют. | ||
+ | * Делаются попытки использовать актуальную бесконечность: имеется в виду, что сумма бесконечного числа членов может иметь вполне определенное значение. | ||
+ | * Но самые большие надежды возлагаются на квантовые компьютеры. Чтобы осуществить вычисление, во-первых, необходимо управлять кубитами, во-вторых, дать реализоваться квантовому алгоритму, в-третьих, измерить состояния кубитов регистра. В принципиальном отношении все три операции осуществимы. | ||
== Источники информации == | == Источники информации == | ||
− | + | *[https://ru.wikipedia.org/wiki/%D0%A1%D0%B2%D0%B5%D1%80%D1%85%D1%82%D1%8C%D1%8E%D1%80%D0%B8%D0%BD%D0%B3%D0%BE%D0%B2%D1%8B%D0%B5_%D0%B2%D1%8B%D1%87%D0%B8%D1%81%D0%BB%D0%B5%D0%BD%D0%B8%D1%8F| Сверхтьюринговые вычисления] | |
− | *[https://ru.wikipedia.org/wiki/%D0%A1%D0%B2%D0%B5%D1%80%D1%85%D1%82%D1%8C%D1%8E%D1%80%D0%B8%D0%BD%D0%B3%D0%BE%D0%B2%D1%8B%D0%B5_%D0%B2%D1%8B%D1%87%D0%B8%D1%81%D0%BB%D0%B5%D0%BD%D0%B8%D1%8F | + | |
− | |||
− | |||
[[Категория: Теория формальных языков]] | [[Категория: Теория формальных языков]] | ||
[[Категория: Теория вычислимости]] | [[Категория: Теория вычислимости]] | ||
[[Категория: Вычислительные формализмы]] | [[Категория: Вычислительные формализмы]] |