Вычислительная полнота¶

Вычислительная полнота (также тьюринг-полнота, от англ. Turing completeness) — свойство формальной системы или языка программирования, означающее, что она способна имитировать работу машины Тьюринга. Иными словами, система, обладающая вычислительной полнотой, может выполнить любой алгоритм, который в принципе может быть реализован на компьютере, при условии наличия достаточного количества памяти и времени.

Понятие вычислительной полноты является фундаментальным в теории вычислимости, информатике и математической логике. Оно позволяет классифицировать вычислительные системы по их выразительной силе и определять, какие задачи они могут решать.

¶История

¶Теоретические предпосылки

В 1936 году британский математик Алан Тьюринг в своей работе «О вычислимых числах, с приложением к проблеме разрешимости» (англ. On Computable Numbers, with an Application to the Entscheidungsproblem) ввёл понятие абстрактной вычислительной машины, впоследствии названной машиной Тьюринга. Эта машина представляет собой простейшее устройство, способное считывать и записывать символы на бесконечной ленте, следуя фиксированному набору правил. Тьюринг показал, что любая задача, которая может быть решена алгоритмически, может быть решена с помощью такой машины.

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

¶Развитие концепции

Термин «тьюринг-полнота» вошёл в обиход в середине XX века, когда начали появляться первые электронные вычислительные машины. В 1940-х годах Джон фон Нейман разработал архитектуру, которая лежит в основе большинства современных компьютеров. Архитектура фон Неймана, предусматривающая хранение программы и данных в одной памяти, оказалась тьюринг-полной, что подтверждает её универсальность.

В 1960-х годах, с развитием языков программирования, концепция вычислительной полноты стала применяться для их классификации. Было доказано, что большинство распространённых языков (C, Java, Python, Lisp и др.) являются тьюринг-полными. Это означает, что на них можно написать программу для решения любой вычислимой задачи, хотя на практике это может быть неэффективно или сложно.

¶Классификация и виды вычислительной полноты

¶Сильная и слабая тьюринг-полнота

Различают сильную и слабую тьюринг-полноту. Сильная тьюринг-полнота подразумевает, что система может имитировать машину Тьюринга без каких-либо ограничений по времени или памяти. Слабая тьюринг-полнота означает, что система может имитировать машину Тьюринга, но с некоторыми практическими ограничениями (например, конечный объём памяти). В реальных компьютерах память всегда конечна, поэтому они являются слабо тьюринг-полными. Однако с практической точки зрения это различие несущественно, так как объём памяти современных компьютеров достаточен для решения подавляющего большинства задач.

¶Неполные системы

Существуют системы, которые не являются тьюринг-полными. Они называются неполными или вычислительно ограниченными. К ним относятся, например, конечные автоматы, регулярные выражения (в классическом понимании), некоторые базы данных, а также многие языки разметки (HTML, CSS). Такие системы могут решать только определённый класс задач, но зато их выполнение часто проще анализировать, предсказывать и оптимизировать.

¶Характеристики и критерии

Для того чтобы система считалась тьюринг-полной, она должна обладать следующими возможностями:

1. Условное ветвление: возможность выполнять различные действия в зависимости от истинности некоторого условия (например, конструкция if-then-else).
2. Циклы: возможность повторять выполнение одного и того же блока кода неограниченное количество раз (например, циклы while, for или рекурсия).
3. Произвольный доступ к памяти: возможность читать и записывать данные в любую ячейку памяти (или на бесконечную ленту).
4. Базовые арифметические и логические операции: возможность выполнять сложение, вычитание, умножение, деление, сравнение и т.д.

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

¶Применение и значение

¶В языках программирования

Вычислительная полнота является ключевым критерием при разработке и выборе языка программирования. Большинство универсальных языков (C++, Java, Python, JavaScript, Go, Rust и др.) являются тьюринг-полными, что позволяет решать на них задачи любой сложности. Однако существуют и специализированные языки, которые не являются тьюринг-полными, например, SQL (Structured Query Language) для работы с реляционными базами данных или HTML для разметки веб-страниц. Они предназначены для решения конкретных задач и не требуют полной вычислительной мощности.

¶В теории вычислимости

Понятие вычислительной полноты используется для доказательства неразрешимости некоторых задач. Например, проблема остановки (определение, завершится ли программа за конечное время) является неразрешимой для тьюринг-полных систем. Это означает, что не существует алгоритма, который мог бы для любой программы и любых входных данных определить, завершится ли она.

¶В неожиданных областях

Вычислительная полнота была обнаружена в самых неожиданных системах, не связанных напрямую с компьютерами. Например:

• Игра «Жизнь» (Conway's Game of Life): клеточный автомат, придуманный Джоном Конвеем в 1970 году, оказался тьюринг-полным. Это было доказано в 1982 году, когда была построена конструкция, имитирующая машину Тьюринга.
• Magic: The Gathering: коллекционная карточная игра, в которой игроки используют карты с различными эффектами, оказалась тьюринг-полной. Это было доказано в 2019 году, когда была построена последовательность ходов, имитирующая работу машины Тьюринга.
• Minecraft: популярная компьютерная игра, в которой игроки могут строить различные механизмы из блоков, также является тьюринг-полной. В игре можно построить компьютер, который будет выполнять произвольные вычисления.
• Правило 110: одномерный клеточный автомат, предложенный Стивеном Вольфрамом, также является тьюринг-полным.

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

¶Критика и ограничения

Концепция вычислительной полноты не лишена критики. Основные замечания касаются её практической применимости. Тьюринг-полнота системы не гарантирует, что на ней можно эффективно решить любую задачу. Например, на языке Brainfuck, который является тьюринг-полным, написание даже простой программы может быть крайне трудоёмким. Кроме того, многие системы, которые являются тьюринг-полными, на практике не используются для решения сложных задач из-за своей неэффективности.

Другое ограничение связано с тем, что тьюринг-полнота системы не гарантирует её безопасности. Например, если язык разметки (например, HTML) становится тьюринг-полным, это может привести к возникновению уязвимостей, таких как выполнение произвольного кода. Поэтому в некоторых областях (например, в веб-разработке) сознательно ограничивают вычислительную мощность используемых языков, чтобы повысить безопасность.

¶Интересные факты

• Первый тьюринг-полный язык программирования: одним из первых тьюринг-полных языков считается Планкалкюль (Plankalkül), разработанный Конрадом Цузе в 1940-х годах, хотя он и не был реализован на практике.
• Самый маленький тьюринг-полный язык: существует множество эзотерических языков программирования, которые являются тьюринг-полными, но имеют минимальный набор команд. Например, язык Brainfuck состоит всего из 8 команд.
• Тьюринг-полнота в биологии: некоторые исследователи предполагают, что клеточные процессы, такие как транскрипция и трансляция, могут быть тьюринг-полными, что открывает возможности для создания биологических компьютеров.

¶Источники

• Тьюринг, А. М. (1936). On Computable Numbers, with an Application to the Entscheidungsproblem. Proceedings of the London Mathematical Society.
• Чёрч, А. (1936). An Unsolvable Problem of Elementary Number Theory. American Journal of Mathematics.
• Хопкрофт, Дж., Мотвани, Р., Ульман, Дж. (2001). Введение в теорию автоматов, языков и вычислений. Издательский дом «Вильямс».
• Вольфрам, С. (2002). A New Kind of Science. Wolfram Media.
• Дэвис, М. (2000). The Universal Computer: The Road from Leibniz to Turing. W. W. Norton & Company.