Хорошие ресурсы для изучения моделей вычислений?

Question

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

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

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

Answer 1

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

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

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

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

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

Это должно дать очень краткое введение в большинство вычислительных моделей, о которых говорят люди. 2:Я бы порекомендовал хороший учебник по информатике (на курсе в университете я учусь в Введение Сипсера в теорию вычислений, что на мой взгляд очень хорошо).Другой подход, вероятно, заключался бы в том, чтобы просто прочитать Википедию.На самом деле вы можете получить большую пользу от статей Википедии, если знаете, что ищете и в каком порядке.Кроме того, если что-то неясно, вы обычно можете использовать 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 2

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

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

Answer 3

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

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

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

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

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

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

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