Студопедия Главная Случайная страница Задать вопрос

Разделы: Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

Вычислимые функции. 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. По заданной машине Тьюринга Т и начальной конфигура­ции К1 найти заключительную конфигурацию ( — заключительное состояние):

a) б)

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

 

 

 



 

 

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

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

 

 

 

T:

 

 

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

 

Вариант 13

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

a) б)

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

 

 

 



 

 

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

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

 

 

T:

 

 

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

 

Вариант 14

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

a) б)

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

 

 

 



 

 

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

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

 

 

T:

 

 

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

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

 

Вариант 15

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

a) б)

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

 

 

i=1, T:

 

 

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

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

 

 







Дата добавления: 2015-09-07; просмотров: 218. Нарушение авторских прав

Studopedia.info - Студопедия - 2014-2017 год . (0.017 сек.) русская версия | украинская версия