Тезис Чёрча-Тьюринга

В этой заметке существенно используются идеи и фразы (местами) следующей статьи

Сверхтьюринговые вычисления и гиперкомпьютеры. Тезис Чёрча-Тьюринга как универсальный предел познания. https://habr.com/ru/articles/961020/

"В 1936 г. Алонзо Чёрч и Алан Тьюринг сформулировали классический тезис Чёрча-Тьюринга, согласно которому любая функция, которую мы интуитивно считаем вычислимой, может быть вычислена машиной Тьюринга. Под «интуитивно вычислимой» они подразумевали функцию, которую математик может вычислить с помощью ручки и бумаги, используя конечный набор простых алгоритмов. И наоборот, функция над натуральными числами может быть вычислена человеком, следующим алгоритму, тогда и только тогда, когда она вычислима машиной Тьюринга".

Тезис Чёрча (часто называемый тезисом Чёрча — Тьюринга) — это фундаментальный принцип в теории вычислимости, который утверждает следующее:

Класс функций, вычислимых с помощью алгоритмов в интуитивном смысле, совпадает с классом частично рекурсивных функций (или, что эквивалентно, с классом функций, вычислимых на машине Тьюринга).

Основные положения тезиса Чёрча

• Интуитивная вычислимость: это те функции, которые человек мог бы вычислить с помощью ручки и бумаги, следуя чёткому алгоритму.
• Формальная вычислимость: функции, которые можно вычислить с помощью строго определённых математических моделей — частично рекурсивных функций или машины Тьюринга.
• Эквивалентность: все известные формальные модели вычислений (λ-исчисление Чёрча, машина Тьюринга, рекурсивные функции) имеют одинаковую вычислительную мощность.

Значение тезиса для математики

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

Тезис Чёрча — фундаментальная основа понимания того, что такое вычисление и каковы пределы возможностей алгоритмов и компьютеров.

Тезис Чёрча — Тьюринга лежит в основе всей современной информатики и теории алгоритмов.

Он утверждает, что если задача может быть решена каким-либо алгоритмом, то её можно решить и на машине Тьюринга (или эквивалентной системе). Тезис Чёрча-Тьюринга установил эквивалентность математики и компьютера, а также других вычислительных машин. А также, всё, что в принципе вычислимо, может быть смоделировано машиной Тьюринга.

Этот тезис не доказывается формально, а принимается как естественнонаучный факт, подтверждаемый всей историей математики и компьютерных наук.

Из книги Манин Ю.И. Математика как метафора.

"Такая «открытость» категории, рассматриваемой с точностью до эквивалентности, является существенной, например, для абстрактной теории вычислимости. Тезис Чёрча лучше всего понимать как постулат, согласно которому существует открытая категория «конструктивных миров» – конечных или счетных множеств со структурой и вычислимых морфизмов между ними, – в которой всякий бесконечный объект изоморфен миру натуральных чисел, а морфизмы соответствуют рекурсивным функциям. Существует очень много других интересных бесконечных конструктивных миров, задаваемых с помощью самых разнообразных внутренних структур: слова над данным алфавитом, конечные графы, машины Тьюринга и т. д. Все они, однако, изоморфны ввиду существования вычислимых нумераций".

Значение тезиса Чёрча-Тюринга "за пределами" математики.

В качестве контекста можно рассмотреть такой набор "метафизических" вопросов (вопросы взятяы из статьи):

• Что делает Вселенную познаваемой?
• Почему работает научный метод?
• Всё, с чем мы имеем дело в ощущениях, является симуляцией, сгенерированной мозгом. Всё, что нам известно о мире – продукты нашего разума. Не означает ли это, что мы никогда не сможем узнать, какова реальность на самом деле?
• Откуда мы знаем, что законы физики универсальны и постижимы человеческим разумом?
• Где гарантия, что законы физики изотропны в пространстве и однородны во времени? Может, они варьируются от места к месту, изменялись в прошлом или изменятся в будущем?
• Существует ли вычислительно более мощный компьютер, чем машина Тьюринга?
• Вычислима ли каждая физическая система?
• Является ли сама Вселенная вычислительной машиной?
• Каковы фундаментальные физические и логические ограничения на то, что может быть вычислено и постигнуто?
• Есть ли вычислительный барьер, который невозможно преодолеть, независимо от того, насколько далеко и какими способами развиваются компьютеры? 
• Или новые типы оборудования, основанные на квантовых, релятивистских или квантово-гравитационных явлениях, могут привести к принципиально новым вычислительным парадигмам и сделать невычислимое вычислимым?

