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