Лекция Машина Тьюринга

Типы алгоритмов. История создания Интенсивный поиск универсального уточнения алгоритма предложил примерно 20 формальных конструкций алгоритмов, которые условно можно разбить на три типа Интенсивный поиск универсального уточнения алгоритма предложил примерно 20 формальных конструкций алгоритмов, которые условно можно разбить на три типа Алгоритмические машины (АМ). Алгоритмические машины (АМ). Функции вычислимые алгоритмом. Функции вычислимые алгоритмом. Исчисления. Исчисления.

Алгоритмические машины (АМ) имеют единственный процессор, выполняющий небольшой набор очень примитивных действий, имеют единственный процессор, выполняющий небольшой набор очень примитивных действий, простую структуру данных (структуру памяти) в виде бесконечной ленты, простую структуру данных (структуру памяти) в виде бесконечной ленты, простую логику (правила) управления процессором. простую логику (правила) управления процессором.

Основные АМ Машина Тьюринга (МТ) предложена Тьюрингом в 1937 г. Машина Тьюринга (МТ) предложена Тьюрингом в 1937 г. Машина Поста (МР) предложена Постом в 1937 г. Машина Поста (МР) предложена Постом в 1937 г. Нормальный алгоритм Маркова (НАМ) предложен Марковым в 1953 г. Нормальный алгоритм Маркова (НАМ) предложен Марковым в 1953 г.

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

Рекурсивные функции на множестве натуральных чисел были предложены Клини в 1938 г. Рекурсивные функции на множестве натуральных чисел были предложены Клини в 1938 г. Конструктивные механизмы рекурсивных функций очень просты, их применение в процессе построения «функции от функции» позволяет явно выстраивать структуру функции в отличие от АМ, где функция определяется процедурно, через последовательность действий. Конструктивные механизмы рекурсивных функций очень просты, их применение в процессе построения «функции от функции» позволяет явно выстраивать структуру функции в отличие от АМ, где функция определяется процедурно, через последовательность действий.

Исчисления. Исчисление функций, вычисляемых на множестве натуральных чисел предложено Эрбраном и Гёделем в 1938 г. Исчисление функций, вычисляемых на множестве натуральных чисел предложено Эрбраном и Гёделем в 1938 г. -исчисление А.Чёрча также может быть отнесено к этому типу алгоритмов, предложено в 1937 г. -исчисление А.Чёрча также может быть отнесено к этому типу алгоритмов, предложено в 1937 г. Формальные грамматики, порождающие языки, предложены Хомским в 1953 – 1956 г. Формальные грамматики, порождающие языки, предложены Хомским в 1953 – 1956 г.

Структура алгоритма (составляющие алгоритма) Процессорная структура. (Исполнитель алгоритма). Процессорная структура. (Исполнитель алгоритма). Во всех теоретических конструкциях алгоритмов и большинстве алгоритмических языках это единственный процессор. Во всех теоретических конструкциях алгоритмов и большинстве алгоритмических языках это единственный процессор. Структуры данных. Структура данных это способ организация записи, хранения и извлечение данных. Структуры данных. Структура данных это способ организация записи, хранения и извлечение данных. Данные – это элементы множеств, которые нужно порождать или распознавать.. Данные – это элементы множеств, которые нужно порождать или распознавать..

Информационная структура алгоритма (ИСА). Структура функций есть описание конструирования функции от функций из базовых. Информационная структура алгоритма (ИСА). Структура функций есть описание конструирования функции от функций из базовых. Логическая структура алгоритма (ЛСА) или программы (ЛСП). ЛСА суть описание организации вычислительного процесса, который управляется состоянием памяти. Логическая структура алгоритма (ЛСА) или программы (ЛСП). ЛСА суть описание организации вычислительного процесса, который управляется состоянием памяти.

