Вычислимые функции. 3 страница

(n массивов единиц, n ≥ 1), где l - фиксировано, n - произвольное.

 

Вариант 10

1. Построить в алфавите машину Тьюринга, обладающую следующими свойством (предполагается, что в начальный момент головка обозревает самый левый символ слова, и в качестве пустого символа берется 0):

§ машина имеет пять команд, применима к словам и не применима к словам .

2. По словесному описанию машины Тьюринга построить ее программу (в алфавите

§ При заданном головка машины, двигаясь вправо от какой- либо пустой ячейки, находит первый при таком перемещении массив, содержащий не менее единиц, стирает в нем первые единиц и останавливается на самой правой из ячеек, в которых были стертые единицы. Остальное содержимое ленты не меняется.

3. По операторной схеме алгоритма ₤ и описанию машин, входящих в нее, построить программу машины Т, задаваемой этой схемой, и найти результат применения машины Т к слову Р:

₤

	—			—

 

			—

 

 

(начальные состояния машин а заключительные — ).

4. Построить машину Тьюринга, правильно вычисляющую функцию :

5. Построить машину Тьюринга, преобразующую один машин­ный код в другой. Заданный l -кратный код набора преобразуется в решетчатый код

(l - фиксированное, меняется α, ).

 

Вариант 11

1. Построить в алфавите машину Тьюринга, обладающую следующими свойством (предполагается, что в начальный момент головка обозревает самый левый символ слова, и в качестве пустого символа берется 0):

§ машина применима к словам , где , и не применима к словам , где .

2. Построить композицию машин Тьюринга по паре состояний и найти результат применения композиции к слову Р ( —заключительное состояние машины ):

 

 

 

 

3. Построить машину Тьюринга, вычисляющую функцию :

4. По программе машины Тьюринга Т записать аналитическое выражение для функций и , вычисляемых машиной Т (в качестве начального состояния берется , а в качестве заключитель­ного — ):

 

 

T:

 

 

5. Построить машину Тьюринга, преобразующую один машин­ный код в другой. Решетчатый код с заданной совокупностью слов, расположен­ных на соответствующих решетках (1-й, 2-й и т.д.), преобразуется в l -кратный код с указанным значением l:

 

Вариант 12

1. По заданной машине Тьюринга Т и начальной конфигура­ции К₁ найти заключительную конфигурацию ( — заключительное состояние):

a) б)

2. Построить композицию машин Тьюринга по паре состояний и найти результат применения композиции к слову Р ( —заключительное состояние машины ):

 

 

 

3. Построить машину Тьюринга, вычисляющую функцию :

4. По программе машины Тьюринга Т записать аналитическое выражение для функций и , вычисляемых машиной Т (в качестве начального состояния берется , а в качестве заключитель­ного — ):

 

 

T:

 

 

5. Построить машину Тьюринга, преобразующую один машин­ный код в другой. Решетчатый код с заданной совокупностью слов, расположен­ных на соответствующих решетках (1-й, 2-й и т.д.), преобразуется в l -кратный код с указанным значением l:

 

Вариант 13

1. По заданной машине Тьюринга Т и начальной конфигура­ции К₁ найти заключительную конфигурацию ( — заключительное состояние):

a) б)

2. Построить композицию машин Тьюринга по паре состояний и найти результат применения композиции к слову Р ( —заключительное состояние машины ):

 

 

 

3. Построить машину Тьюринга, вычисляющую функцию :

4. По программе машины Тьюринга Т записать аналитическое выражение для функций и , вычисляемых машиной Т (в качестве начального состояния берется , а в качестве заключитель­ного — ):

 

T:

 

 

5. Построить машину Тьюринга, преобразующую один машин­ный код в другой. Решетчатый код с заданной совокупностью слов, расположен­ных на соответствующих решетках (1-й, 2-й и т.д.), преобразуется в l -кратный код с указанным значением l:

 

Вариант 14

1. По заданной машине Тьюринга Т и начальной конфигура­ции К₁ найти заключительную конфигурацию ( — заключительное состояние):

a) б)

2. Построить композицию машин Тьюринга по паре состояний и найти результат применения композиции к слову Р ( —заключительное состояние машины ):

 

 

 

3. Построить машину Тьюринга, вычисляющую функцию :

4. По программе машины Тьюринга Т записать аналитическое выражение для функций и , вычисляемых машиной Т (в качестве начального состояния берется , а в качестве заключитель­ного — ):

 

T:

 

 

5. Построить машину Тьюринга, преобразующую один машин­ный код в другой. Заданный l -кратный код набора преобразуется в решетчатый код

(функционирование машины не должно зависеть от зна­чения l).

 

Вариант 15

1. По заданной машине Тьюринга Т и начальной конфигура­ции К₁ найти заключительную конфигурацию ( — заключительное состояние):

a) б)

2. Найти результат применения итерации машины Т по паре состояний ( , ) к слову Р (заключительными состояниями являют­ся и ):

				—	—

 

i=1, T:

 

 

3. Построить машину Тьюринга, вычисляющую функцию :

4. По программе машины Тьюринга Т записать аналитическое выражение для функций и , вычисляемых машиной Т (в качестве начального состояния берется , а в качестве заключитель­ного — ):