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

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

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

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

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

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

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

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

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

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

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

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

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

, …,;

, …,;

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

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

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

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

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

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

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

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

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

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

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

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

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

Дата добавления: 2014-01-04