Интерпретация МТ. Процессор – в МТ называется управляющей головкой (УГ). Процессор – в МТ называется управляющей головкой (УГ). Структура данных (память процессора) бесконечная лента, разбитая на ячейки, в ячейку может быть записан только один символ Структура данных (память процессора) бесконечная лента, разбитая на ячейки, в ячейку может быть записан только один символ Процесс вычислений происходит по тактам Процесс вычислений происходит по тактам Процесс остановки (остановка) МТ. Процесс остановки (остановка) МТ. Замечание Список правил для МТ не упорядочен Замечание Список правил для МТ не упорядочен

ТЬЮРИНГ Алан Матисон (Turing Alan Mathison) ( ), английский математик. Основные труды по математической логике, вычислительной математике. В годах ввел математическое понятие абстрактного эквивалента алгоритма, или вычислимой функции, получившее затем название «машины Тьюринга». В возрасте 24 лет Тьюринг написал работу "О вычислимых числах", которой суждено было сыграть исключительно важную роль в развитии вычислительной математики и информатики

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

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

Машина Тьюринга состоит из трех частей: ленты, считывающе- записывающей головки и логического устройства Машина Тьюринга состоит из трех частей: ленты, считывающе- записывающей головки и логического устройства Лента выступает в качестве внешней памяти; она считается неограниченной (бесконечной)

Головка неподвижна, а лента передвигается относительно нее вправо или влево. Головка неподвижна, а лента передвигается относительно нее вправо или влево. Машина работает в некотором произвольном конечном алфавите Машина работает в некотором произвольном конечном алфавите A = {, a1…a n} – этот алфавит называется внешним. A = {, a1…a n} – этот алфавит называется внешним. В нем выделяется специальный символ –, В нем выделяется специальный символ –, называемый пустым знаком – его посылка в какую-либо ячейку стирает тот знак, который до этого там находился, и оставляет ячейку пустой. называемый пустым знаком – его посылка в какую-либо ячейку стирает тот знак, который до этого там находился, и оставляет ячейку пустой.

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

Система исполняемых головкой команд предельно проста: Система исполняемых головкой команд предельно проста: на каждом такте она производит замену знака в обозреваемой ячейке ai знаком aj на каждом такте она производит замену знака в обозреваемой ячейке ai знаком aj При этом возможны сочетания: При этом возможны сочетания: j = i – это означает, что в обозреваемой ячейке знак не изменился; j = i – это означает, что в обозреваемой ячейке знак не изменился; i_0, j = 0 означает, что хранившийся в ячейке знак заменяется пустым, т.е. стирается; i_0, j = 0 означает, что хранившийся в ячейке знак заменяется пустым, т.е. стирается; i =0, j_ 0 означает, что пустой знак заменяется непустым (с номером j в алфавите), т.е. производится вставка знака; i =0, j_ 0 означает, что пустой знак заменяется непустым (с номером j в алфавите), т.е. производится вставка знака; i j_ 0 соответствует замене одного знака другим. i j_ 0 соответствует замене одного знака другим.

Команды перемещений ленты на ячейку влево, на ячейку влево, на ячейку вправо на ячейку вправо остаться на месте, т.е. адрес обозреваемой ячейки в результате выполнения команды может либо измениться на 1, либо остаться неизменным. остаться на месте, т.е. адрес обозреваемой ячейки в результате выполнения команды может либо измениться на 1, либо остаться неизменным. команда сдвига ленты влево обозначается R («Right»), сдвига вправо – L («Left»), отсутствие сдвига – S («Stop»).

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

Определение Конфигурация машины- совокупность состояний всех ячеек ленты, состояния ЛУ и положение головки Определение Конфигурация машины- совокупность состояний всех ячеек ленты, состояния ЛУ и положение головки В зависимости от начальной конфигурации возможны два варианта : В зависимости от начальной конфигурации возможны два варианта : после конечного числа тактов машина останавливается по команде остановки; при этом на ленте оказывается конечная конфигурация, соответствующая выходной информации; после конечного числа тактов машина останавливается по команде остановки; при этом на ленте оказывается конечная конфигурация, соответствующая выходной информации; остановки не происходит. остановки не происходит. В первом случае говорят, что данная машина применима к начальной информации, во втором – нет. В первом случае говорят, что данная машина применима к начальной информации, во втором – нет.

