Главная | Информатика и информационно-коммуникационные технологии | Планирование уроков и материалы к урокам | 11 классы | Практические работы для 11 класса (по учебнику К.Ю. Полякова, Е.А. Еремина) | Практическая работа №39
Практическая работа № 39
«Вычислимые функции»
1. Целое число n записано на ленте в унарной системе счисления (как последовательность из n меток). Напишите программу для машины Поста, которая вычисляет функцию
и таким образом доказывает разрешимость этой задачи. В начальный момент каретка стоит над первой меткой числа.
Ответ:
2. Используя любого универсального исполнителя (машину Тьюринга, машину Поста или нормальный алгорифм Маркова), докажите вычислимость функции
Целое число n записано в унарной системе счисления.
Ответ:
