Введение в теорию вычислимости и сложности

Вы когда-нибудь задумывались: что это за устройство, на котором вы читаете эту статью? Что такое компьютер?

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

Но есть ли у этих компьютеров, обладающих бесконечным потенциалом, какие-то ограничения? Существуют ли проблемы, для решения которых нельзя использовать компьютеры?

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

Абстрактное представление о вычислениях дает результаты, которые выдержали испытание временем и сегодня так же ценны для нас, как и в начале 1970-х годов.

Вычислимость

Что такое компьютер? Что такое проблема?

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

Функция — это процедура, которую вы применяете к входу x, чтобы найти выход f(x).

Оказывается, математическое определение другое:

Функция — это набор упорядоченных пар, где первый элемент каждой пары принадлежит множеству X (называемому доменом), второй элемент каждой пары — набору Y (называемому кодоменом или диапазоном), а каждый элемент домен связан ровно с одним элементом диапазона.

Это было довольно много. Но что именно это означает?

Это определение говорит нам, что компьютер — это машина для вычисления функций.

Почему?

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

Однако математическое определение позволяет нам прийти к интересным выводам, таким как существование невычислимых функций (т. е. неразрешимых задач):

Потому что не всякую функцию можно описать как алгоритм.

Правила игры

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

Мы будем называть ввод алфавитом машины; то есть набор строк символов из некоторого конечного набора. Например, алфавит машины может быть двоичным (0 и 1) или набором символов ASCII. Любая конечная последовательность символов представляет собой строку, например «0110».

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

Учитывая эти параметры, важно охарактеризовать еще один тип: набор строк. Может быть, нас интересует набор строк, которые принимает какая-то машина, или, может быть, мы строим машину, которая принимает строки из определенного набора и никакие другие, или, может быть, мы спрашиваем, возможно ли вообще спроектировать машину, которая принимает все в некотором наборе. конкретный набор и никакие другие.

Во всех этих случаях набор строк называется языком — например, набор всех двоичных строк, представляющих четные числа, или набор строк с четным числом символов. Оказывается, с языками, как и с числами, можно работать с такими операторами, как конкатенация, объединение, пересечение и т.п.

Одним из важных операторов является оператор звезды Клини, который также используется с регулярными выражениями. Это можно рассматривать как объединение всех возможных возможностей языка. Например, если наш язык A представляет собой набор строк {'01', '1'}, то один элемент A* является строкой '0101111'.

счетность

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

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

В этот момент вы можете подумать: «Бесконечность сама по себе достаточно странная идея; теперь мне придется иметь дело с двумя из них!»

Ну, это не так уж плохо. Счетно бесконечное множество — это множество, которое можно перечислить. Можно сказать, что это первый элемент, это второй элемент и так далее, в конечном итоге присваивая номер каждому элементу множества. Возьмем, к примеру, набор четных чисел. Можно сказать, что 2 — это первое, 4 — второе, 6 — третье и так далее. Такие множества счетно бесконечны или счетны.

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

Счетное множество программ

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

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

Чтобы повторить:

Множество всех строк в любом алфавите (например, множество всех компьютерных программ) счетно.

Неисчислимо много языков

Учитывая этот вывод, как насчет подмножеств этих строк? Спросили по-другому, а как насчет множества всех языков? Оказывается, это множество несчетно.

Множество всех языков любого алфавита несчетно.

Опять же, мы не приводим здесь доказательство.

Последствия

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

Почему?

Предположим, что A — набор символов ASCII; Символы ASCII — это как раз те символы, которые необходимы для составления компьютерной программы. Мы видим, что набор строк, представляющих, скажем, программы на JavaScript, является подмножеством A* (здесь * — оператор звездочки Клини). Выбор JavaScript произволен. Поскольку это множество программ является подмножеством счетного множества, мы имеем, что множество программ JavaScript счетно.

Кроме того, давайте рассмотрим, что для любого языка L мы можем определить некоторую функцию f , которая возвращает 1, если некоторая строка x находится в L , и 0 в противном случае. Все такие функции различны. Поскольку существует соответствие 1:1 с множеством всех языков и поскольку множество всех языков несчетно, мы имеем, что множество всех таких функций несчетно.

Вот глубинный момент:

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

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

