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

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

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

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

3 3
computer-science grammar automata finite-automata

3 ответа:

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

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

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

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

  1. Детерминированный Конечный Автомат
  2. недетерминированный Конечный автомат и их эквивалентность DFAs.
  3. регулярные языки и их эквивалентность DFAs.
  4. Нажимные Автоматы
  5. контекстно-свободные грамматики и их эквивалентность автоматам Pushdown.
  6. Иерархия Хомского
  7. Машины Тьюринга
Это должно обеспечить очень краткое введение в большинство вычислительных моделей, о которых говорят люди. 2: я бы рекомендовал хороший учебник по информатике (в моем курсе Uni я изучаю ВведениеSipser в теорию вычислений , что, на мой взгляд, очень хорошо). Другой подход, вероятно, был бы просто читать в Википедии. Вы действительно можете получить много миль из статей Википедии, Если вы знаете, что вы ищете и в каком порядке. Кроме того, если что-то неясно, вы обычно можете погуглить его и найти больше ресурсов по этой конкретной теме. В качестве отправной точки я бы рекомендуем ознакомиться со следующими темами (в указанном порядке): 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
2

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

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

3

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

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

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

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

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

Обратите внимание (наконец), что "эталонные" языки не устанавливают равенства. То есть, если ваша модель не может сравнить 2 унарных числа, это не означает, что она обязательно эквивалентна FSM, она может быть еще слабее. Языки только установят, что она больше чем у власти, или меньше, чем у власти.

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

1