Задачи.

Используя элементарные машины и операции над машинами, постройте:

а) машину Тьюринга, которая по записи набора чисел x₁, х₂,..., х_n на ленте выдает в качестве результата набор чисел x₁, х₂,..., х_n, 2, воспринимаемый в стандартном положении; Решение: С◦A◦A

б) машину Тьюринга, которая по записи числа на ленте в качестве результата выдает число, увеличенное на единицу и записанное через одну пустую ячейку от данного (иными словами, машину, вычисляющую функцию прибавления единицы f(a) = = а+1). Построить машину Тьюринга означает построить программу машины, а затем проверить, ту ли машину построили, имитируя ее работу для конкретных записей на ленте. При составлении программ для реальных вычислительных машин эту проверку называют отладкой программы. Решение:

Какие операции выполняют машины:

а) . Решение: Справа от данного числа будет две копии этого числа, разделенные одной пустой ячейкой;

б) R². Решение: Переход вправо через одно число;

в) R^k, k³1. Решение: Переход вправо через k чисел;

г) L^k, k³1 Решение: Переход влево через k чисел;

д) С°А⁵ Решение: Запись 5 справа от текущего числа;

е) T₁°A⁴ Решение: Выдать число, увеличенное на четыре и записанное через одну пустую ячейку от данного.

Постройте машину Тьюринга Т₂, которая по записи набора чисел x₁, х на ленте в качестве результата записывает справа от набора через одну пустую ячейку первое число этого набора. Решение:

Составьте программу машины: а) С°А³; б) Т₁°А⁴.

Составьте программу машины Тьюринга Т_x+y, которая по записи набора чисел х, у выдает запись числа, являющегося их суммой, т. е. вычисляющей функцию S(x, y) = x+y. Решение: , где через С_m обозначена машина из примера 11.