Теория вычислительных процессов. Лабораторная работа №1

ID: 148268
Дата закачки: 21 Декабря 2014
Продавец: wars (Напишите, если есть вопросы)
Посмотреть другие работы этого продавца

Тип работы: Работа Лабораторная
Форматы файлов: Microsoft Word
Сдано в учебном заведении: ******* Не известно

Описание:
1. Найдите аналитический вид функции, кодирующей слова в алфавите V = {а, Ь, c} числами, если функция упорядочения К:

V-> {1, 2, 3} такова, что К(а) = 1, К(Ь) = 2, К(с) = 3.

2. Постройте машину Тьюринга, которая стирает с ленты любое начальное слово и записывает вместо него слово aabba в алфавите {а, b}.

3.На рис. 1.4. (лекции 2) даны примеры стандартных схем. Установить, какие из них тотальны, какие пусты, какие пары схем функционально эквивалентны. Укажите свободные схемы.

4. Докажите, что схемы на рисунке 1.11 (лекция 5) эквивалентны.

5. Изобразите схемы операторов: засылки произвольного числа n в счетчик с := n, умножения на число с := с х n и деления на число с := с/n с помощью трех базовых операторов. Используйте не более одного дополнительного счетчика.

6. Покажите, что предикат (с тod n = 0), где n - некоторое число, а (с mod п) - остаток от деления счетчика на n, можно представить через три базовых оператора и один дополнительный счетчик.

Комментарии: СибГУТИ, 2013 г., оценка: зачет

Размер файла: 93,6 Кбайт
Фаил: