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

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

Задачи.






Используя элементарные машины и операции над машинами, постройте:

а) машину Тьюринга, которая по записи набора чисел x1, х2,..., хn на ленте выдает в качестве результата набор чисел x1, х2,..., хn, 2, воспринимаемый в стандартном положении; Решение: С◦A◦A

б) машину Тьюринга, которая по записи числа на ленте в качестве результата выдает число, увеличенное на единицу и записанное через одну пустую ячейку от данного (иными словами, машину, вычисляющую функцию прибавления единицы f(a) = = а+1). Построить машину Тьюринга означает построить программу машины, а затем проверить, ту ли машину построили, имитируя ее работу для конкретных записей на ленте. При составлении программ для реальных вычислительных машин эту проверку называют отладкой программы. Решение:

Какие операции выполняют машины:

а) . Решение: Справа от данного числа будет две копии этого числа, разделенные одной пустой ячейкой;

б) R2. Решение: Переход вправо через одно число;

в) Rk, k³1. Решение: Переход вправо через k чисел;

г) Lk, k³1 Решение: Переход влево через k чисел;

д) С°А5 Решение: Запись 5 справа от текущего числа;

е) T1°A4 Решение: Выдать число, увеличенное на четыре и записанное через одну пустую ячейку от данного.

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

Составьте программу машины: а) С°А3; б) Т1°А4.

Составьте программу машины Тьюринга Тx+y, которая по записи набора чисел х, у выдает запись числа, являющегося их суммой, т. е. вычисляющей функцию S(x, y) = x+y. Решение: , где через Сm обозначена машина из примера 11.







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



Шрифт зодчего Шрифт зодчего состоит из прописных (заглавных), строчных букв и цифр...

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

Практические расчеты на срез и смятие При изучении темы обратите внимание на основные расчетные предпосылки и условности расчета...

Функция спроса населения на данный товар Функция спроса населения на данный товар: Qd=7-Р. Функция предложения: Qs= -5+2Р,где...

Постинъекционные осложнения, оказать необходимую помощь пациенту I.ОСЛОЖНЕНИЕ: Инфильтрат (уплотнение). II.ПРИЗНАКИ ОСЛОЖНЕНИЯ: Уплотнение...

Приготовление дезинфицирующего рабочего раствора хлорамина Задача: рассчитать необходимое количество порошка хлорамина для приготовления 5-ти литров 3% раствора...

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

Методы анализа финансово-хозяйственной деятельности предприятия   Содержанием анализа финансово-хозяйственной деятельности предприятия является глубокое и всестороннее изучение экономической информации о функционировании анализируемого субъекта хозяйствования с целью принятия оптимальных управленческих...

Образование соседних чисел Фрагмент: Программная задача: показать образование числа 4 и числа 3 друг из друга...

Шрифт зодчего Шрифт зодчего состоит из прописных (заглавных), строчных букв и цифр...

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