Практические работы для 11 класса (по учебнику К.Ю. Полякова, Е.А. Еремина)



Практическая работа № 39
«Вычислимые функции»




Файлы-заготовки для выполнения этой практической работы


1. Целое число n записано на ленте в унарной системе счисления (как последовательность из n меток). Напишите программу для машины Поста, которая вычисляет функцию

и таким образом доказывает разрешимость этой задачи. В начальный момент каретка стоит над первой меткой числа.

Ответ:

2. Используя любого универсального исполнителя (машину Тьюринга, машину Поста или нормальный алгорифм Маркова), докажите вычислимость функции

Целое число n записано в унарной системе счисления.

Ответ:






Наверх