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

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

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

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

История [ править ]

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

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

Филиалы [ править ]

Теория автоматов [ править ]

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

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

Теория формального языка [ править ]

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

Теория вычислимости [ править ]

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

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

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

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

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

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

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

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

Модели вычислений [ править ]

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

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

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

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

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

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

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

Алгоритм Маркова

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

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

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

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

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

Ссылки [ править ]

Дальнейшее чтение [ править ]

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

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

• Хопкрофт, Джон Э. и Джеффри Д. Ульман (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..

Внешние ссылки [ править ]

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