Що реалізує така машина Тьюрінга, якщо головка знаходиться ліворуч?

Довести примітивну рекурсивність функції  f(x,y)=x-y. Вважаємо, що x>y, a  функція x-1 є примітивно рекурсивною функцією. Продемонструвати на одному прикладі.

Які два види продукцій можливі в нормальних алгоритмах Маркова?

Яким результатом буде застосування цієї машини до зображеного на стрічці слова?

Часткові функції, які отримують з функцій системи σ

 і найпростіших функцій  із застосуванням скінченної кількості операторів

суперпозиції та примітивної рекурсії, називають _____________ відносно

системи σ.