Сверхтьюринговые вычисления (гипервычисления) — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 1: Строка 1:
 
== Сверхтьюринговые вычисления ==
 
== Сверхтьюринговые вычисления ==
{{Определение
+
 
|definition =
+
'''Сверхтьюринговыми вычислениями''' (или '''гипервычислениями''' (англ. <tex>\it hypercomputation</tex>)) называются такие вычисления, которые не могут быть проделаны на машине Тьюринга
'''Сверхтьюринговыми вычислениями''' (или '''гипервычислениями''' (англ. hypercomputation)) называются такие вычисления, которые не могут быть проделаны на машине Тьюринга
 
 
, а следовательно не исчислимы в рамках тезисов Черча-Тьюринга.
 
, а следовательно не исчислимы в рамках тезисов Черча-Тьюринга.
}}
 
  
 
Такие гипотетические устройства Тьюрингом были рассмотрены еще в 1939 году.  
 
Такие гипотетические устройства Тьюрингом были рассмотрены еще в 1939 году.  
Строка 12: Строка 10:
 
ими же являются неразрешимыми. Это напоминает древний парадокс: может ли всемогущий бог создать камень,  
 
ими же являются неразрешимыми. Это напоминает древний парадокс: может ли всемогущий бог создать камень,  
 
который сам не сможет поднять?.. Поэтому даже если сверхтьюринговые вычисления физически реализуемы,  
 
который сам не сможет поднять?.. Поэтому даже если сверхтьюринговые вычисления физически реализуемы,  
для них также найдутся неразрешимые проблемы. Видимо, что-то не так с самой формой постановки этих проблем,
+
для них также найдутся неразрешимые проблемы.  
неразрешимых ни алгоритмически, ни божественно.
 
 
 
 
 
 
 
 
 
 
== Предполагаемые способы сверхтьюринговых вычислений: ==
 
== Предполагаемые способы сверхтьюринговых вычислений: ==
 
 
* Машина тьюринга которая может выполнить бесконечное число шагов.
 
* Машина тьюринга которая может выполнить бесконечное число шагов.
Один из математических способов - Машина Зенона.
+
Один из математических способов &mdash; Машина Зенона.
 
Машина Зенона выполняет свой первый шаг за <tex>1</tex> минуту, следующий шаг за <tex>1/2</tex> минуты, следующий за <tex>1/4</tex> и т.д.
 
Машина Зенона выполняет свой первый шаг за <tex>1</tex> минуту, следующий шаг за <tex>1/2</tex> минуты, следующий за <tex>1/4</tex> и т.д.
 
Суммируя <tex>1+1/2+1/4</tex> (геометрическая прогрессия) мы видим, что машина выполняет бесконечно количество шагов за 2 минуты.
 
Суммируя <tex>1+1/2+1/4</tex> (геометрическая прогрессия) мы видим, что машина выполняет бесконечно количество шагов за 2 минуты.
Строка 31: Строка 23:
 
гипервычисления, используя бесконечную точность.  
 
гипервычисления, используя бесконечную точность.  
 
Также она предложила модель, основанную на бесконечной эволюции нейронных сетей, способную проводить гипервычисления.
 
Также она предложила модель, основанную на бесконечной эволюции нейронных сетей, способную проводить гипервычисления.
 
 
*Техника, известная как неограниченный детерминизм, может позволять вычисление невычислимых функций. Это вопрос является предметом обсуждения в литературе.
 
*Техника, известная как неограниченный детерминизм, может позволять вычисление невычислимых функций. Это вопрос является предметом обсуждения в литературе.
 
 
*Использование замкнутых времениподобных кривых, вопреки распространённому мнению, не позволяет выполнять сверхтьюринговые вычисления, так как отсутствует бесконечный объём памяти.
 
*Использование замкнутых времениподобных кривых, вопреки распространённому мнению, не позволяет выполнять сверхтьюринговые вычисления, так как отсутствует бесконечный объём памяти.
 
 
 
== Машина Зенона ==
 
== Машина Зенона ==
 
