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

Не путать с вычислительной теорией разума .

Информацию о журнале см. в разделе «Теория вычислений» .

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

Чтобы провести тщательное исследование вычислений, ученые-компьютерщики работают с математической абстракцией компьютеров, называемой моделью вычислений . Используется несколько моделей, но наиболее часто исследуемой является машина Тьюринга . Ученые-компьютерщики изучают машину Тьюринга, потому что ее легко сформулировать, ее можно анализировать и использовать для доказательства результатов, а также потому, что она представляет собой то, что многие считают самой мощной из возможных «разумных» моделей вычислений (см. тезис Черча-Тьюринга ). Может показаться, что потенциально бесконечный объем памяти — нереализуемый атрибут, но любая разрешимая проблема для решения с помощью машины Тьюринга всегда потребуется лишь ограниченный объем памяти. Так что в принципе любая задача, которую может решить (решить) машина Тьюринга, может быть решена и компьютером, имеющим конечный объём памяти.

История

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

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

Филиалы

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

Основная статья: Теория автоматов

Грамматика	Языки	Автомат	Продукционные правила (ограничения)
Тип-0	Рекурсивно перечислимый	Машина Тьюринга	$\alpha \rightarrow \beta$ (без ограничений)
Тип-1	Контекстно-зависимый	Линейно-ограниченная недетерминированная машина Тьюринга	$\alpha A\beta \rightarrow \alpha \gamma \beta$
Тип-2	Контекстно-свободный	Недетерминированный автомат с выталкиванием	$A\rightarrow \gamma$
Тип-3	Обычный	Конечный автомат	$A\rightarrow a$ и $A\rightarrow aB$

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

Теория

Основная статья: Формальный язык

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

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

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

Основная статья: Теория вычислимости

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

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

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

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

Основная статья: Теория сложности вычислений

Представление связи между классами сложности

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

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

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

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

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

Основная статья: Модель вычислений

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

Лямбда-исчисление

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

Комбинаторная логика

это концепция, имеющая много общего с $\lambda$-исчислении, но существуют и важные различия (например, комбинатор Y с фиксированной точкой имеет нормальную форму в комбинаторной логике, но не в $\lambda$-исчисление). Комбинаторная логика разрабатывалась с большими амбициями: понять природу парадоксов, сделать основы математики более экономичными (концептуально), исключить понятие переменных (таким образом, прояснив их роль в математике).

μ-рекурсивные функции

Вычисление состоит из мю-рекурсивной функции, т.е. ее определяющей последовательности, любого входного значения(й) и последовательности рекурсивных функций, появляющихся в определяющей последовательности с входными и выходными данными. Таким образом, если в определяющей последовательности рекурсивной функции $f(x)$ функции $g(x)$ и $h(x,y)$ появляются, то могут появиться члены вида «g(5)=7» или «h(3,2)=10». Каждая запись в этой последовательности должна быть применением базовой функции или следовать из записей выше с использованием композиции , примитивной рекурсии или µ-рекурсии . Например, если $f(x)=h(x,g(x))$, то для появления 'f(5)=3' выше должны встречаться такие термины, как 'g(5)=6' и 'h(5,6)=3'. Вычисление завершается только в том случае, если последний член дает значение рекурсивной функции, примененной к входным данным.

Markov algorithm

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

Зарегистрировать машину

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

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

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

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

Учебники для компьютерщиков

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

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

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

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

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

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

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

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