Машины Тьюринга (автор алан тьюринг) – 3-й способ определения вычислимых функций

Суть способа: лента с “0” и “1” поступает на вход «черного ящика» – ЭВМ. Черный ящик – ЭВМ – используется для входной ленты как пространство памяти ячеек для вычисления в виде инструкций для перехода из одного состояния в другое (модель конечного автомата).

Т.е., «машина Тьюринга» – функция перехода под действием входных данных из одного состояния в другое.

Один шаг действия может быть 3-х типов:

а) предыдущий символ ячейки ленты стирается, а пишется символ (может быть старый); б) лента сдвигается вправо (П) или влево (Л); в) указывается следующая инструкция (ее номер).

Определение 1: Машина Тьюринга – это функция такая, что для некоторого натурального числа область определения этой функции есть подмножество множества , а область значений есть подмножество множества

Например, пусть . То есть, когда машина дойдет до инструкции , а на обозреваемой ячейке написан символ 1, она его стирает, и оставляет 0. Ленту передвигает влево и переходит к инструкции . Если инструкция не определена, то, дойдя до инструкции , а на ячейке написан 1, то машина останавливается.

Входные данные и выходные данные – это строчки из 1, разделенные 0.

Пусть - строчка из 1 длины . Тогда строка, состоящая из строчек из 1, разделенными 0.

Определение 2: Пусть область определения местной функции . Функция называется «вычислимой», если существует машина Тьюринга такая, что как только начинает с инструкции , обозревая самый левый символ строки (вся остальная часть ленты пуста) тогда:

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

б) если значение не определено, то никогда не останавливается.

ЗАМЕАНИЕ 1: Существует бесконечное число машин Тьюринга, для каждой из которых соответствует своя вычислимая функция.

ЗАМЕАНИЕ 2: Для любой вычислимой функции имеется бесконечное число машин Тьюринга.

ПРИМЕР: построим машину Тьюринга для «». Зададим функцию :

; ; ; ;

; ; ; .

Например, ; обозреваемый символ выделен жирным шрифтом и почеркнут.