ЗАДАНИЕ 41. Что такое универсальный исполнитель?
2. Опишите устройство и систему программирования машины Тьюринга. 3. Что такое состояние машины Тьюринга? 4.
Сопоставьте устройство машины Тьюринга с устройством компьютера. Какие
устройства машины Тьюринга выполняют те же функции, что и аналогичные
устройства компьютера?
1.
Напишите программу для машины Поста, которая увеличивает (уменьшает)
число в единичной системе счисления на единицу. Каретка расположена
слева от числа. 2. Напишите программу для машины Поста, которая
складывает два числа в единичной системе счисления. Каретка расположена
над пробелом, разделяющим эти числа на ленте. 3. Что делают следующие программы для машины Поста:
а) 1 1 б) 1 ← в) 1 ? 2,3
2 → 2 ? 3,4 2 1 4
3 → 1 3 1 1 3 → 1
4 стоп 4 стоп
Как будет работать каждая из программ при различных начальных состояниях ленты?
| 
