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

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

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

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


computer-science grammar computation-theory finite-automata automata
person Chris    schedule 12.01.2010    source источник

Ответы (3)


arrow_upward
2
arrow_downward

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

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

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

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

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

Это должно стать очень кратким введением в большинство вычислительных моделей, о которых говорят люди. 2: я бы порекомендовал хороший учебник по информатике (в моем курсе Uni я изучаю Введение Сипсера в теорию вычислений , что, на мой взгляд, очень хорошо). Другой подход, вероятно, состоял бы в том, чтобы просто прочитать Википедию. Вы действительно можете извлечь большую пользу из статей Википедии, если знаете, что ищете и в каком порядке. Кроме того, если что-то неясно, вы обычно можете найти это в Google и найти дополнительные ресурсы по этой конкретной теме. В качестве отправной точки я бы рекомендовал прочитать следующие темы (в указанном порядке): 1. 1: https://rads.stackoverflow.com/amzn/click/com/0534950973

person Edan Maor    schedule 12.01.2010

arrow_upward
3
arrow_downward

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

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

person Christy John    schedule 12.01.2010

arrow_upward
1
arrow_downward

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

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

  • Если ваша модель может распознавать язык всех строк, в которых одинаковое количество букв А и В, то она как минимум более мощная, чем FSM.
  • Если это невозможно, то он может быть эквивалентен FSM.
  • Точно так же, если ваша модель может распознавать язык всех строк, в которых одинаковое количество букв А, В и С в строке, то она более эффективна, чем модель. CFG или КПК.

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

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

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

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

person agorenst    schedule 14.01.2010