Пример Пусть начальной является конфигурация 1q Пусть начальной является конфигурация 1q Такт 1 Обозревается 1, в ЛУ состояние q. Выходная команда q1R, что эквивалентно перемещению головки по отношению ленты на 1 шаг вправо. Следовательно, образуется промежуточная конфигурация 11q111. Такт 1 Обозревается 1, в ЛУ состояние q. Выходная команда q1R, что эквивалентно перемещению головки по отношению ленты на 1 шаг вправо. Следовательно, образуется промежуточная конфигурация 11q111. Такт 2 – аналогичным образом осуществляется переход к конфигурации 111q11. Такт 2 – аналогичным образом осуществляется переход к конфигурации 111q11. Такт 3 – переход к конфигурации 1111q1. Такт 3 – переход к конфигурации 1111q1. Такт 4 –переход к конфигурации 11111q Такт 4 –переход к конфигурации 11111q Такт 5 Обозревается, в ЛУ состояние q. Выходная команда z1S – вместо в ячейку записывается 1, сдвига нет, работа прекращается. Конечная конфигурация z. Такт 5 Обозревается, в ЛУ состояние q. Выходная команда z1S – вместо в ячейку записывается 1, сдвига нет, работа прекращается. Конечная конфигурация z. Задача решена. Задача решена.

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

Алгоритмическая машина Поста Абстрактная машина Поста состоит Абстрактная машина Поста состоит из бесконечной ленты, разделенной на равные секции, из бесконечной ленты, разделенной на равные секции, считывающе-записывающей головки. считывающе-записывающей головки. Каждая секция может быть либо пуста (т.е. в нее ничего не записано), либо заполнена (отмечена – т.е. в нее записана метка). Каждая секция может быть либо пуста (т.е. в нее ничего не записано), либо заполнена (отмечена – т.е. в нее записана метка). Состояние ленты и информация о положении головки характеризуют состояние машины Поста. Состояние ленты и информация о положении головки характеризуют состояние машины Поста.

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

Структура команды Каждая команда имеет следующую структуру Каждая команда имеет следующую структуру xKy, xKy, x – номер исполняемой команды; x – номер исполняемой команды; K – указание о выполняемом действии; K – указание о выполняемом действии; y – номер следующей команды (наследника). y – номер следующей команды (наследника).

Система команд машины

Комментарий к примеру Последовательное исполнение команд 1 и 2 приводит к тому, что головка за два такта работы машины сдвигается на одну позицию вправо. Последовательное исполнение команд 1 и 2 приводит к тому, что головка за два такта работы машины сдвигается на одну позицию вправо. Это передвижение продолжается до тех пор, пока после очередного сдвига под головкой не окажется пустой ячейки – тогда по команде 3 в нее будет поставлена метка Это передвижение продолжается до тех пор, пока после очередного сдвига под головкой не окажется пустой ячейки – тогда по команде 3 в нее будет поставлена метка и по команде 4 машина остановится и по команде 4 машина остановится

Если данные условия не выполняются, происходит безрезультатная остановка машины, т.е. остановка до получения запланированного результата. Если данные условия не выполняются, происходит безрезультатная остановка машины, т.е. остановка до получения запланированного результата. В отличие от этой ситуации, остановка по команде В отличие от этой ситуации, остановка по команде является результативной, т.е. она происходит после того, как результат действия алгоритма получен. является результативной, т.е. она происходит после того, как результат действия алгоритма получен. Кроме того, возможна ситуация, когда машина не останавливается никогда – это происходит, если ни одна из команд не содержит в качестве последователя номера команды остановки или программа не переходит к этой команде. Кроме того, возможна ситуация, когда машина не останавливается никогда – это происходит, если ни одна из команд не содержит в качестве последователя номера команды остановки или программа не переходит к этой команде.