Теперь возникает вопрос: «Как выглядят эти проблемы?» Прежде чем мы продолжим описывать такие проблемы, мы должны сначала смоделировать вычисления в обобщенном виде.

Машины Тьюринга

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

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

• Текущий символ под головой и

• Внутреннее состояние машины, которое также обновляется по мере написания символа

Вот и все.

Универсальность

В 1926 году Алан Тьюринг не только разработал машину Тьюринга, но и получил ряд других важных сведений о природе вычислений, когда написал свою знаменитую статью «О вычислимых числах». Он понял, что сама компьютерная программа может считаться входными данными для компьютера. С этой точки зрения у него появилась прекрасная идея, что машина Тьюринга может имитировать или выполнять этот ввод.

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

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

Прежде чем мы продолжим, давайте рассмотрим важный момент: мы знаем, что машина Тьюринга — это модель вычислений, но достаточно ли она универсальна? Чтобы ответить на этот вопрос, мы обратимся к тезису Черча-Тьюринга, который подтверждает следующее утверждение:

Все, что можно вычислить, можно вычислить на машине Тьюринга.

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

Узнаваемость и разрешимость

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

Язык узнаваем, если существует машина Тьюринга, которая его распознает.

а также

Язык разрешим, если существует машина Тьюринга, которая решает его.

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

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

Неразрешимость

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

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

Мы можем доказать это с помощью машины Тьюринга. Машины Тьюринга можно описать как струны, поэтому их существует счетное количество. Предположим, что M ₁ , M ₂ и так далее составляют множество всех машин Тьюринга. Определим следующую функцию:

Здесь <M> — это синтаксис для «строкового кодирования M», и эта функция представляет проблему вывода 1, если M _i останавливается, принимая M _j в качестве входных данных, и выводя 0 в противном случае. Обратите внимание, что M _i должен остановиться (т.е. быть решающим). Это необходимо, поскольку мы хотим описать неразрешимую функцию (т. е. неразрешимую задачу).

Теперь давайте также определим язык L , состоящий из строковых кодировок машин Тьюринга, которые НЕ принимают собственные описания:

Например, одна машина M ₁ может выдать 0 на входе <M ₁ >, а другая машина M ₂ может выдать 1 на входе <M ₂ >. Чтобы доказать, что этот язык неразрешим, мы спросим, ​​что ML, машина, определяющая язык _L , делает, когда ей дается собственное описание < _ML > в качестве входных данных. Есть две возможности:

M _L принимает <M _L >

или

M _L отклоняет <M _L >

Если ML принимает собственную кодировку, то это означает, что < _ML > не на языке _L ; однако, если бы это было так, то _ML вообще не должен был принимать его кодировку. С другой стороны, если ML не принимает собственную кодировку, то < _ML > находится на языке _L , поэтому _ML должен был принять свою строковую кодировку.

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

Проблема с остановкой

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

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

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

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

Резюме

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

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

Оставив позади вычислимые функции и языки, мы теперь обсудим сложность вычислений, обзор эффективности вычислений и известную проблему P vs. NP.

Сложность

Медленный против быстрого

Ученые-компьютерщики различают множество классов задач, и два интересующих нас класса включают задачи, которые компьютеры могут решать быстро и эффективно, известные как P , и задачи, решения которых можно быстро проверить, но не могут быть быстро получены, известные как NP .

Например, предположим, что вы отвечаете за разработку алгоритмов для службы онлайн-знакомств, и кто-то задает вопрос: «Все ли могут найти свидание?» Ответ сводится к объединению совместимых людей в пары таким образом, чтобы все были в паре. Оказывается, существуют эффективные алгоритмы для решения этой проблемы. Эта задача находится в множестве P .

Ну, а что, если мы хотим определить самую большую клику среди наших пользователей? Под кликой мы подразумеваем самую большую сеть людей, которые все совместимы друг с другом. Когда количество пользователей невелико, эта проблема может быть решена быстро. Мы можем легко идентифицировать, скажем, клику с 3 пользователями. Однако по мере того, как мы начинаем искать более крупные клики, решить проблему становится все труднее и труднее. Эта задача входит в набор NP .

Формальные определения

P — множество задач, решаемых за полиномиальное время. То есть количество вычислительных шагов ограничено полиномиальной функцией от размера задачи. Мы знаем, что вопрос «Все ли могут назначить свидание?» вопрос, также известный как проблема двудольного сопоставления, находится в P .

