Cтраница 3
Алгоритмы, составленные из любого конечного числа правил, представленных приказами машины Поста, называются алгоритмами Поста. [31]
Составьте программу сложения произвольного количества целых неотрицательных чисел, записанных на ленте машины Поста на расстоянии одной пустой секции друг от друга. Каретка находится над крайней левой меткой левого числа. [32]
Однако сказанное выше убеждает в том, что использование двоичного алфавита а, X в машине Поста не является реальным ограничением на сложность алгоритмов Поста. Здесь уместно напомнить, что и в современных ЭВМ все богатство символов кодируется конфигурациями двоичных битов, а соответствующее кодирование / декодирование осуществляют устройства ввода / вывода. [33]
Ограничившись алфавитом П, X докажите, что для любой программы машины Тьюринга существует эквивалентная программа для машины Поста. [34]
Тезис 2.2. Все алгоритмические языки при программировании неформальных процедур имеют ют же уровень сложности, что и язык программирования машины Поста. [35]
При чтении лекций ( если имеется overhead - или мультимедиа-проектор), а также при выполнении лабораторных работ рекомендуется использовать какие-либо из многочисленных программных моделей машин Поста и Тьюринга, разрабатываемых студентами старших курсов при выполнении курсовых и дипломных работ. [36]
Рассмотрим, следуя [16], конструкцию машины Поста. Машина Поста, как и ее близкий родственник - машина Тьюринга, представляет собой мысленную конструкцию, используемую только для математического исследования проблем теории алгоритмов. Для выполнения реальных вычислений машина Поста, именно в силу своей исключительной простоты, окажется совершенно непригодной. С точки зрения удобства программирования ее система команд слишком бедна. [37]
Первые фундаментальные работы по теории алгоритмов были опубликованы в середине 1930 - х годов Аланом Тьюрингом, Алоизом Черчем и Эмилем Постом. Предложенные ими машина Тьюринга, машина Поста и класс рекурсивно-вычислимых функций Черча были первыми формальными описаниями алгоритма, использующими строго определенные модели вычислений. [38]
По Посту, проблема задается внешней силой путем пометки конечного количества ящиков ленты. В более поздних работах по машине Поста ( [8]) принято считать, что машина работает в единичной системе счисления ( 0 V; 1 W; 2 VW), т.е. ноль представляется одним помеченным ящиком, а целое положительное число - помеченными ящиками в количестве на единицу больше его значения. Поскольку множество конкретных проблем, составляющих общую проблему, является счетным, то можно установить взаимно однозначное соответствие ( биективное отображение) между множеством положительных целых чисел N и множеством конкретных проблем. Общая проблема называется по Посту 1 - за данной если существует такой финитный 1-процесс, что, будучи, применим к п N в качестве исходной конфигурации ящиков, он задает n - ую конкретную проблему в виде набора помеченных ящиков в пространстве символов. [39]
Другими словами, всякий ли алгоритм представим в виде программы машины Поста. На первый взгляд уже сама бедность используемого алфавита П, X представляется препятствием для реализации в машине Поста сложных алгоритмов. [40]
Во-первых, представляется интуитивно естественным, что всякий алгоритм можно запрограммировать на машине Поста. С программистской точки зрения это особенно естественно - программисты уже привыкли к тому, что на самых различных ЭВМ с разнообразными системами команд ( иногда довольно ограниченными) удается программировать любые алгоритмы, являющиеся алгоритмами в интуитивном смысле, и, значит, не видно причин, почему этого нельзя сделать на машине Поста. Команды целочисленной арифметики действительно удается представить в виде алгоритмов Поста [16], а более сложные арифметические операции очевидно могут быть выражены через целочисленные операции. Логические операции проще арифметических и поэтому могут быть представлены алгоритмами Поста. [41]
Этот тезис, однако, не может быть предметом доказательства: ведь алгоритм в обычном смысле - это не точное математическое понятие, о котором можно рассуждать формально, по строгим правилам. Источником обоснования такого рода содержательных тезисов служит практика: она показывает, что все известные алгоритмы могут быть представлены в виде машины Тьюринга или нормального алгорифма Маркова ( или машины Поста и др.); найти же противоречащий пример никто не смог. Математическая практика, таким образом, подтверждает эти тезисы. Их подтверждает и то обстоятельство, что - в этом случае уже с полной математической строгостью - удается доказать эквивалентность друг другу всех точных определений понятия алгоритм, в том числе эквивалентность машины Тьюринга и нормального алгорифма Маркова. И, наконец, еще одно, самое важное соображение: построенные с помощью определения нормального алгорифма или машины Тьюринга ( и связанных с ними тезисов) математические и логические теории решают ряд трудных задач самих математики и логики ( в том числе, подчеркивает С. А. Яновская, и конструктивной математики) ( С. А. Яновская, 1966, стр. [42]
Рассмотрим, следуя [16], конструкцию машины Поста. Машина Поста, как и ее близкий родственник - машина Тьюринга, представляет собой мысленную конструкцию, используемую только для математического исследования проблем теории алгоритмов. Для выполнения реальных вычислений машина Поста, именно в силу своей исключительной простоты, окажется совершенно непригодной. С точки зрения удобства программирования ее система команд слишком бедна. [43]
В отличие от машины Поста в каждой ячейке ленты машины Тьюринга может находиться один из символов некоторого конечного алфавита, а устройство управления может быть в одном из, конечных состояний. Другими словами, машина Тьюринга, работая в произвольном конечном алфавите, может выполнять некоторое конечное число приказов. При этом машины Тьюринга, как и машины Поста, могут сдвигать ленту на одну ячейку вправо или влево, оставляя содержимое ячеек неизменным, или могут изменять со-стояние воспринимаемой ячейки, оставляя ленту неподвижной. [44]
На информационной ленте либо вправо, либо влево от секции, над которой расположена каретка, находится массив меток. Расстояние до массива выражается произвольным числом. Необходимо составить программу, работая по которой машина Поста найдет этот массив и установит каретку на начало этого массива. [45]