Элементарная Машина Тьюринга

Введение

Машина Тьюринга (МТ) — абстрактный исполнитель (абстрактная вычислительная машина). Была предложена Аланом Тьюрингом в 1936 году для формализации понятия алгоритма.

Машина Тьюринга является расширением конечного автомата и, согласно тезису Чёрча — Тьюринга, способна имитировать все другие исполнители (с помощью задания правил перехода), каким-либо образом реализующие процесс пошагового вычисления, в котором каждый шаг вычисления достаточно элементарен.

В состав машины Тьюринга входит бесконечная в обе стороны лента (возможны машины Тьюринга, которые имеют несколько бесконечных лент), разделённая на ячейки, и управляющее устройство, способное находиться в одном из множества состояний. Число возможных состояний управляющего устройства конечно и точно задано.

Управляющее устройство может перемещаться влево и вправо по ленте, читать и записывать в ячейки ленты символы некоторого конечного алфавита. Выделяется особый пустой символ, заполняющий все клетки ленты, кроме тех из них (конечного числа), на которых записаны входные данные.

Управляющее устройство работает согласно правилам перехода, которые представляют алгоритм, реализуемый данной машиной Тьюринга. Каждое правило перехода предписывает машине, в зависимости от текущего состояния и наблюдаемого в текущей клетке символа, записать в эту клетку новый символ, перейти в новое состояние и переместиться на одну клетку влево или вправо. Некоторые состояния машины Тьюринга могут быть помечены как терминальные, и переход в любое из них означает конец работы, остановку алгоритма.[1]

 

 

Описание формальной модели алгоритма на основе рекурсивных функций

Определение понятия примитивно рекурсивной функции является индуктивным. Оно состоит из указания класса базовых примитивно рекурсивных функций и двух операторов (подстановки и примитивной рекурсии), позволяющих строить новые примитивно рекурсивные функции на основе уже имеющихся.

К базовым примитивно рекурсивным фунциям относят:

- нулевую функцию;

- последователь;

- выбор аргумента [2].

Задание: доказать примитивную рекурсивность функции «ближайшее к n простое число».

Текст доказательства….

Протестируем приведённую выше схему вычисления ближайшего к простого числа на конкретных примерах.

Пример 1.

В качестве параметра возьмём простое число 5.

 

======

Тест функции

======

Рисунок 1.1 - Тест алгоритма на числе 5

 

Пример 2:

В качестве параметра возьмём 15:

======

Тест функции

Рисунок 1.2 - Тест алгоритма на числе 15

Аналитическая модель Машины Тьюринга

Элементарная Машина Тьюринга

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

Во входных данных находятся делимое и делитель в унарном коде, разделённые символом «*». В выходных данных к входным должна добавиться конструкция «=<число>», где <число> - результат вычислений в унарном коде.

Пример входных данных: 11111111*111

Пример выходных данных: 11111111*111=11

Ниже приведено описание элементарной машины Тьюринга тремя способами: списком правил переходов, таблицей состояний и графом:

<<Правила переходов>> Рисунок 2.1 - Правила переходов для Машины Тьюринга

2.1.6 Описание Машины Тьюринга таблицей состояний

Таблица 2.1 - Таблица состояний Машины Тьюринга

q\a		*	λ	_	=	#
q0
q1

Продолжение таблицы 2.1

q\a		*	λ	_	=	#
q2
q3
q4
q5
q6
q7
q8
q9
q10
q11

 

Рисунок с графом переходов.

====

Рисунок 2.2 - Граф переходов

 

На рисунке 2.3 приведено тестирование работы Машины Тьюринга для входных данных 11111*11.

Трассировка алгоритма на каком-то контрольном значении Рисунок 2.3 - Тестирование Машины Тьюринга

2.2 Композиция Машин Тьюринга

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

Пример входных данных: 111111

Пример выходных данных: 11111

Ниже привдена блок-схема алгоритма, реализующего вычисление заданного алгоритма:

 

<<<Блок-схема>>

Рисунок 2.4 - Блок схема алгоритма поиска ближайшего к s простого числа

 

В композиции будут участвовать следующие Машины Тьюринга:

- – машина копирования;

- – машина проверки на простоту;

- – машина выбора m-го элемента из n;

- - машина увеличения на единицу;

-

СХЕМА КОМПОЗИЦИИ ИЗ 3 ЛАБЫ Рисунок 2.5 - Композиция Машин Тьюринга

- машина уменьшения на единицу.

Теперь распишем машину , которая используется для проверки числа на простоту.

В композиции будут участвовать машины:

- – машина копирования;

- – машина выбора m-го элемента из n;

- - машина логическое и;

- - машина сравненения;

- - машина установки двойки;

- - машина проверки на равенство двойке;

- - машина проверки на равенство нулю;

- - машина вычисления остатка от деления;

- - машина увеличения на единицу;

- - машина уменьшения на единицу;

- - машина сложения.

СХЕМА КОМПОЗИЦИИ ИЗ 3 ЛАБЫ

Рисунок 2.6 - Композиция машины проверки на простоту