Машина - пост
Cтраница 2
На информационной ленте машины Поста расположено N массивов меток, отделенных друг от друга свободной ячейкой. Каретка находится над крайней левой меткой первого массива. [16]
На информационной ленте машины Поста находятся два массива в М и TV меток. Составьте программу выяснения, одинаковы ли массивы по длине. [17]
На информационной ленте машины Поста находится массив меток. Сотрите все метки, кроме крайних, таким образом, чтобы положение каретки при этом не изменилось. [18]
 |
На ленте записаны числа 2 и 3. [19] |
Машина Тьюринга [12-14] аналогична машине Поста. [20]
Перечислите приказы, выполняемые машиной Поста. [21]
Напишите и самостоятельно исполните программу машины Поста, делящую одно число на другое, разделенные на ленте одним пробелом. [22]
Число k представляется на ленте машины Поста k 1 идущими подряд метками. Одна метка соответствует нулю. [23]
Число k представлено на ленте машины Поста k 1 идущими подряд метками. Найдите остаток от деления целого неотрицательного числа & на 3, если известно, что каретка находится справа от заданного числа. [24]
Рассмотрим, следуя [16], конструкцию машины Поста. Машина Поста, как и ее близкий родственник - машина Тьюринга, представляет собой мысленную конструкцию, используемую только для математического исследования проблем теории алгоритмов. Для выполнения реальных вычислений машина Поста, именно в силу своей исключительной простоты, окажется совершенно непригодной. С точки зрения удобства программирования ее система команд слишком бедна. [25]
Всякий алгоритм, представимый в виде программы машины Поста, будем называть алгоритмом Поста. [26]
Как и в машине Тьюринга, все состояния машины Поста пронумерованы. [27]
Наконец, может показаться, что бедность системы команд машины Поста препятствует программированию на ней сложных алгоритмов. В самом деле, современные ЭВМ содержат сотни типов команд, а здесь всего шесть. Однако рассмотрение системы команд, скажем ЕС ЭВМ, показывает, что подавляющее большинство команд введено для обеспечения удобства программирования, но не связано с какими-либо принципиальными сооб-ражаниями о представимости алгоритмов. Например, для умножения чисел с плавающей точкой достаточно иметь команды сложения и умножения целых чисел - формально нет необходимости в команде умножения чисел с плавающей точкой. Однако такая команда присутствует в системе команд ЕС ЭВМ [25] и существенно упрощает программирование вычислений. Кроме того, следует учесть, что на аппаратном уровне реализации команд ЭВМ фактическое разнообразие выполняемых операций уже сравнимо по богатству с системой команд машины Поста. [28]
Тезис 5.1. Интуитивное понятие финитной системы равнообъемно с точным понятием машины Поста. [29]
Алгоритмы, составленные из любого конечного члсла правил, представленных приказами машины Поста; называются алгоритмами Поста. Доказано, что алгоритмы Поста сводятся к алгоритмам, реализуемым с помощью частично рекурсивных функций, и наоборот, любая частично рекурсивная функция может быть представлена алгоритмом системы Поста. [30]
Страницы: 1 2 3 4