Сверхтьюринговые вычисления (гипервычисления) — различия между версиями
м (rollbackEdits.php mass rollback) |
|||
(не показано 35 промежуточных версий 4 участников) | |||
Строка 1: | Строка 1: | ||
== Сверхтьюринговые вычисления == | == Сверхтьюринговые вычисления == | ||
− | '''Сверхтьюринговыми вычислениями''' (или '''гипервычислениями''' (англ. | + | '''Сверхтьюринговыми вычислениями''' (или '''гипервычислениями''' (англ. ''hypercomputation'')) называются такие вычисления, которые не могут быть проделаны на [[Машина Тьюринга|машине Тьюринга]] |
, а следовательно не исчислимы в рамках тезисов Черча-Тьюринга. | , а следовательно не исчислимы в рамках тезисов Черча-Тьюринга. | ||
Такие гипотетические устройства Тьюрингом были рассмотрены еще в 1939 году. | Такие гипотетические устройства Тьюрингом были рассмотрены еще в 1939 году. | ||
− | Это машины с оракулом. Под оракулом понимается некая сущность, | + | Это машины с [[Сложностные классы. Вычисления с оракулом | оракулом]]. Под оракулом понимается некая сущность, |
− | способная «вычислять» невычислимые функции или решать алгоритмически неразрешимые проблемы. | + | способная «вычислять» [[Вычислимые функции | невычислимые функции]] или решать алгоритмически [[Примеры неразрешимых задач: проблема соответствий Поста | неразрешимые проблемы]]. |
Тьюринг показал, что для таких машин проблемы, сформулированные относительно них самих (например, проблема останова машины с оракулом) | Тьюринг показал, что для таких машин проблемы, сформулированные относительно них самих (например, проблема останова машины с оракулом) | ||
ими же являются неразрешимыми. Это напоминает древний парадокс: может ли всемогущий бог создать камень, | ими же являются неразрешимыми. Это напоминает древний парадокс: может ли всемогущий бог создать камень, | ||
Строка 12: | Строка 12: | ||
для них также найдутся неразрешимые проблемы. | для них также найдутся неразрешимые проблемы. | ||
== Предполагаемые способы сверхтьюринговых вычислений: == | == Предполагаемые способы сверхтьюринговых вычислений: == | ||
− | * Машина | + | * Машина Тьюринга, которая может выполнить бесконечное число шагов. |
− | ::Один из математических способов — Машина Зенона. Машина Зенона выполняет свой первый шаг за <tex>1</tex> минуту, следующий шаг за <tex>\frac{1}{2}</tex> минуты, следующий за <tex>\frac{1}{4}</tex> и т.д. | + | ::Один из математических способов — Машина Зенона. Машина Зенона выполняет свой первый шаг за <tex>\displaystyle 1 </tex> минуту, следующий шаг за <tex> \displaystyle \frac{1}{2}</tex> минуты, следующий за <tex>\displaystyle \frac{1}{4}</tex> и т.д. |
− | Суммируя <tex>1+\frac{1}{2}+\frac{1}{4}</tex> (геометрическая прогрессия) мы видим, что машина выполняет бесконечно количество шагов за 2 минуты. | + | ::Суммируя <tex>\displaystyle 1+\frac{1}{2}+\frac{1}{4} \dots</tex> (геометрическая прогрессия) мы видим, что машина выполняет бесконечно количество шагов за 2 минуты. |
*Вечная машина Тьюринга. | *Вечная машина Тьюринга. | ||
::Вечная машина Тьюринга это обобщение машина Зенона, которая может выполнить неопределенно продолжительное вычисление, | ::Вечная машина Тьюринга это обобщение машина Зенона, которая может выполнить неопределенно продолжительное вычисление, | ||
− | шаги в котором перенумерованы потенциально трансфинитными ординальными числами. | + | ::шаги в котором перенумерованы потенциально трансфинитными ординальными числами. |
+ | |||
+ | *Artificial Recurrent Neural Network <ref>[http://en.wikipedia.org/wiki/Recurrent_neural_network Wikipedia {{---}} Artificial Recurrent Neural Network]</ref>. | ||
+ | ::В 1994 Хава Сигельманн доказала, что ее новая вычислительная модель the Artificial Recurrent Neural Network (ARNN) может выполнить гипервычисления, используя бесконечную точность. Также она предложила модель, основанную на бесконечной эволюции нейронных сетей, способную проводить гипервычисления. | ||
+ | *Неограниченный детерминизм. | ||
+ | ::Техника, известная как неограниченный детерминизм, позволяет вычислять невычислимые функции. Это вопрос является предметом обсуждения в литературе. | ||
+ | *Использование замкнутых времениподобных кривых<ref>[https://ru.wikipedia.org/wiki/%D0%97%D0%B0%D0%BC%D0%BA%D0%BD%D1%83%D1%82%D0%B0%D1%8F_%D0%B2%D1%80%D0%B5%D0%BC%D0%B5%D0%BD%D0%B8%D0%BF%D0%BE%D0%B4%D0%BE%D0%B1%D0%BD%D0%B0%D1%8F_%D0%BA%D1%80%D0%B8%D0%B2%D0%B0%D1%8F Википедия {{---}} Замкнутая времениподобная кривая]</ref>, вопреки распространённому мнению, не позволяет выполнять сверхтьюринговые вычисления, так как отсутствует бесконечный объём памяти. | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
== Машина Зенона == | == Машина Зенона == | ||
{{Определение | {{Определение | ||
|definition = | |definition = | ||
− | '''Машина Зенона''' | + | '''Машина Зенона''' (англ. ''zeno machine'') — это гипотетическая компьютерная модель, связанная с машиной Тьюринга, которая способна совершить счётное количество алгоритмических шагов за конечное время. В большинстве моделей вычислений такие машины не рассматриваются. |
}} | }} | ||
− | + | Некоторые функции, которые не могут быть вычислены на машине Тьюринга, могут быть вычислены с использованием машины Зенона. Например, на ней может быть решена проблема остановки (что иллюстрируется следующим псевдокодом): | |
− | Некоторые функции, которые не могут быть вычислены на машине Тьюринга, могут быть вычислены с использованием машины Зенона. Например, на ней может быть решена проблема остановки (что иллюстрируется следующим псевдокодом): | + | |
− | ''' | + | Будем использовать двуленточную машину Зенона. На одной ленте будем симулировать машину Тюринга, а на второй записывать результат. |
− | записать 0 в первую ячейку на ленте | + | '''<tex> p(M,x){:}</tex>''' |
− | ''' | + | записать 0 в первую ячейку на второй ленте |
− | смоделировать очередной шаг работы данной машины Тьюринга на данном входе | + | '''while''' ''true'': |
− | ''' | + | смоделировать очередной шаг работы данной машины Тьюринга на данном входе на первой ленте |
− | ''' | + | '''if''' машина Тьюринга остановилась: |
− | + | записать 1 в первую ячейку на ленте | |
+ | '''break''' | ||
+ | '''return''' первую ячейку на второй ленте | ||
Такие вычисления, выходящие за рамки возможности машины Тьюринга, называются гипервычислениями. | Такие вычисления, выходящие за рамки возможности машины Тьюринга, называются гипервычислениями. | ||
− | Стоит заметить, что проблема | + | |
+ | |||
+ | '''Замечание:''' | ||
+ | Стоит заметить, что проблема останова машины Зенона не может быть решена на самой машине Зенона. Хоть программы со счётным числом операций работают конечное время, всё равно программа на МЗ может зависнуть. | ||
+ | Пусть МЗ решает такую задачу: ей надо вывести все двоичные последовательности бесконечной длины. | ||
+ | Известно, что таких последовательностей — континуум. | ||
+ | А MЗ за бесконечное время выведет только не более чем счётное множество таких поиследовательностей, так как не более чем счётное объединение не более чем счётных множеств является не более чем счётным. Значит, МЗ может зависнуть. Поэтому для по аналогичным для МТ рассуждениям проблема останова для МЗ неразрешима. | ||
== Возможность супертьюринговых машин == | == Возможность супертьюринговых машин == | ||
− | + | Смысл двух приведенных ниже тезисов состоит в обосновании возможности сверхтьюринговых машин, способных осуществлять гипервычисления. | |
− | |||
− | |||
* Процесс может быть использован в математических целях, если и только если его поведение на входе/выходе: | * Процесс может быть использован в математических целях, если и только если его поведение на входе/выходе: | ||
** либо детерминистично, либо приблизительно детерминистично и вызываемая им ошибка может быть сведена к произвольно малой величине; | ** либо детерминистично, либо приблизительно детерминистично и вызываемая им ошибка может быть сведена к произвольно малой величине; | ||
** определяется за конечное число шагов. | ** определяется за конечное число шагов. | ||
− | * Процесс | + | * Процесс может быть использован в его физических качествах, если и только если его поведение на входе/выходе в соответствии с научными данными может быть использовано для моделирования других специфических процессов. |
− | |||
== Проекты супертьюринговых машин == | == Проекты супертьюринговых машин == | ||
− | Существует несколько десятков проектов супертьюринговых машин | + | Существует несколько десятков проектов супертьюринговых машин: |
− | + | * попытка отказаться от линейности времени: оно замедляется, ускоряется, замыкается. Как известно из физики, такие процессы действительно существуют; | |
− | * попытка отказаться от линейности времени: оно замедляется, ускоряется, замыкается. Как известно из физики, такие процессы действительно существуют | + | * делаются попытки использовать актуальную бесконечность: имеется в виду, что сумма бесконечного числа членов может иметь вполне определенное значение; |
− | * делаются попытки использовать актуальную бесконечность: имеется в виду, что сумма бесконечного числа членов может иметь вполне определенное значение | + | * самые большие надежды возлагаются на [[Квантовые гейты | квантовые компьютеры]]. Чтобы осуществить вычисление, во-первых, необходимо управлять кубитами, во-вторых, дать реализоваться квантовому алгоритму, в-третьих, измерить состояния кубитов регистра. В принципиальном отношении все три операции осуществимы. |
− | * | + | |
== См. также == | == См. также == | ||
− | * [[ | + | * [[Стековые машины, эквивалентность двухстековой машины МТ]] |
* [[Лямбда-исчисление]] | * [[Лямбда-исчисление]] | ||
+ | * [[Линейный клеточный автомат, эквивалентность МТ]] | ||
+ | |||
+ | == Примечания == | ||
+ | <references/> | ||
+ | |||
== Источники информации == | == Источники информации == | ||
− | *[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://en.wikipedia.org/wiki/Hypercomputation Wikipedia {{---}} Hypercomputation] |
− | * [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%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 Wikipedia {{---}} Сверхтьюринговые вычисления] |
+ | * [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 Wikipedia {{---}} Машина Зенона] | ||
+ | * [http://arxiv.org/ftp/math/papers/0209/0209332.pdf Hypercomputation: computing more than the Turing machine] | ||
[[Категория: Теория формальных языков]] | [[Категория: Теория формальных языков]] | ||
[[Категория: Теория вычислимости]] | [[Категория: Теория вычислимости]] | ||
[[Категория: Вычислительные формализмы]] | [[Категория: Вычислительные формализмы]] |
Текущая версия на 19:03, 4 сентября 2022
Сверхтьюринговые вычисления
Сверхтьюринговыми вычислениями (или гипервычислениями (англ. hypercomputation)) называются такие вычисления, которые не могут быть проделаны на машине Тьюринга , а следовательно не исчислимы в рамках тезисов Черча-Тьюринга.
Такие гипотетические устройства Тьюрингом были рассмотрены еще в 1939 году. Это машины с оракулом. Под оракулом понимается некая сущность, способная «вычислять» невычислимые функции или решать алгоритмически неразрешимые проблемы. Тьюринг показал, что для таких машин проблемы, сформулированные относительно них самих (например, проблема останова машины с оракулом) ими же являются неразрешимыми. Это напоминает древний парадокс: может ли всемогущий бог создать камень, который сам не сможет поднять?.. Поэтому даже если сверхтьюринговые вычисления физически реализуемы, для них также найдутся неразрешимые проблемы.
Предполагаемые способы сверхтьюринговых вычислений:
- Машина Тьюринга, которая может выполнить бесконечное число шагов.
- Один из математических способов — Машина Зенона. Машина Зенона выполняет свой первый шаг за минуту, следующий шаг за минуты, следующий за и т.д.
- Суммируя (геометрическая прогрессия) мы видим, что машина выполняет бесконечно количество шагов за 2 минуты.
- Вечная машина Тьюринга.
- Вечная машина Тьюринга это обобщение машина Зенона, которая может выполнить неопределенно продолжительное вычисление,
- шаги в котором перенумерованы потенциально трансфинитными ординальными числами.
- Artificial Recurrent Neural Network [1].
- В 1994 Хава Сигельманн доказала, что ее новая вычислительная модель the Artificial Recurrent Neural Network (ARNN) может выполнить гипервычисления, используя бесконечную точность. Также она предложила модель, основанную на бесконечной эволюции нейронных сетей, способную проводить гипервычисления.
- Неограниченный детерминизм.
- Техника, известная как неограниченный детерминизм, позволяет вычислять невычислимые функции. Это вопрос является предметом обсуждения в литературе.
- Использование замкнутых времениподобных кривых[2], вопреки распространённому мнению, не позволяет выполнять сверхтьюринговые вычисления, так как отсутствует бесконечный объём памяти.
Машина Зенона
Определение: |
Машина Зенона (англ. zeno machine) — это гипотетическая компьютерная модель, связанная с машиной Тьюринга, которая способна совершить счётное количество алгоритмических шагов за конечное время. В большинстве моделей вычислений такие машины не рассматриваются. |
Некоторые функции, которые не могут быть вычислены на машине Тьюринга, могут быть вычислены с использованием машины Зенона. Например, на ней может быть решена проблема остановки (что иллюстрируется следующим псевдокодом):
Будем использовать двуленточную машину Зенона. На одной ленте будем симулировать машину Тюринга, а на второй записывать результат.
записать 0 в первую ячейку на второй ленте
while true:
смоделировать очередной шаг работы данной машины Тьюринга на данном входе на первой ленте
if машина Тьюринга остановилась:
записать 1 в первую ячейку на ленте
break
return первую ячейку на второй ленте
Такие вычисления, выходящие за рамки возможности машины Тьюринга, называются гипервычислениями.
Замечание:
Стоит заметить, что проблема останова машины Зенона не может быть решена на самой машине Зенона. Хоть программы со счётным числом операций работают конечное время, всё равно программа на МЗ может зависнуть.
Пусть МЗ решает такую задачу: ей надо вывести все двоичные последовательности бесконечной длины.
Известно, что таких последовательностей — континуум.
А MЗ за бесконечное время выведет только не более чем счётное множество таких поиследовательностей, так как не более чем счётное объединение не более чем счётных множеств является не более чем счётным. Значит, МЗ может зависнуть. Поэтому для по аналогичным для МТ рассуждениям проблема останова для МЗ неразрешима.
Возможность супертьюринговых машин
Смысл двух приведенных ниже тезисов состоит в обосновании возможности сверхтьюринговых машин, способных осуществлять гипервычисления.
- Процесс может быть использован в математических целях, если и только если его поведение на входе/выходе:
- либо детерминистично, либо приблизительно детерминистично и вызываемая им ошибка может быть сведена к произвольно малой величине;
- определяется за конечное число шагов.
- Процесс может быть использован в его физических качествах, если и только если его поведение на входе/выходе в соответствии с научными данными может быть использовано для моделирования других специфических процессов.
Проекты супертьюринговых машин
Существует несколько десятков проектов супертьюринговых машин:
- попытка отказаться от линейности времени: оно замедляется, ускоряется, замыкается. Как известно из физики, такие процессы действительно существуют;
- делаются попытки использовать актуальную бесконечность: имеется в виду, что сумма бесконечного числа членов может иметь вполне определенное значение;
- самые большие надежды возлагаются на квантовые компьютеры. Чтобы осуществить вычисление, во-первых, необходимо управлять кубитами, во-вторых, дать реализоваться квантовому алгоритму, в-третьих, измерить состояния кубитов регистра. В принципиальном отношении все три операции осуществимы.