Полезное:
Как сделать разговор полезным и приятным
Как сделать объемную звезду своими руками
Как сделать то, что делать не хочется?
Как сделать погремушку
Как сделать так чтобы женщины сами знакомились с вами
Как сделать идею коммерческой
Как сделать хорошую растяжку ног?
Как сделать наш разум здоровым?
Как сделать, чтобы люди обманывали меньше
Вопрос 4. Как сделать так, чтобы вас уважали и ценили?
Как сделать лучше себе и другим людям
Как сделать свидание интересным?
Категории:
АрхитектураАстрономияБиологияГеографияГеологияИнформатикаИскусствоИсторияКулинарияКультураМаркетингМатематикаМедицинаМенеджментОхрана трудаПравоПроизводствоПсихологияРелигияСоциологияСпортТехникаФизикаФилософияХимияЭкологияЭкономикаЭлектроника
|
Машина Тьюринга⇐ ПредыдущаяСтр 13 из 13 Теоретические сведения Основные свойства алгоритма дискретности, детерминированности, массовости и результативности позволяют представить процесс вычисления какой-либо числовой функции с помощью абстрактной математической машины. Эта машина за конечное число шагов из исходных числовых данных в соответствии с заданными правилами может получить искомый числовой результат. Такая модель алгоритма была предложена английским математиком Тьюрингом в конце 30-х годов прошлого столетия, что почти на два десятилетия опередило появление электронных вычислительных машин и послужило их теоретическим прообразом. Машина Тьюринга состоит из информационной ленты, считывающей и записывающей головки и управляющего устройства. Информационная лента бесконечной длины представляет собой последовательность ячеек, в каждую из которых может быть записан в точности только один символ из множества символов алфавита А = { a0; a1; a2;... an}; последовательность символов на ленте формирует слово a = (a1; a2;... ai). Информационную ленту чаще всего называют внешней памятью машины Тьюринга; поскольку символы на информационной ленте предназначены для считывания, то множество этих символов тождественно множеству терминальных символов формальной грамматики. Один из символов алфавита А выделяют, например, a0 и называют его пустым. Его наличие в ячейке означает, что она пустая. Считывающая-записывающая головка обозревает одну ячейку информационной ленты, передает информацию о содержимом ячейки в управляющее устройство и по указанию последнего сохраняет или изменяет содержимое ячейки. Управляющее устройство представляет собой такой механизм, который на каждом шаге вычисления находится в одном из множества состояний Q = {q1; q2;... qm}; в зависимости от состояния управляющего устройства qi и считанного символа aj из обозреваемой ячейки информационной ленты возбуждается команда на стирание или запись символа в обозреваемую ячейку, перевод управляющего устройства в новое состояние и перемещение головки на соседнюю ячейку информационной ленты; множество состояний управляющего устройства чаще всего называют внутренней памятью машины Тьюринга; поскольку символы внутренней памяти не выводятся на информационную ленту, то множество этих символов тождественно множеству нетерминальных символов формальной грамматики; среди всех состояний управляющего устройства следует выделить q1 – начальное состояние («старт») и q0 – конечное состояние, («стоп»), что облегчит формализацию протоколов отдельных машин Тьюринга и последующую композицию для реализации сложных вычислений. Для формализации перемещений головки относительно информационной ленты введем дополнительный алфавит W = {R; L; S}, где R – означает перемещение головки вправо на одну ячейку информационной ленты, L – влево на одну ячейку и S – останов. Работа машины происходит по программе, состоящей из отдельных команд. Структура команды имеет вид: где - символ, считываемый головкой с ленты, - состояние, в котором находится устройство управления машины, - символ, который головка записывает в обозреваемую ячейку, - состояние, в которое переходит устройство управления машины, W - команда перемещения головки. Построить машину Тьюринга – означает написать программу ее работы. Машина Тьюринга останавливается только в том случае, если на очередном шаге управляющее устройство генерирует состояние q0. Результатом работы машины Тьюринга будет заключительное слово на информационной ленте, представляющее искомый результат вычисления по заданному алгоритму. В дальнейшем будем полагать, что алфавит машины Тьюринга состоит из двух символов {0, 1}, где 0 – пустой символ, а 1 – символ занятой ячейки. в этом алфавите любое целое неотрицательное число k представляется k+1 символами 1, записанными в соседних ячейках ленты. в этом случая число 0 будет записано так …010…
Пример. Построить машину Тьюринга, вычисляющую функцию . Определим порядок вычисления значения этой функции машиной Тьюринга. Так как результат должен представлять массив из занятых ячеек, то где - число ячеек, занятых аргументом x, то вычисление организуем следующим образом. В ячейку, занятую аргументом x, вместо символа 1 записываем пустой символ 0. в каждом таком случае символ 1 записывается в двух ячейках, представляющих результат. Этот результат формируем в виде массива ячеек, расположенных справа от массива ячеек, занятых аргументом x, через одну пустую ячейку. Когда вместо всех ячеек, занятых аргументом x, будут только пустые ячейки, в новом массиве занятых ячеек удаляется одна ячейка с символом 1. Программа работы машины Тьюринга, вычисляющая функцию , имеет вид: - удалена одна занятая ячейка аргумента. - читаются занятые ячейки аргумента. - найдена разделяющая пустая ячейка. - читаются занятые ячейки результата. - заполнена одна пустая ячейка результата. - заполнена вторая ячейка результата. - просматриваются в обратном порядке занятые ячейки результата. - найдена пустая разделяющая ячейка. - найдена вторая пустая ячейка. - снова читается пустая разделительная ячейка. - удаляется один занятый символ. Конец. - найдена занятая ячейка аргумента. - просматриваются в обратном порядке занятые ячейки аргумента. - найдена пустая ячейка перед занятыми ячейками аргумента.
|