Вычислимые функции. 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 -кратный код набора преобразуется в решетчатый код