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

редактировать

Академическое подразделение информатики

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

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

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

Содержание

1 История
2 Ветви
- 2.1 Теория автоматов
  - 2.1.1 Теория формального языка
- 2.2 Теория вычислимости
- 2.3 Теория сложности вычислений
3 Модели вычислений
4 Ссылки
5 Дополнительная литература
6 Внешние ссылки

История

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

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

Ветви

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Литература

Дополнительная литература

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

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

Хопкрофт, Джон Э.. и Джеффри Д. Уллман (2006). Введение в теорию автоматов, языки и вычисления. 3-е изд. Рединг, Массачусетс: Эддисон-Уэсли. ISBN 978-0-321-45536-9 Одна из стандартных ссылок в данной области.
. Введение в формальный язык и автоматы. Издательство Нароса. ISBN 9788173197819.
Майкл Сипсер (2013). Введение в теорию вычислений (3-е изд.). Cengage Learning. ISBN 978-1-133-18779-0.
(1989). Введение в теорию вычислений. Computer Science Press. ISBN 0-7167-8182-4. Архивировано из оригинала 07.01.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-е изд.). Wadsworth / Thomson Learning. ISBN 0-534-54644-7..

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

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