Теория вычислений

В теоретической информатике и математике теория вычислений — это раздел, который занимается тем, какие проблемы могут быть решены на модели вычислений, используя алгоритм , насколько эффективно они могут быть решены или в какой степени (например, приближенные решения по сравнению с точными). Область делится на три основных раздела: теория автоматов и формальных языков , теория вычислимости и теория вычислительной сложности , которые связаны вопросом: «Каковы основные возможности и ограничения компьютеров?». ^[1]

Для проведения строгого исследования вычислений специалисты по информатике работают с математической абстракцией компьютеров, называемой моделью вычислений . Существует несколько используемых моделей, но наиболее часто изучаемой является машина Тьюринга . ^[2] Специалисты по информатике изучают машину Тьюринга, потому что ее просто сформулировать, ее можно анализировать и использовать для доказательства результатов, а также потому, что она представляет собой то, что многие считают наиболее мощной возможной «разумной» моделью вычислений (см. тезис Чёрча–Тьюринга ). ^[3] Может показаться, что потенциально бесконечная емкость памяти является нереализуемым атрибутом, но любая разрешимая задача ^[4], решаемая машиной Тьюринга, всегда будет требовать только конечного объема памяти. Поэтому в принципе любая задача, которая может быть решена (решена) машиной Тьюринга, может быть решена компьютером, имеющим конечный объем памяти.

История

Теорию вычислений можно считать созданием моделей всех видов в области компьютерных наук. Поэтому используются математика и логика . В прошлом веке она отделилась от математики и стала самостоятельной академической дисциплиной со своими собственными конференциями, такими как FOCS в 1960 году и STOC в 1969 году, и своими собственными наградами, такими как IMU Abacus Medal (учреждена в 1981 году как премия Рольфа Неванлинны), премией Гёделя , учрежденной в 1993 году, и премией Кнута , учрежденной в 1996 году.

Пионерами теории вычислений были Рамон Луллий , Алонсо Чёрч , Курт Гёдель , Алан Тьюринг , Стивен Клини , Рожа Петер , Джон фон Нейман и Клод Шеннон .

Филиалы

Теория автоматов

Теория автоматов — это изучение абстрактных машин (или, точнее, абстрактных «математических» машин или систем) и вычислительных задач, которые могут быть решены с помощью этих машин. Эти абстрактные машины называются автоматами. Автоматы происходят от греческого слова (Αυτόματα), которое означает, что что-то делает что-то само по себе. Теория автоматов также тесно связана с формальной теорией языка, ^[5], поскольку автоматы часто классифицируются по классу формальных языков, которые они способны распознавать. Автомат может быть конечным представлением формального языка, который может быть бесконечным множеством. Автоматы используются в качестве теоретических моделей для вычислительных машин и используются для доказательств вычислимости.

Теория формального языка

Иерархия Хомского — Включения множеств, описанные иерархией Хомского

Теория языка — это раздел математики, занимающийся описанием языков как набора операций над алфавитом . Она тесно связана с теорией автоматов, поскольку автоматы используются для генерации и распознавания формальных языков. Существует несколько классов формальных языков, каждый из которых допускает более сложную спецификацию языка, чем предыдущий, т. е. иерархия Хомского ^[6] , и каждый соответствует классу автоматов, который его распознает. Поскольку автоматы используются в качестве моделей для вычислений, формальные языки являются предпочтительным способом спецификации для любой проблемы, которая должна быть вычислена .

Теория вычислимости

Теория вычислимости занимается в первую очередь вопросом о том, в какой степени проблема разрешима на компьютере. Утверждение о том, что проблема остановки не может быть решена машиной Тьюринга ^[7], является одним из важнейших результатов в теории вычислимости, поскольку это пример конкретной проблемы, которую легко сформулировать и невозможно решить с помощью машины Тьюринга. Большая часть теории вычислимости строится на результате проблемы остановки.

Другим важным шагом в теории вычислимости стала теорема Райса , которая утверждает, что для всех нетривиальных свойств частичных функций невозможно решить , вычисляет ли машина Тьюринга частичную функцию с этим свойством. ^[8]

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