{{Определение
 
{{Определение
 
|definition =
 
|definition =
'''Машина Зенона''' — это гипотетическая компьютерная модель, связанная с машиной Тьюринга, которая способна совершить счётное количество алгоритмических шагов за конечное время. В большинстве моделей вычислений такие машины не рассматриваются.
+
'''Машина Зенона''' <tex>\it (zeno </tex> <tex>\it machine) </tex> — это гипотетическая компьютерная модель, связанная с машиной Тьюринга, которая способна совершить счётное количество алгоритмических шагов за конечное время. В большинстве моделей вычислений такие машины не рассматриваются.
 
}}
 
}}
 
Теория точки Омега, разработанная Франком Типплером, верна, только если машина Зенона может существовать.
 
Теория точки Омега, разработанная Франком Типплером, верна, только если машина Зенона может существовать.
 
Некоторые функции, которые не могут быть вычислены на машине Тьюринга, могут быть вычислены с использованием машины Зенона. Например, на ней может быть решена проблема остановки (что иллюстрируется следующим псевдокодом):
 
Некоторые функции, которые не могут быть вычислены на машине Тьюринга, могут быть вычислены с использованием машины Зенона. Например, на ней может быть решена проблема остановки (что иллюстрируется следующим псевдокодом):
 
 
  '''начало программы'''  
 
  '''начало программы'''  
 
   записать 0 в первую ячейку на ленте;
 
   записать 0 в первую ячейку на ленте;
Строка 59: Строка 46:
 
Множится число исследователей, полагающих, что существуют процессы, требующие методов, которые не охвачены теорией Тьюринга.  
 
Множится число исследователей, полагающих, что существуют процессы, требующие методов, которые не охвачены теорией Тьюринга.  
 
Такова, в частности, позиция сторонников теории гиперкомпьютинга и, соответственно, гипервычислений, понимаемых как сверхтьюринговых.
 
Такова, в частности, позиция сторонников теории гиперкомпьютинга и, соответственно, гипервычислений, понимаемых как сверхтьюринговых.
 
 
Теоретическая разработка
 
Теоретическая разработка
 
 
* Процесс может быть использован в математических целях, если и только если его поведение на входе/выходе:
 
* Процесс может быть использован в математических целях, если и только если его поведение на входе/выходе:
 
** либо детерминистично, либо приблизительно детерминистично и вызываемая им ошибка может быть сведена к произвольно малой величине;
 
** либо детерминистично, либо приблизительно детерминистично и вызываемая им ошибка может быть сведена к произвольно малой величине;
 
** определяется за конечное число шагов.
 
** определяется за конечное число шагов.
 
* Процесс Р может быть использован в его физических качествах, если и только если его поведение на входе/выходе в соответствии с научными данными может быть использовано для моделирования других специфических процессов.
 
* Процесс Р может быть использован в его физических качествах, если и только если его поведение на входе/выходе в соответствии с научными данными может быть использовано для моделирования других специфических процессов.
 
 
Смысл двух приведенных выше тезисов состоит в обосновании возможности сверхтьюринговых машин, способных осуществлять гипервычисления.  
 
Смысл двух приведенных выше тезисов состоит в обосновании возможности сверхтьюринговых машин, способных осуществлять гипервычисления.  
 
 
== Проекты супертьюринговых машин ==
 
== Проекты супертьюринговых машин ==
 
Существует несколько десятков проектов супертьюринговых машин.  
 
Существует несколько десятков проектов супертьюринговых машин.  
Строка 75: Строка 58:
 
* Делаются попытки использовать актуальную бесконечность: имеется в виду, что сумма бесконечного числа членов может иметь вполне определенное значение.
 
* Делаются попытки использовать актуальную бесконечность: имеется в виду, что сумма бесконечного числа членов может иметь вполне определенное значение.
 
* Но самые большие надежды возлагаются на квантовые компьютеры. Чтобы осуществить вычисление, во-первых, необходимо управлять кубитами, во-вторых, дать реализоваться квантовому алгоритму, в-третьих, измерить состояния кубитов регистра. В принципиальном отношении все три операции осуществимы.
 
* Но самые большие надежды возлагаются на квантовые компьютеры. Чтобы осуществить вычисление, во-первых, необходимо управлять кубитами, во-вторых, дать реализоваться квантовому алгоритму, в-третьих, измерить состояния кубитов регистра. В принципиальном отношении все три операции осуществимы.
 
 
== Источники информации ==
 
