Научная литература
booksshare.net -> Добавить материал -> Лингвистика -> Гросс М. -> "Теория формальных грамматик " -> 21

Теория формальных грамматик - Гросс М.

Гросс М., Лантен А. Теория формальных грамматик — М.: Мир, 1971. — 296 c.
Скачать (прямая ссылка): teoriyaformalnihgrammatik1971.djvu
Предыдущая << 1 .. 15 16 17 18 19 20 < 21 > 22 23 24 25 26 27 .. 101 >> Следующая


3.4.3. Разрешимость в комбинаторных системах

Используя гёделевскую нумерацию1) и вводя необходимые предикаты, можно доказать, что множество теорем любой комбинаторной системы рекурсивно перечислимо.

Это свойство еще не позволяет для конкретной системы сказать, является ли множество ее теорем рекурсивным; если же это так, система называется разрешимой.

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

3.4.4. Упражнения

1. Что можно сказать о (S+) в следующих случаях: система (S) является полутуэвской, туэвской, нормальной, системой Поста?

2. Найти более экономный способ кодирования, нежели

а+ = 10г+11,

показав, что не обязательно иметь два маркера.

3. Закодируем алфавит {а, Ь, с, d] следующим образом: а —» ->0, b -> 10, с->110, d-*-lll. Необходим ли символ-разделитель? Ответить на этот же вопрос при кодировках а—>-00, Ь-*01, с-+10, d-*ll и а —> 0, b —> 1, с —> 10, d —> 11.

') О гёделевской нумерации см. ниже § 5.3. — Прим. перев. Глава IV АЛГОРИТМЫ. МАШИНЫ ТЬЮРИНГА

§ 4.1. АЛГОРИТМЫ

4.1.1. Понятие алгоритма1)

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

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

Пример 1. Дифференцирование многочлена.

(1) Взять очередной член многочлена; если такового уже не осталось, написать «конец» и остановиться.

(2) Взять показатель степени переменной данного члена и

(2.1) умножить его на коэффициент; сделать это произведение коэффициентом при новом члене;

(2.2) уменьшить его на 1 и сделать показателем степени при новом члене.

(3) Вернуться к (1).

Пример 2. Поиск слова в двуязычном (переводном) словаре.

(1) Взять первую букву искомого слова и найти тот раздел словаря, первое слово которого начинается этой буквой.

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

(3) Начиная с найденной страницы, просматривать подряд все слова, сравнивая их с искомым словом до тех пор, пока либо будет получено совпадение («искомое слово найдено»), либо мы дойдем до слова, не начинающегося на три буквы, выделенные на шаге (2) («искомое слово не найдено»).

(4) Если искомое слово найдено, взять все его эквиваленты; конец.

') Бочее подробно с этим понятием можно познакомиться по статье «Алгоритм» в «Философской энциклопедии», т. 1, M., I960, или по книге Б. A. Tpax-тенброта «Алгоритмы и машинное решение задач», M., 1960. — Прим. ред. Гл. IV. Алгоритмы. Машины Тьюринга

65

(б) Если искомое слово не найдено, взять более полный словарь и вернуться к (I)1).

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

Более детальная характеристика понятия «алгоритм» должна включать следующие аспекты (по Хартли Роджерсу):

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

б) Имеется механизм (человек, механическое, оптическое и т. п. устройство, электронная машина), воспринимающий и выполняющий инструкции.

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

г) Существенно, что все выполняемые процедуры являются дискретными (хотя обрабатываемые ими объекты могут быть по своему характеру непрерывными).

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

Напрашивается аналогия с парой (вычислительная машина, программа), а именно:

а) соответствует программе;

б) соответствует вычислительной машине, работающей по,этой программе;

в) соответствует машинной памяти;

г) соответствует дискретной («цифровой») природе цифровых вычислительных машин (в отличие от аналоговых);

д) соответствует механичности и жесткой детерминированности порядка выполнения команд программы.
Предыдущая << 1 .. 15 16 17 18 19 20 < 21 > 22 23 24 25 26 27 .. 101 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

Есть, чем поделиться? Отправьте
материал
нам
Авторские права © 2009 BooksShare.
Все права защищены.
Rambler's Top100

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed