Урок 33
Уточнение понятие алгоритма. Универсальные исполнители
§34. Уточнение понятия алгоритма
Содержание урока
Зачем нужно определение алгоритма?
Задачи
Задачи
1. Что делают следующие программы для машины Тьюринга?
В каких случаях эти программы зацикливаются?
2. Предложите программу для машины Тьюринга и начальное состояние ленты, при котором эта программа зацикливается.
3. Составьте программу для машины Тьюринга, которая уменьшает двоичное число на 1.
4. Составьте программы для машины Тьюринга, которые увеличивают и уменьшают на единицу число, записанное в десятичной системе счисления.
5. Составьте программу для машины Тьюринга, которая складывает два числа в двоичной системе, разделенные на ленте знаком «+».
6. Составьте программы для машины Тьюринга, которые выполняют сложение и вычитание двух чисел в десятичной системе счисления.
7. Что делают следующие программы для машины Поста?
Как будет работать каждая из программ при различных начальных состояниях ленты?
8. Напишите программу для машины Поста, которая увеличивает (уменьшает) число в единичной системе счисления на единицу. Каретка расположена слева от числа.
9. Напишите программу для машины Поста, которая складывает два числа в единичной системе счисления. Каретка расположена над пробелом, разделяющим эти числа на ленте.
10. Что делают следующие НАМ, если применить их к символьной цепочке, состоящей из нулей и единиц?
Как будет работать каждая из программ при различных начальных состояниях ленты?
11. Напишите НАМ, который сортирует цифры двоичного числа так, чтобы сначала стояли все нули, а потом — все единицы.
12. Напишите: НАМ, который удаляет поглгдпий символ строки, состоящей из цифр 0 и 1. Какую операцию он выполняет, если рассматривать строку как двоичную запись числа.
13. Напишите НАМ, который умножает двоичное число на 2, добавляя О в конец записи числа.
Следующая страница 
§34. Уточнение понятия алгоритма
Cкачать материалы урока
