Редактирование: Сверхтьюринговые вычисления (гипервычисления)
Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.
Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия | Ваш текст | ||
Строка 1: | Строка 1: | ||
== Сверхтьюринговые вычисления == | == Сверхтьюринговые вычисления == | ||
− | '''Сверхтьюринговыми вычислениями''' (или '''гипервычислениями''' (англ. | + | '''Сверхтьюринговыми вычислениями''' (или '''гипервычислениями''' (англ. <tex>\it hypercomputation</tex>)) называются такие вычисления, которые не могут быть проделаны на машине Тьюринга |
, а следовательно не исчислимы в рамках тезисов Черча-Тьюринга. | , а следовательно не исчислимы в рамках тезисов Черча-Тьюринга. | ||
Такие гипотетические устройства Тьюрингом были рассмотрены еще в 1939 году. | Такие гипотетические устройства Тьюрингом были рассмотрены еще в 1939 году. | ||
− | Это машины | + | Это машины с оракулом. Под оракулом понимается некая сущность, |
− | способная «вычислять» | + | способная «вычислять» невычислимые функции или решать алгоритмически неразрешимые проблемы. |
Тьюринг показал, что для таких машин проблемы, сформулированные относительно них самих (например, проблема останова машины с оракулом) | Тьюринг показал, что для таких машин проблемы, сформулированные относительно них самих (например, проблема останова машины с оракулом) | ||
ими же являются неразрешимыми. Это напоминает древний парадокс: может ли всемогущий бог создать камень, | ими же являются неразрешимыми. Это напоминает древний парадокс: может ли всемогущий бог создать камень, | ||
Строка 12: | Строка 12: | ||
для них также найдутся неразрешимые проблемы. | для них также найдутся неразрешимые проблемы. | ||
== Предполагаемые способы сверхтьюринговых вычислений: == | == Предполагаемые способы сверхтьюринговых вычислений: == | ||
− | * Машина | + | * Машина тьюринга которая может выполнить бесконечное число шагов. |
− | ::Один из математических способов — Машина Зенона. Машина Зенона выполняет свой первый шаг за <tex> | + | ::Один из математических способов — Машина Зенона. Машина Зенона выполняет свой первый шаг за <tex>1</tex> минуту, следующий шаг за <tex>\frac{1}{2}</tex> минуты, следующий за <tex>\frac{1}{4}</tex> и т.д. |
− | + | Суммируя <tex>1+\frac{1}{2}+\frac{1}{4}</tex> (геометрическая прогрессия) мы видим, что машина выполняет бесконечно количество шагов за 2 минуты. | |
*Вечная машина Тьюринга. | *Вечная машина Тьюринга. | ||
::Вечная машина Тьюринга это обобщение машина Зенона, которая может выполнить неопределенно продолжительное вычисление, | ::Вечная машина Тьюринга это обобщение машина Зенона, которая может выполнить неопределенно продолжительное вычисление, | ||
− | + | шаги в котором перенумерованы потенциально трансфинитными ординальными числами. | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
+ | *Artificial Recurrent Neural Network | ||
+ | ::В 1994 Хава Сигельманн доказала, что ее новая вычислительная модель the Artificial Recurrent Neural Network (ARNN), может выполнить | ||
+ | гипервычисления, используя бесконечную точность. Также она предложила модель, основанную на бесконечной эволюции нейронных сетей, способную проводить гипервычисления. | ||
+ | *Неограниченный детерминизм | ||
+ | ::Техника, известная как неограниченный детерминизм, может позволять вычисление невычислимых функций. Это вопрос является предметом обсуждения в литературе. | ||
+ | *:Использование замкнутых времениподобных кривых, вопреки распространённому мнению, не позволяет выполнять сверхтьюринговые вычисления, так как отсутствует бесконечный объём памяти. | ||
== Машина Зенона == | == Машина Зенона == | ||
{{Определение | {{Определение | ||
|definition = | |definition = | ||
− | '''Машина Зенона''' ( | + | '''Машина Зенона''' <tex>\it (zeno </tex> <tex>\it machine) </tex> — это гипотетическая компьютерная модель, связанная с машиной Тьюринга, которая способна совершить счётное количество алгоритмических шагов за конечное время. В большинстве моделей вычислений такие машины не рассматриваются. |
}} | }} | ||
− | Некоторые функции, которые не могут быть вычислены на машине Тьюринга, могут быть вычислены с использованием машины Зенона. Например, на ней может быть решена проблема остановки (что иллюстрируется следующим псевдокодом): | + | Теория точки Омега, разработанная Франком Типплером, верна, только если машина Зенона может существовать. |
− | + | Некоторые функции, которые не могут быть вычислены на машине Тьюринга, могут быть вычислены с использованием машины Зенона. Например, на ней может быть решена проблема остановки (что иллюстрируется следующим псевдокодом): | |
− | + | '''начало программы''' | |
− | ''' | + | записать 0 в первую ячейку на ленте; |
− | записать 0 в первую ячейку на | + | '''начало цикла''' |
− | ''' | + | смоделировать очередной шаг работы данной машины Тьюринга на данном входе; |
− | смоделировать очередной шаг работы данной машины Тьюринга на данном входе | + | '''если''' машина Тьюринга остановилась, '''то''' записать 1 в первую ячейку на ленте и '''прервать цикл'''; |
− | ''' | + | '''конец цикла''' |
− | + | '''конец программы''' | |
− | |||
− | |||
Такие вычисления, выходящие за рамки возможности машины Тьюринга, называются гипервычислениями. | Такие вычисления, выходящие за рамки возможности машины Тьюринга, называются гипервычислениями. | ||
− | + | Стоит заметить, что проблема остановки для самой машины Зенона не может быть решена на машине Зенона. | |
− | |||
− | |||
− | Стоит заметить, что проблема | ||
− | |||
− | |||
− | |||
== Возможность супертьюринговых машин == | == Возможность супертьюринговых машин == | ||
− | + | Множится число исследователей, полагающих, что существуют процессы, требующие методов, которые не охвачены теорией Тьюринга. | |
+ | Такова, в частности, позиция сторонников теории гиперкомпьютинга и, соответственно, гипервычислений, понимаемых как сверхтьюринговых. | ||
+ | Теоретическая разработка | ||
* Процесс может быть использован в математических целях, если и только если его поведение на входе/выходе: | * Процесс может быть использован в математических целях, если и только если его поведение на входе/выходе: | ||
** либо детерминистично, либо приблизительно детерминистично и вызываемая им ошибка может быть сведена к произвольно малой величине; | ** либо детерминистично, либо приблизительно детерминистично и вызываемая им ошибка может быть сведена к произвольно малой величине; | ||
** определяется за конечное число шагов. | ** определяется за конечное число шагов. | ||
− | * Процесс может быть использован в его физических качествах, если и только если его поведение на входе/выходе в соответствии с научными данными может быть использовано для моделирования других специфических процессов. | + | * Процесс Р может быть использован в его физических качествах, если и только если его поведение на входе/выходе в соответствии с научными данными может быть использовано для моделирования других специфических процессов. |
+ | Смысл двух приведенных выше тезисов состоит в обосновании возможности сверхтьюринговых машин, способных осуществлять гипервычисления. | ||
== Проекты супертьюринговых машин == | == Проекты супертьюринговых машин == | ||
− | Существует несколько десятков проектов супертьюринговых машин | + | Существует несколько десятков проектов супертьюринговых машин. |
− | * попытка отказаться от линейности времени: оно замедляется, ускоряется, замыкается. Как известно из физики, такие процессы действительно существуют | + | * ввод информации еще на стадии выполнения программы, |
− | * делаются попытки использовать актуальную бесконечность: имеется в виду, что сумма бесконечного числа членов может иметь вполне определенное значение | + | * попытка отказаться от линейности времени: оно замедляется, ускоряется, замыкается. Как известно из физики, такие процессы действительно существуют. |
− | * самые большие надежды возлагаются на | + | * делаются попытки использовать актуальную бесконечность: имеется в виду, что сумма бесконечного числа членов может иметь вполне определенное значение. |
− | + | * но самые большие надежды возлагаются на квантовые компьютеры. Чтобы осуществить вычисление, во-первых, необходимо управлять кубитами, во-вторых, дать реализоваться квантовому алгоритму, в-третьих, измерить состояния кубитов регистра. В принципиальном отношении все три операции осуществимы. | |
== См. также == | == См. также == | ||
− | * [[ | + | * [[Машина Тьюринга]] |
* [[Лямбда-исчисление]] | * [[Лямбда-исчисление]] | ||
− | |||
− | |||
− | |||
− | |||
− | |||
== Источники информации == | == Источники информации == | ||
− | + | *[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 | + | * [https://ru.wikipedia.org/wiki/%D0%9C%D0%B0%D1%88%D0%B8%D0%BD%D0%B0_%D0%97%D0%B5%D0%BD%D0%BE%D0%BD%D0%B0| Машина Зенона] |
− | * [https://ru.wikipedia.org/wiki/%D0%9C%D0%B0%D1%88%D0%B8%D0%BD%D0%B0_%D0%97%D0%B5%D0%BD%D0%BE%D0%BD%D0%B0 | ||
− | |||
[[Категория: Теория формальных языков]] | [[Категория: Теория формальных языков]] | ||
[[Категория: Теория вычислимости]] | [[Категория: Теория вычислимости]] | ||
[[Категория: Вычислительные формализмы]] | [[Категория: Вычислительные формализмы]] |