Теория сложности вычислений

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

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

Чтобы упростить эту проблему, специалисты по информатике приняли нотацию Big O , которая позволяет сравнивать функции таким образом, что гарантирует, что не нужно учитывать конкретные аспекты конструкции машины, а только асимптотическое поведение по мере того, как проблемы становятся большими. Таким образом, в нашем предыдущем примере мы могли бы сказать, что проблема требует шагов для решения. $O(n)$

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

Модели вычислений

Помимо машины Тьюринга , используются и другие эквивалентные (см.: тезис Чёрча–Тьюринга ) модели вычислений.

Лямбда-исчисление: Вычисление состоит из начального лямбда-выражения (или двух, если вы хотите разделить функцию и ее входные данные) и конечной последовательности лямбда-терминов, каждый из которых выводится из предыдущего члена путем одного применения бета-редукции .
Комбинаторная логика: - это концепция, которая имеет много общего с -исчислением, но также существуют и важные различия (например, комбинатор с фиксированной точкой Y имеет нормальную форму в комбинаторной логике, но не в -исчислении). Комбинаторная логика была разработана с большими амбициями: понимание природы парадоксов, создание более экономичных основ математики (концептуально), устранение понятия переменных (тем самым проясняя их роль в математике). $\лямбда$ $\лямбда$
μ-рекурсивные функции: вычисление состоит из мю-рекурсивной функции, т. е. ее определяющей последовательности, любых входных значений и последовательности рекурсивных функций, появляющихся в определяющей последовательности с входами и выходами. Таким образом, если в определяющей последовательности рекурсивной функции появляются функции и , то могут появиться члены вида 'g(5)=7' или 'h(3,2)=10'. Каждая запись в этой последовательности должна быть применением базовой функции или следовать из записей выше с помощью композиции , примитивной рекурсии или μ-рекурсии . Например, если , то для появления 'f(5)=3' выше должны появиться члены типа 'g(5)=6' и 'h(5,6)=3'. Вычисление завершается только в том случае, если последний член дает значение рекурсивной функции, примененной к входам. $f(x)$ $g(x)$ $h(x,y)$ $f(x)=h(x,g(x))$
Алгоритм Маркова: система переписывания строк , использующая правила, подобные грамматике, для работы со строками символов.
Регистрационная машина: теоретически интересная идеализация компьютера. Существует несколько вариантов. В большинстве из них каждый регистр может хранить натуральное число (неограниченного размера), а инструкции просты (и немногочисленны), например, существуют только декрементация (в сочетании с условным переходом) и инкрементация (и остановка). Отсутствие бесконечного (или динамически растущего) внешнего хранилища (наблюдаемого в машинах Тьюринга) можно понять, заменив его роль методами нумерации Гёделя : тот факт, что каждый регистр хранит натуральное число, позволяет представить сложную вещь (например, последовательность или матрицу и т. д.) соответствующим образом огромным натуральным числом — однозначность как представления, так и интерпретации может быть установлена с помощью теоретических основ этих методов.

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

Различные модели вычислений способны выполнять различные задачи. Один из способов измерения мощности вычислительной модели — изучить класс формальных языков , которые может генерировать эта модель; таким образом получается иерархия языков Хомского .

Ссылки

