• Математические основы информатики А. Гейн. Машина Тьюринга

Текст задания

3.1 Работа машины Тьюринга описана следующей функциональной схемой:

Определите, какое сообщение будет на ленте после окончания работы машины, и укажите (например, * над ячейкой), напротив какой ячейки в этот момент будет находиться ее пишущий блок.


3.2 На ленте машины Тьюринга записана строка, состоящая из символов “*” и символов “#” (вперемежку без пробелов). Один из возможных вариантов такой строки приведен на рис. 2.

Рис. 2

Для приведенной ниже функциональной схемы определите, для решения какой задачи она предназначена. В качестве ответа укажите закономерность, связывающую исходную последовательность с результирующей.


3.3 В задании 8 из раздела "Вопросы и задания" Параграфа 2 Лекция 2 (стр. 46) машина Тьюринга удаляет из исходного сообщения все знаки "+". Проанализировав программу МТ, заданную в виде таблицы, укажите, что выполняет эта машина Тьюринга в каждом состоянии.

Задания 3.4-3.5 будут проверяться тестированием на имитаторе машины Тьюринга "Алго2000" с помощью системы тестов. Сумма баллов по всем тестам одного задания равна 5. Считается, что на ленте первоначальная информация записана корректно (т.к. в точности соответствует условию). Количество внутренних состояний - на усмотрение решающего задачу.

3.4 На ленте записана последовательность из n символов “*” (n – натуральное число). Составьте функциональную схему для машины Тьюринга, с помощью которой на ленте вместо исходной последовательности будет записана последовательность из n/2 звездочек. (Все звездочки в выходном слове записаны непрерывно, без пробелов.)

Пусть внешний алфавит состоит из символа “a0”, цифр 0, 1, 2, ..., 9, а также символов “+” и “=”. На ленту записан пример на сложение двух натуральных чисел в десятичной системе счисления. Образец:

Составьте функциональную схему для машины Тьюринга, с помощью которой на ленте будет записана сумма этих чисел. Ответ требуется записать после знака “=”.


Решение

Решение контрольной работы оформлено в виде архива, который содержит отчет в Word по заданиям 3.1-3.3 и файлы с программами, созданные в программе-имитаторе машины Тьюринга "Алго2000" для заданий 3.3-3.4. Для получения решения необходимо оформить заказ и оплатить его.


Написать отзыв

Внимание: HTML не поддерживается! Используйте обычный текст!
    Плохо           Хорошо

Математические основы информатики А. Гейн. Машина Тьюринга

  • Дисциплина: Информатика
  • Код работы: КО-93
  • Работу выложил: Администратор
  • 450.00 р.




Смотрите также

Математические основы информатики А. Гейн. Графы

Математические основы информатики А. Гейн. Графы

Все графы, фигурирующие в контрольной работе, обыкновенные, без петель и кратных ребер.4.1. Существу..

450.00 р.

Математические основы информатики А. Гейн. Логические модели в информатике

Математические основы информатики А. Гейн. Логические модели в информатике

При выполнении заданий 5.1 и 5.2 перечислите номера всех правильных ответов.5.1. Высказывание &..

450.00 р.

Математические основы информатики А. Гейн. Математические модели формальных исполнителей

Математические основы информатики А. Гейн. Математические модели формальных исполнителей

2.1. Для автомата, изображенного на рис. 1, определите, в каком состоянии он будет находиться п..

300.00 р.

Математические основы информатики А. Гейн. Алгоритм и свойства алгоритма

Математические основы информатики А. Гейн. Алгоритм и свойства алгоритма

В приведенных ниже заданиях ваш ответ о том, конечен или нет предложенный алгоритм, требуется обосно..

200.00 р.

Теги: Алго2000

Не подошла работа?

Узнайте стоимость написания работы по Вашему заданию

(это быстро и бесплатно)

Узнать стоимость

Спасибо, не надо