Гипервычисления
Гипервычисления или вычисления супер-Тьюринга относятся к моделям вычислений , которые могут давать выходные данные, не поддающиеся вычислению по Тьюрингу . Вычисления супер-Тьюринга, представленные в начале 1990-х Хавой Зигельманн, относятся к таким нейрологическим вдохновленным, биологическим и физическим вычислениям; Это стало математическим основанием непрерывного машинного обучения, новейшего направления искусственного интеллекта. Говорят, что гипервычисления, появившиеся как область науки в конце 1990-х годов, основаны на Супер Тьюринге, но также включают в себя философские конструкции. Например, машина, которая могла бы решить проблему остановки , была бы гиперкомпьютером; так же и тот, кто может правильно оценить каждое утверждениев арифметике Пеано .
Тезис Черча-Тьюринга утверждает, что любая «вычислимая» функция, которую может вычислить математик с ручкой и бумагой, используя конечный набор простых алгоритмов, может быть вычислена машиной Тьюринга. Гиперкомпьютеры вычисляют функции, которые машина Тьюринга не может вычислить и которые, следовательно, не вычислимы в смысле Черча-Тьюринга.
Технически выход случайной машины Тьюринга невычислим; однако большая часть литературы по гипервычислениям вместо этого фокусируется на вычислении детерминированных, а не случайных невычислимых функций.
Вычислительная модель, выходящая за рамки машин Тьюринга, была представлена Аланом Тьюрингом в его докторской диссертации 1938 года «Системы логики, основанной на порядковых числах» . [1] В этой статье исследовались математические системы, в которых был доступен оракул , который мог вычислить единственную произвольную (нерекурсивную) функцию от натуральных чисел до натуральных. Он использовал это устройство, чтобы доказать, что даже в этих более мощных системах все еще присутствует неразрешимость . Машины-оракулы Тьюринга представляют собой математические абстракции и физически не реализуемы. [2]
В некотором смысле большинство функций невычислимы: есть вычислимые функции, но существует несчетное количество ( ) возможных супер-тьюринговых функций. [3]
Модели гиперкомпьютеров варьируются от полезных, но, вероятно, неосуществимых (таких как оригинальные оракулы Тьюринга) до менее полезных генераторов случайных функций, которые более правдоподобно «реализуемы» (таких как случайная машина Тьюринга ).