Вычислимые функции. 2 страница4. Построить машину Тьюринга, правильно вычисляющую функцию : 5. На решетке с шагом l смоделировать работу машины Т, вычисляющей функцию
Вариант 5 1. Выяснить, применима ли машина Тьюринга Т, задаваемая программой П, к слову Р. Если применима, то выписать результат применения машины Т к слову Р. Предполагается, что — начальное состояние, — заключительное состояние и в начальный момент головка машины обозревает самую левую единицу на ленте: a) б) в) 2. По словесному описанию машины Тьюринга построить ее программу (в алфавите § Начав работу с последней единицы массива из единиц, машина «сдвигает» его на одну ячейку влево, не изменяя «остального содержимого» ленты. Головка останавливается на первой единице «перенесенного» массива. 3. Найти результат применения машины к слову Р ( — заключительное состояние машины , а — заключительное состояние машины ):
4. Построить машину Тьюринга, правильно вычисляющую функцию : 5. На решетке с шагом l смоделировать работу машины Т, вычисляющей функцию
Вариант 6 1. Построить в алфавите машину Тьюринга, обладающую следующими свойством (предполагается, что в начальный момент головка обозревает самый левый символ слова, и в качестве пустого символа берется 0): § машина имеет одно состояние, одну команду и применима к любому слову в алфавите . 2. По словесному описанию машины Тьюринга построить ее программу (в алфавите § Начав двигаться вправо от какой-то «начальной» ячейки, головка «находит» первую при таком перемещении ячейку с единицей (если такая ячейка «встретится на пути») и, сделав «один шаг» вправо, останавливается на соседней ячейке. Если в «начальной» ячейке записана единица, то головка останавливается на соседней справа ячейке. Содержимое ленты не меняется. 3. Используя машины и построить операторную схему алгоритма ₤ (здесь — заключительные состояния соответствующих машин):
₤: . 4. Построить машину Тьюринга, правильно вычисляющую функцию : 5. Построить машину Тьюринга, преобразующую один машинный код в другой. Заданный l -кратный код набора преобразуется в решетчатый код (функционирование машины не должно зависеть от значения l).
Вариант 7 1. Построить в алфавите машину Тьюринга, обладающую следующими свойством (предполагается, что в начальный момент головка обозревает самый левый символ слова, и в качестве пустого символа берется 0): § машина имеет две команды, не применима ни к какому слову в алфавите и зона работы на каждом слове бесконечная. 2. По словесному описанию машины Тьюринга построить ее программу (в алфавите § Машина начинает работу с самой левой непустой ячейки и отыскивает единицу, примыкающую с левой стороны к первому слева массиву из трех нулей («окаймленному» единицами). Головка останавливается на найденной единице (если такая есть). Содержимое ленты не меняется. 3. Используя машины и построить операторную схему алгоритма ₤ (здесь — заключительные состояния соответствующих машин):
₤: 4. Построить машину Тьюринга, правильно вычисляющую функцию : 5. Построить машину Тьюринга, преобразующую один машинный код в другой. Заданный l -кратный код набора преобразуется в решетчатый код (функционирование машины не должно зависеть от значения l).
Вариант 8 1. Построить в алфавите машину Тьюринга, обладающую следующими свойством (предполагается, что в начальный момент головка обозревает самый левый символ слова, и в качестве пустого символа берется 0): § машина имеет две команды, не применима ни к какому слову в алфавите и зона работы на любом слове ограничена одним и тем же числом ячеек, не зависящим от выбранного слова. 2. По словесному описанию машины Тьюринга построить ее программу (в алфавите § При заданном головка машины, начав работу с произвольной ячейки, содержащей единицу, двигается вправо до тех пор, пока не пройдет подряд нулей. Головка останавливается на первой ячейке за этими нулями, напечатав в ней 1. Остальное содержимое ленты не меняется. 3. Используя машины и построить операторную схему алгоритма ₤ (здесь — заключительные состояния соответствующих машин):
₤: 4. Построить машину Тьюринга, правильно вычисляющую функцию : 5. Построить машину Тьюринга, преобразующую один машинный код в другой. Заданный l -кратный код набора преобразуется в решетчатый код (n массивов единиц, n ≥ 1), где n - фиксировано, l - произвольное.
Вариант 9 1. Построить в алфавите машину Тьюринга, обладающую следующими свойством (предполагается, что в начальный момент головка обозревает самый левый символ слова, и в качестве пустого символа берется 0): § машина имеет три команды, применима к словам и не применима к словам . 2. По словесному описанию машины Тьюринга построить ее программу (в алфавите § При заданном головка машины, начав работу с какой-то ячейки и двигаясь вправо, ставит подряд единиц и останавливается на последней из них. 3. По операторной схеме алгоритма ₤ и описанию машин, входящих в нее, построить программу машины Т, задаваемой этой схемой, и найти результат применения машины Т к слову Р: ₤
(начальные состояния машин а заключительные — ). 4. Построить машину Тьюринга, правильно вычисляющую функцию : 5. Построить машину Тьюринга, преобразующую один машинный код в другой. Заданный l -кратный код набора преобразуется в решетчатый код
|