Cтраница 1
Постовское пространство символов представляет собой бесконечную ленту ящиков ( ячеек), каждый из которых может быть или помечен, или не помечен. [1]
На основе анализа множества элсоинов, образующих символы, пространство символов ( алфавиты) и пространство наблюдения ( информационные модели), может быть определено необходимое число элсоинов при заданных значениях градаций параметров, длине рабочего алфавита и заданной помехозащищенности символов или решена любая обратная задача. [2]
Если 17, 21 и 100 не только рассматриваются как единицы, но и подвергаются такому же обращению, как если бы каждая из них занимала одну ячейку пространства символов, то достаточно переопределить символы так что каждое из указанных чисел образует единый символ, чтобы свести составное рассмотрение к простому рассмотрению такого типа, как в машине Тьюринга. [3]
Эти ограничения в поведении вычислителя-человека при вычислении значения арифметической функции для данных аргументов, состоящие в следовании только предписанным правилам, сходны с ограничениями, входящими в конструкцию машины Тьюринга. Лента-это пространство символов для машины, а состояние машины соответствует состоянию ума вычислителя. [4]
Вычисления обычно производятся на двумерной бумаге, и двумерный характер бумаги иногда используется в элементарной арифметике. Теоретически мы должны также рассмотреть возможность и других видов пространства символов. Пространство символов должно обладать достаточно правильной структурой для того. [5]
Вычислитель-человек менее ограничен в своих действиях чем машина, так как: ( а) Он может рассматривать одновременно более чем одно вхождение символа. Он может выполнить более сложное элементарное действие, чем машина, ( с) Его пространство символов не обязательно должно быть одномерной лентой, ( d) Он может выбрать символическое представление значений аргументов и функций, отличное от использованного в нашем определении вычислимости. Мы рассмотрим различные возможности типа ( а) - ( d) и покажем вкратце, как каждая из них может быть сведена к эквивалентной в терминах машин Тьюринга. Мы обычно будем говорить так, как будто надо свести только одну из них, но наши методы будут годиться и для последовательного сведения любой их комбинации. [6]
Различные состояния ума фиксированы до появления конкретных рассуждений, поскольку мы рассматриваем вычисление согласно предписанному методу и не допускаем математического творчества по ходу вычислительной работы. Каждое производимое вычислителем действие должно заключаться в дискретном изменении конечной системы, состоящей из вхождений символов в пространство символов, распределения рассматриваемых клеток в этом пространстве и состояния его ума. [7]
Вычисления обычно производятся на двумерной бумаге, и двумерный характер бумаги иногда используется в элементарной арифметике. Теоретически мы должны также рассмотреть возможность и других видов пространства символов. Пространство символов должно обладать достаточно правильной структурой для того. [8]
Пользуясь методами § 68, мы можем построить машину Тьюринга, которая будет находить р4 () - ую клетку, отправляясь от - ой, если на 0 - й ( или - 1 - й) клетке постоянно имеется отличительная пометка. Вычисления, выполняемые для этой цели, могут производиться с помощью пометок, которые впоследствии будут стерты, причем за это время на них ничего не будет печататься. Это позволяет нам свести вычисление в данном пространстве символов к вычислению на линейной ленте машины Тьюринга. Это имеет место в любом обычном пространстве символов. Исключение представляет вычислитель, принимающий время от времени сигналы на слух. Пространство символов может состоять из нескольких разобщенных подпространств, в каждом из которых имеется своя воспринимаемая ячейка, как, например, в случае вычислителя, который одновременно глазами читает на бумаге символ, ощупью находит на ленте другой и получает на слух сигнал. Если имеется г таких подпространств, мы можем перестроить ячейки так, чтобы они были наборами из г ячеек, по одной в каждом из этих подпространств. [9]
По Посту, проблема задается внешней силой путем пометки конечного количества ящиков ленты. В более поздних работах по машине Поста ( [8]) принято считать, что машина работает в единичной системе счисления ( 0 V; 1 W; 2 VW), т.е. ноль представляется одним помеченным ящиком, а целое положительное число - помеченными ящиками в количестве на единицу больше его значения. Поскольку множество конкретных проблем, составляющих общую проблему, является счетным, то можно установить взаимно однозначное соответствие ( биективное отображение) между множеством положительных целых чисел N и множеством конкретных проблем. Общая проблема называется по Посту 1 - за данной если существует такой финитный 1-процесс, что, будучи, применим к п N в качестве исходной конфигурации ящиков, он задает n - ую конкретную проблему в виде набора помеченных ящиков в пространстве символов. [10]
Число ячеек, которые в конечном счете могут быть достигнуты, оказывается поэтому счетным. Одна и та же ячейка может быть достигнута различными последовательностями ходов. Например, на плоскости ход вниз и затем ход вправо приводит к той же самой клетке, что и сначала ход вправо, а затем ход вниз. Мы допустим, что может быть дана нумерация без повторений для всех ячеек, так что имеет место следующее. Это допущение выполнено для любого из вводившихся до сих пор пространств символов. [11]
Пользуясь методами § 68, мы можем построить машину Тьюринга, которая будет находить р4 () - ую клетку, отправляясь от - ой, если на 0 - й ( или - 1 - й) клетке постоянно имеется отличительная пометка. Вычисления, выполняемые для этой цели, могут производиться с помощью пометок, которые впоследствии будут стерты, причем за это время на них ничего не будет печататься. Это позволяет нам свести вычисление в данном пространстве символов к вычислению на линейной ленте машины Тьюринга. Это имеет место в любом обычном пространстве символов. Исключение представляет вычислитель, принимающий время от времени сигналы на слух. Пространство символов может состоять из нескольких разобщенных подпространств, в каждом из которых имеется своя воспринимаемая ячейка, как, например, в случае вычислителя, который одновременно глазами читает на бумаге символ, ощупью находит на ленте другой и получает на слух сигнал. Если имеется г таких подпространств, мы можем перестроить ячейки так, чтобы они были наборами из г ячеек, по одной в каждом из этих подпространств. [12]
Допустим, что символами служат десять арабских цифр. Описанное поведение можно рассматривать как пове-i дение обобщенной машины Тьюринга, в которой конфигурация ( определяющая действие) есть ( е, /, a, g, h, qj, где е, f, a, g, h - цифры, занимающие пять клеток, сгруппированных вокруг находящейся в поле зрения. Приходится добавлять не только состояния q, но и некоторые другие, принимаемые в процессе перехода от qc к qcefgh. Это сведение является иллюстрацией замечания, что можно вспомнить конечное число ранее рассмотренных символов, изменив состояние ума, в котором они рассматривались. Если эти клетки расположены в пространстве символов так, что вычислитель может найти их и вернуться посредством действий, аналогичных производимым машинами Тьюринга ( ср. [13]