Теория вычислений - Theory of computation

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

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

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

История

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

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

ветви

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

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

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

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

Набор включений, описываемых иерархией Хомского

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Марковский алгоритм

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

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

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

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

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

использованная литература

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

Учебники для информатиков

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

• Хопкрофт, Джон Э. и Джеффри Д. Ульман (2006). Введение в теорию автоматов, языки и вычисления . 3-е изд. Рединг, Массачусетс: Эддисон-Уэсли. ISBN  978-0-321-45536-9 Одна из стандартных ссылок в этой области.
• Линц P . Введение в формальный язык и автоматы . Издательство Нароса. 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) Теория вычислений. Садбери, Массачусетс: Джонс и Бартлетт. 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-е изд.) . Wadsworth / Thomson Learning. ISBN 0-534-54644-7..

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

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