Машина - пост
Cтраница 1
 |
Лента машины Поста разделена на ячейки и неограниченно простирается влево и вправо. [1] |
Машина Поста состоит из ленты и головки, осуществляющей чтение и запись. Заметим, что лента объявлена бесконечной лишь для простоты изложения. С тем же успехом можно предположить, что лента конечна в данный момент, но при необходимости наращивается. [2]
 |
Лента машины Поста разделена на ячейки и неограниченно простирается влево и вправо. [3] |
Работа машины Поста состоит в том, что головка передвигается вдоль ленты и печатает или стирает метки. Эта работа происходит по инструкции определенного вида, называемой программой. [4]
На ленте машины Поста расположен массив в N отмеченных секциях. При этом исходный массив может быть стерт. [5]
На ленте машины Поста расположен массив из N меток. [6]
На ленте машины Поста расположен массив из 2N отмеченных секций. [7]
На ленте машины Поста расположен массив из 2N - 1 меток. [8]
На ленте машины Поста расположены два массива. Составьте программу стирания того из массивов, который имеет большее количество меток. [9]
На ленте машины Поста находится п массивов меток, после последнего массива на расстоянии более трех пустых секций находится одна метка. [10]
На ленту машины Поста нанесены два массива меток на некотором расстоянии друг от друга. [11]
На ленте машины Поста отмечен массив п меток. Если да, то после числа через одну пустую секцию поставьте две метки, если нет - поставьте три метки. Каретка находится над крайней левой отмеченной секцией. [12]
На ленте машины Поста находятся п массивов меток. Каретка находится где-то над первым массивом. [13]
В отличие от машины Поста в каждой ячейке ленты машины Тьюринга может находиться один из символов некоторого конечного алфавита, а устройство управления может быть в одном из, конечных состояний. Другими словами, машина Тьюринга, работая в произвольном конечном алфавите, может выполнять некоторое конечное число приказов. При этом машины Тьюринга, как и машины Поста, могут сдвигать ленту на одну ячейку вправо или влево, оставляя содержимое ячеек неизменным, или могут изменять со-стояние воспринимаемой ячейки, оставляя ленту неподвижной. [14]
Пусть на ленте машины Поста заданы наборы помеченных ящиков ( кортежи) произвольной длины с произвольными расстояниями между кортежами, и головка находится у самого левого помеченного ящика. Задача состоит в установке головки на самый правый помеченный ящик последнего кортежа. Попытка построения алгоритма, решающего эту задачу, приводит к необходимости ответа на вопрос - когда после обнаружения конца кортежа мы сдвинулись вправо по пустым ящикам на М позиций и не обнаружили начало следующего кортежа - больше на ленте кортежей нет или они есть где-то правее. Информационная неопределенность задачи состоит в отсутствии информации либо о количестве кортежей на ленте, либо о максимальном расстоянии между кортежами - при наличии такой информации, т.е. при разрешении информационной неопределенности, задача становится алгоритмически разрешимой. [15]
Страницы: 1 2 3 4