Cтраница 1
Алгоритмы Поста сводятся к алгоритмам, реализуемым с помощью частично рекурсивных функций, и наоборот - любая частично рекурсивная функция может быть представлена алгоритмом системы Поста. [1]
Класс всех алгоритмов, эквивалентных, алгоритмам Поста, совпадает с классом всех нормализуемых алгоритмов. [2]
Одна часть тезиса Поста очевидна - всякий алгоритм Поста является несомненно и алгоритмом в интуитивном смысле. [3]
Интуитивное понятие алгоритма Рввнообъемно с точным понятием алгоритма Поста. [4]
Алгоритмы, составляемые из любого конечного числа правил описанных типов, называются алгоритмами Поста. [5]
Всякий алгоритм, представимый в виде программы машины Поста, будем называть алгоритмом Поста. [6]
Учитывая указанные свойства памяти универсальных цифровых машин, нетрудно заметить, что для выполнения произвольного алгоритма Поста достаточно пользоваться лишь операцией ( алгебраического) сложения, одной из операций условного перехода, например операцией условного перехода по точному совпадению слов, и операцией остановки машины. [7]
Алгоритмы, составленные из любого конечного члсла правил, представленных приказами машины Поста; называются алгоритмами Поста. Доказано, что алгоритмы Поста сводятся к алгоритмам, реализуемым с помощью частично рекурсивных функций, и наоборот, любая частично рекурсивная функция может быть представлена алгоритмом системы Поста. [8]
Алгоритмы, составленные из любого конечного числа правил, представленных приказами машины Поста, называются алгоритмами Поста. [9]
Однако сказанное выше убеждает в том, что использование двоичного алфавита а, X в машине Поста не является реальным ограничением на сложность алгоритмов Поста. Здесь уместно напомнить, что и в современных ЭВМ все богатство символов кодируется конфигурациями двоичных битов, а соответствующее кодирование / декодирование осуществляют устройства ввода / вывода. [10]
Наконец, имеется эмпирическое подтверждение: за пятьдесят лет, прошедших с тех пор, как был выдвинут тезис Поста ( а также и тезис Черча), не была получена никакая процедура, являющаяся алгоритмом по общему признанию, но не представимая в виде алгоритма Поста или посредством какого-либо другого уточнения алгоритма. [11]
В 1950 - е годы существенный вклад в развитие теории алгоритмов внесли работы Колмогорова и, основанный на теории формальных грамматик, алгоритмический формализм Маркова, так называемые нормальные алгоритмы Маркова. Формальные модели алгоритмов Поста, Тьюринга и Черча, равно как и модели Колмогорова и Маркова, оказались эквивалентными в том смысле, что любой класс проблем, разрешимых в одной модели, разрешим и в другой. [12]
Алгоритмы, составленные из любого конечного члсла правил, представленных приказами машины Поста; называются алгоритмами Поста. Доказано, что алгоритмы Поста сводятся к алгоритмам, реализуемым с помощью частично рекурсивных функций, и наоборот, любая частично рекурсивная функция может быть представлена алгоритмом системы Поста. [13]
I, в алгоритмах Поста может встречаться шесть различных типов приказов. Приказы первых двух типов ( запись в рассматриваемую ячейку нуля и единицы) моделируются приказами машины М, осуществляющими пересылку информации из ячеек Ь0 или Ьг в активную ячейку, указанную, например, по третьему адресу машинного приказа. [14]
В схеме Тьюринга, которую принято называть машиной Тьюринга, также производится запись информации на бесконечной в обе стороны информационной ленте, разделенной на отдельные ячейки. Однако, в отличие от алгоритма Поста, здесь для записи информации употребляется произвольный конечный алфавит. Каждая ячейка информационной ленты служит для записи одной буквы. Эта буква может обозреваться специальным чувствительным элементом так называемой головки машины Тьюринга, способной перемещаться вдоль информационной ленты в обе стороны. [15]