Индивидуальные очистные сооружения: К классу индивидуальных очистных сооружений относят сооружения, пропускная способность которых...
Особенности сооружения опор в сложных условиях: Сооружение ВЛ в районах с суровыми климатическими и тяжелыми геологическими условиями...
Топ:
Генеалогическое древо Султанов Османской империи: Османские правители, вначале, будучи еще бейлербеями Анатолии, женились на дочерях византийских императоров...
Марксистская теория происхождения государства: По мнению Маркса и Энгельса, в основе развития общества, происходящих в нем изменений лежит...
Методика измерений сопротивления растеканию тока анодного заземления: Анодный заземлитель (анод) – проводник, погруженный в электролитическую среду (грунт, раствор электролита) и подключенный к положительному...
Интересное:
Что нужно делать при лейкемии: Прежде всего, необходимо выяснить, не страдаете ли вы каким-либо душевным недугом...
Искусственное повышение поверхности территории: Варианты искусственного повышения поверхности территории необходимо выбирать на основе анализа следующих характеристик защищаемой территории...
Мероприятия для защиты от морозного пучения грунтов: Инженерная защита от морозного (криогенного) пучения грунтов необходима для легких малоэтажных зданий и других сооружений...
Дисциплины:
2017-12-09 | 259 |
5.00
из
|
Заказать работу |
|
|
Располагая натуральными алгоритмами, можно построить огромное количество различных операций и, значит, огромное количество семейств первичных алгоритмов. Читатель помнит, что это связано не только с присоединением к имеющимся операциям новых операций, но и с построением формальных языков, как алгоритмических, так и операндных.
Пользуясь набором натуральных операций, можно построить не только операции над словами, но и над другими значительно более сложными конструкциями благодаря операциям линеаризации и делинеаризации. По сравнению с избранными алгоритмами, которые были изучены в логических теориях, первичные алгоритмы обладают большими возможностями. Вместе с появлением первичных алгоритмов понятие алгоритма «освобождается от оков», в которых его держали, связывая его с конструктивными объектами, называемыми словами. Объем книги и значительная тру доемкость построения алгоритмов не позволяют автору привести все алгоритмы, которые хотелось бы, для того чтобы проиллюстрировать сказанное. Ограничимся рассказом об алгоритмах.
Можно построить натуральные алгоритмы включения и исключения букв перед рассматриваемой буквой преобразуемого квазислов. Допустим, что такие алгоритмы у нас уже есть.
…
является алгоритмом выполнения для любого алгоритма ранга r, записью которого является конструкция t.
Если применение алгоритма W к конструкции дает результат , то полагаем, что применение алгоритма t ранга r к набору операндов s1, s2,..., sr дает тот же результат ρ.
Язык L* называется алгоритмическим языком, а язык L — языком исходных данных. Еще раз подчеркнем, что по существу, таким же образом было введено понятие первичного алгоритма, только вместо алгоритма выполнения там было применено правило выполнения. Мы тогда еще не располагали запасом алгоритмов и потому вынуждены были опираться на правило, в отношении которого не могли сказать, является ли оно алгоритмом, хотя догадывались, что является. В частном случае алгоритм может иметь ранг, равный 1.
|
Если алгоритм W уже известен, а это всегда так, то можно объявить соответствующую ему операцию. Будем считать, что это сделано, и алгоритмом ранга г называть совокупность записи 1 и операции W.
Иметь дело не с алгоритмом W, а с сопутствующей ему операцией удобнее потому, что, вводя все новые и новые классы алгоритмов с помощью последнего приема, не нужно помнить обо всех «предках» этих алгоритмов.
Вот тут мы допустили еще одно отклонение от схемы определения первичного алгоритма. Вместо правила, вместо даже алгоритма выполнения, мы, имея дело с алгоритмом t, должны знать только операцию . Это не значит, что алгоритм W мы должны забыть ради операции . Нет. Ведь знание алгоритма содержит в себе и знание операции. Какой же смысл в таком отклонении от схемы? Оказывается, очень большой. Вместо алгоритма W можно взять любой другой алгоритм, соответствующий той же операции . При этом алгоритм t будет нам так же понятен [25], как ранее при алгоритме W. Для практики очень важно пользоваться самым простым способом запоминания операции W. Сделанное отклонение от схемы дает такую возможность. Теперь нетрудно уже дать формулировку широкого формального понятия алгоритма.
Всякий первичный алгоритм, записанный на некотором языке L* и работающий над другим языком L, является алгоритмом. Кроме того, всякий r-местный алгоритм, записанный на некотором языке L* и работающий над языком L, — тоже алгоритм.
Наличие у первичных алгоритмов правил выполнения вместо алгоритма выполнения является их неприятной особенностью. Но эта особенность для практика неощутима. Она неприятна для теоретика. И вот, чтобы ее преодолеть, доказана такая теорема.
|
Теорема однотипности всех алгоритмов. Для каждого семейства первичных алгоритмов существует алгоритм выполнения, графически одинаковый и эквивалентный с их правилом выполнения.
Сам этот алгоритм выполнения принадлежит семейству, находящемуся на достаточно высоком уровне иерархии.
Казалось бы, такая теорема позволяет нам выбросить правила выполнения первичных алгоритмов. Но, увы! Это не так. Если бы мы выбросили все правила выполнения, то система определений понятия алгоритма превратилась бы в порочный круг. А наука (по крайней мере математика) этого не допускает. Несмотря на это, указанная теорема позволяет не выделять первичные алгоритмы из совокупности всех алгоритмов.
Теперь понятие алгоритма достигло высокой степени широты. Алгоритмы приобрели и те две степени свободы, которых им недоставало в предыдущем параграфе. Теперь алгоритмы могут быть какими угодно конструкциями и не только перерабатывать какие угодно конструкции, но и сами они и способы их «действия» могут быть очень разнообразными. Алгоритмы могут не только перерабатывать свои собственные записи, но даже могут «сливаться» с операндами, на некотором этапе образуя текст, где невозможно отделить алгоритм от операнда.
Обладая указанными тремя степенями свободы, алгоритмы становятся пригодными для того, чтобы служить математическими описаниями очень многих реальных объектов и процессов. Перечислим еще раз эти три степени свободы.
1. Для соответствующим образом выбранного алгоритма допустимыми исходными данными могут быть конструкции любого заданного класса конструкций (группирующиеся в формальный язык).
2. Записью алгоритма может быть любая конструкция.
3. В процессе «работы» алгоритмы не только могут перерабатывать исходные данные, но и самих себя и даже «сливаться» е преобразуемыми объектами.
Располагая широким формальным понятием алгоритма мы без существенного труда (только лишь преодолевая некоторые технические трудности) можем доказать, что нормальные алгоритмы — это одно из семейств алгоритмов в широком смысле.
То же можно доказать и по отношению к алгоритмам, сопутствующим машинам Тьюринга или рекурсивным функциям. Конечно, в данной книге читатель этих доказательств не найдет.
|
|
Папиллярные узоры пальцев рук - маркер спортивных способностей: дерматоглифические признаки формируются на 3-5 месяце беременности, не изменяются в течение жизни...
Индивидуальные очистные сооружения: К классу индивидуальных очистных сооружений относят сооружения, пропускная способность которых...
Особенности сооружения опор в сложных условиях: Сооружение ВЛ в районах с суровыми климатическими и тяжелыми геологическими условиями...
Опора деревянной одностоечной и способы укрепление угловых опор: Опоры ВЛ - конструкции, предназначенные для поддерживания проводов на необходимой высоте над землей, водой...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!