Определение вычислимой функции

Композиции машин Тьюринга. Тезис Тьюринга

1°. Машина последовательной обработки. Пусть и – машины Тьюринга в одном алфавите. Построим третью машину Тьюринга, работа которой будет равносильна последовательной работе машин и .

Пусть машина имеет множество состояний , а – . Назначим заключительное состояние машины начальным состоянием машины . Определим машину более точно. Пусть она имеет множество состояний , а ее команды получаются из команд машин и следующим образом:

– в командах машины всюду заменим на ;

– в командах машины всюду заменим на .

Такую композицию машин и называют машиной последовательной обработки и обозначают , а также изображают блок-схемой СЛЕДОВАНИЕ (рис. 1).

Рис. 1. Структура СЛЕДОВАНИЕ

Пример 4. Композиция машин “+1” и дает машину, которая после прибавления 1 возвращает головку на правый символ результата. Программа новой машины:

2°. Машина условного перехода. Пусть , и – машины Тьюринга в одном алфавите. Машина имеет множество внутренних состояний , среди которых два заключительных. Машина – , машина – .

Построим машину, которая работает следующим образом: сначала записанное на ленту слово обрабатывает машина , которая в зависимости от процесса обработки может остановиться либо в состоянии , либо в состоянии . В первом случае образовавшееся на ленте слово обрабатывается машиной , во втором – .

Для построения такой машины надо выполнить действия:

1) переобозначить состояния машин и :

, …, ;

, …, ;

2) заменить в программе машины на , на и добавить к измененному таким образом тексту программы машины программы машин и с переобозначенными состояниями.

Построенная композиция машин , и называется машиной условного перехода и обозначатся блок-схемой РАЗВЕТВЛЕНИЕ (рис. 2).

Если в качестве одной из машин или взять машину , то получим структуру ЦИКЛ (рис. 3).

Рис. 2. Структура РАЗВЕТВЛЕНИЕ Рис. 3. Структура ЦИКЛ

Пусть функция определена на подмножестве множества всех наборов чисел из расширенного натурального ряда и принимающая значения также из .Такого рода функции называются частичными функциями счетнозначной логики. Обозначим через множество всех частичных функций счетнозначной логики.

Функция называется вычислимой, если существует машина Тьюринга такая, что:

1) при машина , будучи применена к основному коду и находясь в начальном состоянии над его левой единицей, останавливается и в заключительном состоянии на ленте выдает код для ;

2) при машина , будучи применена к основному коду и находясь в начальном состоянии над его левой единицей, либо не останавливается, либо останавливается, но при этом запись на ленте отлична от кода для .

Обозначим через класс всех вычислимых функций. Очевидно, .

Машина Тьюринга реализует (вычисляет) функцию правильным образом, если:

1) при машина , будучи применена к основному коду и находясь в начальном состоянии над его левой единицей, останавливается и в заключительном состоянии на ленте выдает код для ; при этом останов происходит над левой единицей кода для ;

2) при машина , будучи применена к основному коду и находясь в начальном состоянии над его левой единицей, либо не останавливается.

Лемма. Если – вычислимая функция, то существует машина Тьюринга, которая вычисляет ее правильным образом.