== Источники информации ==
 
*[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| Машина Зенона]
 
 
[[Категория: Теория формальных языков]]
 
[[Категория: Теория формальных языков]]
 
[[Категория: Теория вычислимости]]
 
[[Категория: Теория вычислимости]]
 
[[Категория: Вычислительные формализмы]]
 
[[Категория: Вычислительные формализмы]]

Версия 22:22, 7 января 2015

Сверхтьюринговые вычисления

Сверхтьюринговыми вычислениями (или гипервычислениями (англ. [math]\it hypercomputation[/math])) называются такие вычисления, которые не могут быть проделаны на машине Тьюринга , а следовательно не исчислимы в рамках тезисов Черча-Тьюринга.

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

Предполагаемые способы сверхтьюринговых вычислений:

  • Машина тьюринга которая может выполнить бесконечное число шагов.

Один из математических способов — Машина Зенона. Машина Зенона выполняет свой первый шаг за [math]1[/math] минуту, следующий шаг за [math]1/2[/math] минуты, следующий за [math]1/4[/math] и т.д. Суммируя [math]1+1/2+1/4[/math] (геометрическая прогрессия) мы видим, что машина выполняет бесконечно количество шагов за 2 минуты.

  • Вечная машина Тьюринга это обобщение машина Зенона, которая может выполнить неопределенно продолжительное вычисление,

шаги в котором перенумерованы потенциально трансфинитными ординальными числами.

  • В 1994 Хава Сигельманн доказала, что ее новая вычислительная модель the Artificial Recurrent Neural Network (ARNN), может выполнить

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

  • Техника, известная как неограниченный детерминизм, может позволять вычисление невычислимых функций. Это вопрос является предметом обсуждения в литературе.
  • Использование замкнутых времениподобных кривых, вопреки распространённому мнению, не позволяет выполнять сверхтьюринговые вычисления, так как отсутствует бесконечный объём памяти.

Машина Зенона

Определение:
Машина Зенона [math]\it (zeno [/math] [math]\it machine) [/math] — это гипотетическая компьютерная модель, связанная с машиной Тьюринга, которая способна совершить счётное количество алгоритмических шагов за конечное время. В большинстве моделей вычислений такие машины не рассматриваются.

Теория точки Омега, разработанная Франком Типплером, верна, только если машина Зенона может существовать. Некоторые функции, которые не могут быть вычислены на машине Тьюринга, могут быть вычислены с использованием машины Зенона. Например, на ней может быть решена проблема остановки (что иллюстрируется следующим псевдокодом):

начало программы 
  записать 0 в первую ячейку на ленте;
  начало цикла
    смоделировать очередной шаг работы данной машины Тьюринга на данном входе;
    если машина Тьюринга остановилась, то записать 1 в первую ячейку на ленте и прервать цикл;
  конец цикла
конец программы

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

Возможность супертьюринговых машин

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

  • Процесс может быть использован в математических целях, если и только если его поведение на входе/выходе:
    • либо детерминистично, либо приблизительно детерминистично и вызываемая им ошибка может быть сведена к произвольно малой величине;
    • определяется за конечное число шагов.
  • Процесс Р может быть использован в его физических качествах, если и только если его поведение на входе/выходе в соответствии с научными данными может быть использовано для моделирования других специфических процессов.

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

Проекты супертьюринговых машин

Существует несколько десятков проектов супертьюринговых машин.

  • Ввод информации еще на стадии выполнения программы,
  • Попытка отказаться от линейности времени: оно замедляется, ускоряется, замыкается. Как известно из физики, такие процессы действительно существуют.
  • Делаются попытки использовать актуальную бесконечность: имеется в виду, что сумма бесконечного числа членов может иметь вполне определенное значение.
  • Но самые большие надежды возлагаются на квантовые компьютеры. Чтобы осуществить вычисление, во-первых, необходимо управлять кубитами, во-вторых, дать реализоваться квантовому алгоритму, в-третьих, измерить состояния кубитов регистра. В принципиальном отношении все три операции осуществимы.

Источники информации