Хорошие ресурсы, чтобы узнать о моделях вычислений?

Question

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

Во-первых, кто-нибудь может порекомендовать хороший ресурс для изучения различных моделей вычислений? Я интересуюсь грамматикой, языками и автоматами, и как доказать эквивалентность и различие между всеми ними. В идеале ресурс будет разбивать все элементы каждой модели очень подробно и сравнивать их.

Во-вторых, существует ли общий подход или структура, которую следует использовать при попытке приспособить систему к любой из этих вычислительных моделей?

Answer 1

Видеолекции по следующей ссылке дают хорошее введение в теорию вычислений. Это один из лучших ресурсов на эту тему.

Видеолекции профессора Шая Симонсона по теории вычислений

Answer 2

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

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

Конечно, это будет не так же хорошо, как настоящий учебник, но этоХорошее место для начала прямо сейчас , и это бесплатно.

В качестве отправной точки я бы рекомендовал прочитать следующие темы (в указанном порядке):

1. Детерминированный конечный автомат
2. Недетерминированный конечный автомат и их эквивалентность DFA.
3. Обычные языки ,и их эквивалентность DFA.
4. Автоматы Pushdown
5. Грамматики без контекста и эквивалентность автоматам Pushdown.
6. Иерархия Хомского
7. Машины Тьюринга

Это должно дать очень краткое введение в большинство вычислительных моделей, о которых говорят люди. 2 : я бы порекомендовал хороший учебник по информатике (В моем курсе Uni я учусь у Введение Сипсера в теорию вычислений , что, на мой взгляд, очень хорошо).Другой подход, вероятно, будет просто читать в Википедии.На самом деле вы можете получить много пользы от статей в Википедии, если знаете, что ищете и в каком порядке.Кроме того, если что-то неясно, вы можете найти его в Google и найти больше ресурсов по этой конкретной теме.Для начала я бы рекомендовал прочитать следующие темы (в указанном порядке): 1. 1 : http://www.amazon.com/Introduction-Theory-Computation-Second-Michael/dp/0534950973/ref=sr_1_1?ie=UTF8&s=books&qid=1263282346&sr=8-1

Answer 3

Более старый текст, который может быть трудно найти, - это «Введение в теорию автоматов, языки и вычисления» Хопкрофта и Уллмана.Есть несколько изданий - я слышал, что 79-й - лучший, поскольку он вносит наименьшее количество ударов при представлении сложных вещей.Это законный, хотя и небольшой учебник, и он представляет всю сферу, а не только то, что вы ищете.Я полагаю, что это может быть напрасной надеждой на то, что, возможно, одним из этих «хитрых» доказательств, которые опускают другие источники, может быть ваш ключ.

В качестве более удобной отправной точки есть несколько удобных «эталонных» языков.

• Если ваша модель может распознавать язык всех строк, в которых одинаковое количество символов As и B в строке, то она, по крайней мере, более мощная, чем FSM.
• Если это невозможно, то может быть эквивалентным FSM.
• Аналогично, если ваша модель может распознавать язык всех строк, где естьто же количество As, Bs и Cs в строке означает, что он на больше мощнее, чем CFG или PDA.

Эти "эталонные языки" на самом деле являются просто функциямизамаскированный --- первый в основном спрашивает, равны ли 2 одинарных числа, второй спрашивает, равны ли 3 одинарных числа.Они приятны и просты, и, как известно, выше или ниже возможностей конкретных моделей.Я не знаю простых для более сложных машин, поэтому вы можете быть сами по себе.

Обратите внимание, что для модели "LBA", линейно ограниченных автоматов, я считаю, что не существует известного естественного языка, которыйвычисляется с ТМ, но НЕ с LBA.Это утверждение взято из туманных воспоминаний, поэтому не принимайте его как формальное доказательство.:)

Обратите внимание (наконец), что языки "эталонных тестов" НЕ УСТАНАВЛИВАЮТ РАВЕНСТВО.То есть, если ваша модель не может сравнивать 2 одинарных числа, это означает, что не означает, что она обязательно эквивалентна FSM, она может быть еще слабее.Языки могут установить только то, что больше, чем у власти, или меньше, чем у власти.

На совершенно (полностью) другой дорожке книга Сипсера действительно доказывает эквивалентность между регулярными выражениями иFSM, а также между КПК и CFG.Я не уверен, насколько это будет полезно, поскольку вы достаточно расплывчаты в отношении той модели вычислений, которую вы рассматриваете, но если вы не уверены в эквивалентности, это может быть хорошей отправной точкой.