^ Майкл Сипсер (2013). Введение в теорию вычислений 3-е . Cengage Learning. ISBN 978-1-133-18779-0. центральные области теории вычислений: автоматы, вычислимость и сложность. (Страница 1)
^ Ходжес, Эндрю (2012). Алан Тьюринг: Энигма (ред. The Centenary). Princeton University Press . ISBN 978-0-691-15564-7.
^ Рабин, Майкл О. (июнь 2012 г.). Тьюринг, Чёрч, Гёдель, Вычислимость, сложность и рандомизация: личный взгляд.
^ Дональд Монк (1976). Математическая логика . Springer-Verlag. ISBN 9780387901701.
^ Хопкрофт, Джон Э. и Джеффри Д. Ульман (2006). Введение в теорию автоматов, языки и вычисления. 3-е изд . Reading, MA: Addison-Wesley. ISBN 978-0-321-45536-9.
^ Иерархия Хомского (1956). «Три модели описания языка». Теория информации, Труды IRE на . 2 (3). IEEE: 113–124. doi :10.1109/TIT.1956.1056813. S2CID 19519474.
^ Алан Тьюринг (1937). «О вычислимых числах с приложением к Entscheidungsproblem». Труды Лондонского математического общества . 2 (42). IEEE: 230–265. doi :10.1112/plms/s2-42.1.230. S2CID 73712. Получено 6 января 2015 г.
^ Генри Гордон Райс (1953). «Классы рекурсивно перечислимых множеств и проблемы их принятия решений». Труды Американского математического общества . 74 (2). Американское математическое общество: 358–366. doi : 10.2307/1990888 . JSTOR 1990888.
^ Мартин Дэвис (2004). Неразрешимое: основные статьи о неразрешимых предложениях, неразрешимых проблемах и вычислимых функциях (Dover Ed) . Dover Publications. ISBN 978-0486432281.

Дальнейшее чтение

Учебники для компьютерных специалистов

(В этой области существует множество учебников; этот список по необходимости неполный.)

Хопкрофт, Джон Э. и Джеффри Д. Ульман (2006). Введение в теорию автоматов, языки и вычисления . 3-е изд. Чтение, Массачусетс: Addison-Wesley. ISBN 978-0-321-45536-9 Один из стандартных справочников в этой области.
Линц П. (2007). Введение в формальный язык и автоматы . Издательство Нароса. ISBN 9788173197819.
Майкл Сипсер (2013). Введение в теорию вычислений (3-е изд.). Cengage Learning. ISBN 978-1-133-18779-0.
Эйтан Гурари (1989). Введение в теорию вычислений. Computer Science Press. ISBN 0-7167-8182-4. Архивировано из оригинала 2007-01-07.
Хайн, Джеймс Л. (1996) Теория вычислений. Садбери, Массачусетс: Jones & Bartlett. ISBN 978-0-86720-497-1 Легкое введение в эту область, подходящее для студентов второго курса бакалавриата, изучающих компьютерные науки.
Тейлор, Р. Грегори (1998). Модели вычислений и формальные языки. Нью-Йорк: Oxford University Press. ISBN 978-0-19-510983-2 Необычайно легко читаемый учебник, подходящий для студентов старших курсов или начинающих аспирантов.
Льюис, ФД (2007). Основы теоретической информатики Учебник, охватывающий темы формальных языков, автоматов и грамматик. Акцент, по-видимому, делается на представлении обзора результатов и их приложений, а не на предоставлении доказательств результатов.
Мартин Дэвис , Рон Сигал, Элейн Дж. Вейукер, Вычислимость, сложность и языки: основы теоретической информатики , 2-е изд., Academic Press, 1994, ISBN 0-12-206382-1 . Охватывает более широкий круг тем, чем большинство других вводных книг, включая семантику программ и теорию квантификации . Рассчитана на аспирантов.

Книги по теории вычислимости с (более широкой) математической точки зрения

Хартли Роджерс-младший (1987). Теория рекурсивных функций и эффективная вычислимость , MIT Press. ISBN 0-262-68052-1
S. Barry Cooper (2004). Теория вычислимости . Chapman and Hall/CRC. ISBN 1-58488-237-9..
Карл Х. Смит , Рекурсивное введение в теорию вычислений , Springer, 1994, ISBN 0-387-94332-3 . Более короткий учебник, подходящий для аспирантов по информатике.

Историческая перспектива

Ричард Л. Эпштейн и Уолтер А. Карниелли (2000). Вычислимость: вычислимые функции, логика и основы математики, с Вычислимость: временная шкала (2-е изд.) . Wadsworth/Thomson Learning. ISBN 0-534-54644-7..

Внешние ссылки

Теория вычислений в Массачусетском технологическом институте
Теория вычислений в Гарварде
Computability Logic - Теория интерактивных вычислений. Основной веб-источник по этой теме.