NP — это множество задач, проверяемых за полиномиальное время. Это включает, конечно, все проблемы в P; однако мы не знаем, является ли это ограничение строгим. Мы знаем о проблемах, которые эффективно проверяемы, но не эффективно решаемы, но мы не знаем, действительно ли эта проблема неразрешима. Проблема клики — одна из таких проблем. Мы знаем, что можем эффективно проверить решение, но мы не знаем наверняка, сможем ли мы эффективно решить проблему.

Наконец, NP-complete — это набор задач, которые являются самыми сложными в NP . Их называют самыми сложными, потому что любая проблема в NP может быть эффективно преобразована в NPC . В результате, если бы кто-то нашел эффективное решение проблемы в NPC , то весь класс NP был бы поглощен P. Проблема клики есть и в NPC .

Таким образом, мы приходим к проблеме P против NP . Многие ученые-компьютерщики и математики твердо убеждены, что P и NP не равны. Если бы они были, последствия были бы более глубокими. Большая часть современной цифровой инфраструктуры опирается на тот факт, что в NP есть проблемы, которых нет в P. Если бы это было не так, то криптографические методы, например, рухнули бы в одночасье, позволив человеку, обладающему эффективным решением проблемы NPC , подорвать даже самые строгие протоколы безопасности.

Тонкости сговорчивости

Новичкам в информатике разница между задачами на сопоставление и клики может показаться не такой уж большой. На самом деле разница между проблемой в P и проблемой в NP может быть очень тонкой. Способность заметить разницу важна для любого, кто разрабатывает алгоритмы в реальном мире.

Рассмотрим задачу о кратчайшем пути. Учитывая два местоположения, цель состоит в том, чтобы определить кратчайший путь между ними. iPhone вычисляет это за миллисекунды. Это вычислительно решаемая задача.

С другой стороны, рассмотрим задачу коммивояжера, где цель состоит в том, чтобы посетить подмножество возможных пунктов назначения, заканчивающихся в исходной точке, преодолевая при этом кратчайшее расстояние. Эта задача похожа на задачу о кратчайшем пути, но является NP-полной; это также объясняет, почему логистика цепочек поставок — это индустрия с оборотом в миллиарды долларов.

На самом деле мы можем быть еще тоньше. Вместо запроса кратчайшего пути (P) мы можем запросить самый длинный путь без циклов. Оказывается, задача о самом длинном пути также является NP-полной.

Есть еще много примеров этого тонкого различия, включая идентификацию покрытия вершин в двудольных и общих графах или выполнение логических формул с двумя или тремя литералами в предложении. Дело в том, что не сразу становится очевидным, находится ли проблема в P или NP, и именно поэтому анализ времени выполнения является важным навыком. Если алгоритм, который необходимо разработать, предназначен для задачи в P, то мы знаем, что существует эффективное решение. С другой стороны, если проблема находится в NP, то у нас есть веские аргументы против поиска решения, потому что алгоритм, как правило, просто займет слишком много времени для решения проблемы.

Резюме

В этом исследовании сложности мы определили классы задач P и NP. P неформально представляет проблемы, которые могут быть эффективно решены компьютером, в то время как NP представляет те, которые можно эффективно проверить.

Никто не смог доказать, что P не равно NP. Эквивалентны ли эти два класса задач, известно как проблема P и NP, и это самая важная открытая проблема в теоретической информатике на сегодняшний день, если не во всей математике. Фактически, в 2000 году Математический институт Клэя назвал проблему P против NP одним из семи наиболее важных открытых вопросов в математике и предложил награду в миллион долларов за доказательство, определяющее решение этой проблемы.

Заключение

В этой статье мы углубились в области вычислимости и сложности, отвечая на важные вопросы, такие как «Что такое компьютер?» Хотя детали могут быть ошеломляющими, есть ряд важных выводов, о которых стоит помнить:

• Есть вещи, которые просто невозможно вычислить, например, проблему остановки.

• Есть некоторые вещи, которые невозможно эффективно вычислить, например, проблемы в NPC.

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

Дальнейшее чтение в блоге Toptal Engineering:

• Как подойти к написанию интерпретатора с нуля