Лента - машина - тьюринг
Cтраница 2
В отличие от машины Поста в каждой ячейке ленты машины Тьюринга может находиться один из символов некоторого конечного алфавита, а устройство управления может быть в одном из, конечных состояний. Другими словами, машина Тьюринга, работая в произвольном конечном алфавите, может выполнять некоторое конечное число приказов. При этом машины Тьюринга, как и машины Поста, могут сдвигать ленту на одну ячейку вправо или влево, оставляя содержимое ячеек неизменным, или могут изменять со-стояние воспринимаемой ячейки, оставляя ленту неподвижной. [16]
После чего Петри переходит к построению сети для моделирования ленты машины Тьюринга. Эта сеть является целиком асинхронной и строится из идентичных ячеек, которые передают информацию своим соседям ( левым или правым) по мере необходимости. Поскольку лента бесконечна, то необходимо бесконечное число ячеек. Однако важность этой работы заключается в акцентировании асинхронной природы взаимодействий. [17]
 |
Соответствие между ящиками и. [18] |
Важно уяснить соотношение между ящиками абака и соответствующими частями ленты машины Тьюринга. [19]
Интересно отметить, что ЗУ на входе ЭВМ следует рассматривать как аналог ленты машины Тьюринга, обладающий потенциальной бесконечностью ( только) в одну сторону. Точно так же следует рассматривать ЗУ на выходе ЭВМ. Связано это с тем, что на входе можно поместить сколь угодно длинную ( хотя и конечную) строку символов, а на выходе тоже может быть получена сколь угодно длинная строка. [20]
Чтобы показать обратное, используем алгоритм, предложенный Фишером [2] для моделирования ленты машины Тьюринга с помощью трех счетчиков Л, В и С. [21]
Эта работа касается определения нижних границ времени вычисления некоторых входно-выходных преобразований и взаимосвязи между временем вычисления и размерностью лент машины Тьюринга. Метод, использованный при установлении этой границы, применяется в разд. Этот результат обобщается в разд. Хартманиса - Стирнза [2, 3] не может быть значительно улучшен и что имеется существенная разница между размерностью и количеством лент машины Тьюринга. [22]
Аналогично, вычислимые по Тьюрингу множества StrP обладают тем свойством, что их характеристическая функция может быть получена в виде выпечатанной последовательности нулей и единиц на ленте машины Тьюринга с подходящей программой. S в том и только том случае, если, скажем, на ленте выпечатывается 1 в n - й позиции. [23]
Не существует алгоритма ( машины Тьюринга), позволяющего по описанию произвольного алгоритма и его исходных данных, при этом и алгоритм и данные заданы символами на ленте машины Тьюринга, определить, останавливается ли этот алгоритм на этих данных или работает бесконечно. [24]
Это соответствует бесконечно длинной ленте памяти в машине Тьюринга. Положению ленты машины Тьюринга соответствует наблюдаемая х, спектр которой образует все множество Z. Наблюдаемая х адресует номер места ленты, сканируемого в настоящий момент. Поскольку лента - бесконечно длинная, но находится в движении на протяжении вычислений, она не должна быть жесткой или ее нельзя заставить двигаться конечным способом. Механизм, который движет ленту в соответствии с сигналами, передаваемыми с конечной скоростью только между смежными сегментами, должен удовлетворять требованию конечности средств и должен быть способен выполнить то, что описано далее. Удовлетворившись тем, что такой механизм возможен, мы не нуждаемся в том, чтобы моделировать его явно. [25]
Работы Хартманиса и Стирнза [2, 3] показывают, что уменьшение размерности ленты машины Тьюринга никогда не требует больше чем квадрата обычного времени вычисления. [26]
Точно так же имитации работы программы 23 на куске Н может мешать кусок Р или те записи, которые возникли бы в результате его обработки. Конечно, положение сильно упростилось бы, если бы вместо одной одномерной ленты машины Тьюринга в качестве внешней памяти имелись бы две ленты, причем правила функционирования машины допускали бы переписывание с одной ленты на другую. В таком случае можно было бы вычисление ЩР) осуществлять на одной ленте, вычисление 33 ( Я) на другой, и потом можно было бы свести результаты вместе. Это замечание показывает, что для машин другого типа ( с более гибкой и удобной памятью) алгоритм, программирующий параллельную композицию, был бы совсем тривиален. Для машин Тьюринга и для тыо-ринговых программ дело обстоит несколько хуже, но в конечном счете нужный программирующий алгоритм ( и даже в разных вариантах) удается описать. [27]
С оценками сложности вычислений связан другой подход к классификации вычислимых функций. Связь между аналитическим и сложностным подходами исследуется в статье Р. В. Ри-чи для сложности, измеряемой длиной ленты машины Тьюринга, используемой при вычислении. В общей постановке этот вопрос рассмотрен в добавлении А. А. Мучника ( стр. [28]
 |
Видеокамера, направленная на зеркало, строит модель себя внутри самой себя. Становится ли она от этого самосознающей. [29] |
Разумеется, трудно понять, как случайные процессы естественного отбора могли быть достаточно умными, чтобы дать авто-мату-хкщнику полную копию программы жертвы. А частичная программа ( в смысле отрезка ленты машины Тьюринга или чего-то подобного такой ленте) вряд ли была бы достаточно полезна хищнику с точки зрения естественного отбора. Ему был бы необходим какой-нибудь завершенный фрагмент этой ленты, а лучше ( хотя и менее вероятно) - вся лента целиком. [30]
Страницы: 1 2 3