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

T:

 

 

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

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

 

Вариант 16

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

a) б) в)

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

				—	—

i=1, T:

 

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

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

 

T:

 

 

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

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

 

Вариант 17

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

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

				—	—

 

i=1, T:

 

 

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

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

			—

 

T:

 

 

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

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

 

Вариант 18

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

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

				—	—

 

i=1, T:

 

 

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

4. Какие одноместные функции вычисляются всеми такими ма­шинами Тьюринга в алфавите , программы которых содержат только по одной команде?

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

 

Вариант 19

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

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

 

i=1, T:

 

 

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

4. На решетке с шагом l смоделировать работу машины Т, вычисляющей функцию

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

 

Вариант 20

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

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

 

 

i=1, T:

 

 

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

4. На решетке с шагом l смоделировать работу машины Т, вычисляющей функцию

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

 

 

 

СПИСОК ЛИТЕРАТУРЫ

 

1) Галиев Ш.И. Математическая логика и теория алгоритмов. Казанский технический университет им. А.Н. Туполева. 2002. – 262 с.

2) Лавров И.А., Максимова Л.Л. Задачи по теории множеств, математической логике и теории алгоритмов. Издание третье. М.: Физматлит. 1995. – 246 с.

3) Лавров И.А., Максимова Л.Л. Задачи по теории множеств, математической логике и теории алгоритмов. Издание пятое. М.: Физматлит. 2004. – 256 с.

4) Гуц А.К. Математическая логика и теория алгоритмов. Омскийй государственный университет. 2003. – 110 с.

5) Манцев А.П. Математическая логика и теория алгоритмов. 2004. – 89 с.

6) Игошин В.И. Задачи и упражнения по математической логике и теории алгоритмов. М.: Академия. 2007. – 305 с.