Cтраница 4
Другими словами, всякий ли алгоритм представим в виде программы машины Поста. На первый взгляд уже сама бедность используемого алфавита П, X представляется препятствием для реализации в машине Поста сложных алгоритмов. [46]
Во-первых, представляется интуитивно естественным, что всякий алгоритм можно запрограммировать на машине Поста. С программистской точки зрения это особенно естественно - программисты уже привыкли к тому, что на самых различных ЭВМ с разнообразными системами команд ( иногда довольно ограниченными) удается программировать любые алгоритмы, являющиеся алгоритмами в интуитивном смысле, и, значит, не видно причин, почему этого нельзя сделать на машине Поста. Команды целочисленной арифметики действительно удается представить в виде алгоритмов Поста [16], а более сложные арифметические операции очевидно могут быть выражены через целочисленные операции. Логические операции проще арифметических и поэтому могут быть представлены алгоритмами Поста. [47]
Команды первых двух типов устанавливают новое содержимое обозреваемой ячейки ленты, оставляя эту ячейку в поле зрения машины. Первые пять типов команд не зависят от информации на ленте; поэтому, если бы алгоритм был составлен только из команд этих типов, то он записывал бы на ленту всегда одно и то же слово, зависящее только от вида алгоритма, но не от входного слова. Однако добавление шестого типа команд делает алгоритмическую схему Поста такой же универсальной, как алгоритмические схемы Тьюринга и Маркова. Доказательство возможности перехода от любой машины Тьюринга к машине Поста основывается на том, что после кодировки исходного алфавита знаками 0 и 1 каждое состояние машины Тьюринга, работающей с этими знаками, описывается несколькими состояниями машины Поста. [48]
Команды первых двух типов устанавливают новое содержимое обозреваемой ячейки ленты, оставляя эту ячейку в поле зрения машины. Первые пять типов команд не зависят от информации на ленте; поэтому, если бы алгоритм был составлен только из команд этих типов, то он записывал бы на ленту всегда одно и то же слово, зависящее только от вида алгоритма, но не от входного слова. Однако добавление шестого типа команд делает алгоритмическую схему Поста такой же универсальной, как алгоритмические схемы Тьюринга и Маркова. Доказательство возможности перехода от любой машины Тьюринга к машине Поста основывается на том, что после кодировки исходного алфавита знаками 0 и 1 каждое состояние машины Тьюринга, работающей с этими знаками, описывается несколькими состояниями машины Поста. [49]
Более того, мы замечаем, что финитные системы не очень-то уж выразительны. Подчеркнем, что этот недостаток не является признаком бедности канонических исчислений Поста по сравнению с другими финитными системами. В настоящее время доказана эквивалентность самых различных подходов к понятию финитной системы. Это означает, что если некоторая процедура описана средствами одной финитной системы, то эта процедура может быть описана и средствами другой финитной системы. Так, машина Поста может быть смоделирована в некотором каноническом исчислении Поста. И наоборот, любой алгоритм, заданный средствами канонического исчисления, может быть представлен в машине Поста. [50]
Другими словами, всякий ли алгоритм представим в виде программы машины Поста. На первый взгляд уже сама бедность используемого алфавита П, X представляется препятствием для реализации в машине Поста сложных алгоритмов. Это значит, что любые исходные данные могут быть подходящим образом закодированы некоторой конфигурацией меток на ленте машины Поста. Точно также и результат работы машины Поста, т.е. конфигурацию меток, получаемую в случае результативной остановки машины, можно считать двоичным кодом некоторого содержательного результата. [51]
Другими словами, всякий ли алгоритм представим в виде программы машины Поста. На первый взгляд уже сама бедность используемого алфавита П, X представляется препятствием для реализации в машине Поста сложных алгоритмов. Это значит, что любые исходные данные могут быть подходящим образом закодированы некоторой конфигурацией меток на ленте машины Поста. Точно также и результат работы машины Поста, т.е. конфигурацию меток, получаемую в случае результативной остановки машины, можно считать двоичным кодом некоторого содержательного результата. [52]
Более того, мы замечаем, что финитные системы не очень-то уж выразительны. Подчеркнем, что этот недостаток не является признаком бедности канонических исчислений Поста по сравнению с другими финитными системами. В настоящее время доказана эквивалентность самых различных подходов к понятию финитной системы. Это означает, что если некоторая процедура описана средствами одной финитной системы, то эта процедура может быть описана и средствами другой финитной системы. Так, машина Поста может быть смоделирована в некотором каноническом исчислении Поста. И наоборот, любой алгоритм, заданный средствами канонического исчисления, может быть представлен в машине Поста. [53]