Поделиться
Л3-00135.docx
Практическая работа № 39. Вычислимые функции
1. Целое число n записано на ленте в унарной системе счисления (как последовательность из n меток). Напишите программу для машины Поста, которая вычисляет функцию
и таким образом доказывает разрешимость этой задачи. В начальный момент каретка стоит над первой меткой числа.
Ответ:
|
1 |
|
|
2 |
|
|
3 |
|
|
4 |
|
|
5 |
|
|
6 |
|
|
7 |
|
|
8 |
|
2. Используя любого универсального исполнителя (машину Тьюринга, машину Поста или нормальный алгорифм Маркова), докажите вычислимость функции
Целое число n записано в унарной системе счисления.
Ответ:
Материалы на данной страницы взяты из открытых источников либо размещены пользователем в соответствии с договором-офертой сайта. Вы можете сообщить о нарушении.
