2015-05-10
447
В начальном состоянии на ленте имеем: 
После работы машины Тьюринга на ленте должно быть: 
Программа такой машины, например, такая:
Машина, построенная таким образом, вначале, двигаясь вправо, заменяет нуль, разделяющий массивы единиц, единицей; затем, пройдя массив единиц, начинает движение влево, заменяя две последние единицы нулями.
Пример 3. Найти функцию, получаемую из g(x)= x, h(x, y,z)= zy + z с помощью операции примитивной рекурсии.