"Первым, кто увидел в тезисе Чёрча-Тьюринга физический смысл, был биолог-теоретик Роберт Розен. Он переформулировал тезис как утверждение о невозможности определённого класса физических процессов и предположил, что ограничения в вычислениях объясняют факты о природе, однако на его работу никто не обратил внимания. В 1985 г. Дэвид Дойч в статье «Квантовая теория, принцип Чёрча-Тьюринга и универсальный квантовый компьютер» предложил считать тезис Чёрча-Тьюринга физическим принципом": 

«Я предлагаю переосмыслить «функции Тьюринга, которые естественным образом считались бы вычислимыми» как функции, которые в принципе могут быть вычислены реальной физической системой. Ибо, конечно, было бы трудно считать функцию «естественно» вычислимой, если бы её нельзя было вычислить в Природе, и наоборот». 

В той же статье был сформулирован тезис Чёрча-Тьюринга-Дойча: 

«Каждая конечно реализуемая физическая система может быть идеально смоделирована универсальной модельной вычислительной машиной, действующей конечными средствами». 

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

* * *

Казалось бы, вывод Дойча ограничивает как реальность, так и познаваемость. Но имеются контаргументы. Определение физической реальности неявно определена как вычислимость и получаем логический (порочный) круг. Если расширить физическую реальность запредельным по отношению вычислимости, то встает вопрос о познаваемости такой запредельности. Человек - как физическое существо оперирует невычислительными объектами. Например, натуральный ряд, или более обще, бесконечное счетное множество не вычислимо. Невычислимо и иррациональное действительное число. Но человек оперирует этими объектами. Сам человек без сомнения объект физической реальности. И тут встает вопрос о идеальном (мысли) отношении идеального к физической реальности. И расширении физической реальности.

Такой ход, - расширение, - проделан в математике по отношению к теоремам Гёделя касательно аксиоматической теории арифметики. А именно как расширение стандартной модели арифметики. 

Иная точка зрения изложена в книге "Большое, малое и человеческий разум" Роджером Пенроузом. В ней представлена "устройство" совершенно новой физики, основанной на идее невычислимости некоторых операций и объективного восстановления волновых функций. Возможно, эта идея позволит созадать физическую теорию нового типа для которой тезис Дейча будет лишь частным случаем.

* * *

Примечание. О определенных видах машин Тьюринга.

Недетерминированная машина Тьюринга (NTM) – это машина Тьюринга, в которой функция перехода приводит к более чем одному выбору, а выбор осуществляется вероятностным образом (подбрасыванием монетки). В отличие от детерминированной машины Тьюринга, которая имеет единственный «путь вычислений», недетерминированная машина имеет «дерево вычислений» (в общем случае — экспоненциальное число путей). Строка принимается, если она принимается хотя бы в одной из ветвей, и отвергается, только если ни одна из ветвей её не принимает. Можно считать, что недетерминированная машина Тьюринга использует параллельные процессоры для вычислений, поскольку на каждом вычислительном шаге она может перейти в несколько состояний, а не только в одно. Вычисление завершается, когда все возможные ветви вычислений находятся в состоянии остановки. Недетерминированная машина Тьюринга быстрее решает NP-задачи, хотя детерминированная машина Тьюринга может моделировать недетерминированную, не занимая существенно больше места, но может использовать существенно больше времени.

Вероятностная машина Тьюринга (PTM), случайная машина Тьюринга (RTM) или машина Тьюринга, подверженная ошибкам (FTM). Это разновидности детерминированной машины Тьюринга, имеющие дополнительный аппаратный источник случайных битов, любое число которых они могут «заказать», загрузить на отдельную ленту и потом использовать в вычислениях. Вероятностная машина на каждом шаге может делать случайный выбор между несколькими переходами с заданной вероятностью, случайная машина выбирает следующее состояние при каждом переходе с равной вероятностью, а подверженная ошибкам моделирует ненадёжное вычисление в условиях аппаратных сбоев и шумов. Однако ни истинная квантовая случайность, ни детерминированная псевдослучайность не делают невычислимые задачи вычислимыми. Генератор случайных чисел в качестве источника входных данных может создавать случайные невычислимые функции или помогать угадывать правильное решение, но не даёт гарантированных ответов на неразрешимые проблемы.