В этом разделе мы приведем примеры вычислений на машинах Тьюринга и рассмотрим некоторые общие приемы, позволяющие комбинировать программы различных м. Т. для получения более сложных вычислений. Будем считать, что ячейки ленты м.Т. занумерованы от -? до +? , причем в начальной конфигурации головка находится в 1-ой ячейке:
Пример 9.2.Функция f(x)=x+1
Унарное кодирование.
Пусть м.Т.
Бинарное кодирование.
Пусть м.Т.
Нетрудно видеть, что эта машина в состоянии q0 находит младший разряд двоичного входа, затем в состоянии q1, идя справа налево, заменяет единицы на нули до тех пор, пока не находит 0 (или
Пример 9.2. Копирование.
Рассмотрим функцию копирования (дублирования) слов в алфавите ?: copy(x)= x*x (мы предполагаем, что *
Для ее реализации используем один из типичных приемов Тьюрингова программирования - { it расширение алфавита}.Пусть ?'= {a' | a
Из этого описания непосредственно следует, что