Машина поста и тьюринга кратко

Обновлено: 05.07.2024

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

1.3. Машины Тьюринга и Поста

1.3.1. Основные понятия

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

Однако это решение не вполне прямое, так как понятие вычислимой функции является вторичным по отношению к понятию алгоритма. Возникает вопрос, нельзя ли уточнить непосредственно само понятие алгоритма, а затем при его помощи определить и классы вычислимых функций?

Это было сделано в 1936-1937г. Постом и Тьюрингом независимо друг от друга и почти одновременно с работами Чёрча.

Основная идея Поста и Тьюринга заключалась в том, что:

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

Под машинами Поста и Тьюринга понимается некоторая гипотетическая машина, состоящая из следующих частей:

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

Схематично машина может быть представлена следующим образом:

Рассмотрим теперь алгоритмическую систему, предложенную Постом.

В алгоритмической системе Поста информация представляется в двоичном алфавите А=(1,0 ). Таким образом, в каждой ячейке ИЛ можно поместить либо 0, либо 1.

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

3.Сдвинуть ИЛ вправо на одну ячейку и приступить к выполнению i-го приказа;

4.Сдвинуть ИЛ влево на одну ячейку и приступить к выполнению i-го приказа;

6.Окончание работы алгоритма (останов)

Алгоритмы, составленные из любого конечного числа правил, представленных приказами машины Поста, называются алгоритмами Поста.

Доказано, что алгоритмы Поста сводятся к алгоритмам, реализуемым с помощью ч.р.ф. и наоборот, любая ч.р.ф. может быть представлена алгоритмом Поста.

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

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

МТ называется стандартной, если она при сдвиге может предварительно изменить состояние воспринимаемой ячейки.

Пусть алфавит МТ задан в виде множества A=(S0,S1,….Sn)

где S0 соответствует пустой ячейке, а состояния УУ заданы в виде множества Q=(q0,q1,…qm), где q0 соответствует заключительному состоянию.

Конечная совокупность символов алфавита, с которым работает МТ, называется внешним алфавитом, а конечная совокупность состояний УУ – внутренним алфавитом.

Совокупность, образованная последовательностью состояний всех ячеек ИЛ и состоянием УУ, называется конфигурацией машины.

Конфигурация задается в виде слова, описывающего конкретное состояние машины.

Пусть в некоторый момент времени МТ находится в состоянии, представленном на схеме:

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

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

абстрактная схема машины Тьюринга

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

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

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

Машина Поста

Машина Поста – это абстрактная (несуществующая реально) вычислительная машина, созданная для уточнения (формализации) понятия алгоритма. Представляет собой универсальный исполнитель, позволяющий вводить начальные данные и читать результат выполнения программы.
В 1936 г. американский математик Эмиль Пост в статье описал систему, обладающую алгоритмической простотой и способную определять, является ли та или иная задача алгоритмически разрешимой. Если задача имеет алгоритмическое решение, то она представима в форме команд для машины Поста.

Машина Поста состоит из …

1. бесконечной ленты, поделенной на одинаковые ячейки (секции). Ячейка может быть пустой (0 или пустота) или содержать метку (1 или любой другой знак),

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

Текущее состояние машины Поста описывается состоянием ленты и положением каретки. Состояние ленты – информация о том, какие секции пусты, а какие отмечены. Шаг – это движение каретки на одну ячейку влево или вправо. Состояние ленты может изменяться в процессе выполнения программы.

Кареткой управляет программа, состоящая из строк команд. Каждая команда имеет следующий синтаксис:

I K j,

где i - номер команды, K – действие каретки, j - номер следующей команды (отсылка).

Всего для машины Поста существует шесть типов команд:

· V j - поставить метку, перейти к j-й строке программы.

· X j - стереть метку, перейти к j-й строке программы.

· j - сдвинуться вправо, перейти к j-й строке программы.

· ? j₁; j₂ - если в ячейке нет метки, то перейти к j₁-й строке программы, иначе перейти к j₂-й строке программы.

· ! – конец программы (стоп).

Варианты окончания выполнения программы на машине Поста:

1. Команда "стоп" - корректная остановка. Возникает в результате выполнения правильно написанного алгоритма.

2. Выполнение недопустимой команды – нерезультативная остановка. Случаи, когда головка должна записать метку там, где она уже есть, или стереть метку там, где ее нет, являются аварийными (недопустимыми).

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

Лекция №4.Основы алгоритмизации и программирования. Основные конструкции программирования

План лекции

1. Стратегия решения задач и поиск решений

2. Концепции и свойства алгоритмов, реализации алгоритмов

3. Блок-схемы как графическая реализация алгоритмов

4. Основные конструкции программирования

Ключевые слова:алгоритм, свойства, классификация, прогаммирование, конструкция.

Иллюстративный материал:Электронный учебник, слайд, схема.

Устройство машины Тьюринга

Описание машины Тьюринга

Конкретная машина Тьюринга задаётся перечислением элементов множества букв алфавита A, множества состояний Q и набором правил, по которым работает машина. Они имеют вид: q_ia_j→q_i1a_j1d_k (если головка находится в состоянии q_i, а в обозреваемой ячейке записана буква a_j, то головка переходит в состояние q_i1, в ячейку вместо a_j записывается a_j1, головка делает движение d_k, которое имеет три варианта: на ячейку влево (L), на ячейку вправо (R), остаться на месте (N)). Для каждой возможной конфигурации имеется ровно одно правило. Правил нет только для заключительного состояния, попав в которое машина останавливается. Кроме того, необходимо указать конечное и начальное состояния, начальную конфигурацию на ленте и расположение головки машины.

Машина Поста

Принцип работы

Машина Поста состоит из каретки (или считывающей и записывающей головки) и разбитой на секции бесконечной в обе стороны ленты (см. пример ниже). Каждая секция ленты может быть либо пустой — 0, либо помеченной меткой 1. За один шаг каретка может сдвинуться на одну позицию влево или вправо, считать, поставить или стереть символ в том месте, где она стоит. Работа машины Поста определяется программой, состоящей из конечного числа строк. Всего команд шесть:

N. → J	сдвиг вправо
N. ← J	сдвиг влево
N. 1 J	запись метки
N. 0 J	удаление метки
N. ? J₁, J₀	если в ячейке есть метка, то перейти к j₁ строке программы, иначе перейти к j₀ строке программы.
N. Stop	остановка

где N. — номер строки, J — строка на которую переходит управление далее.

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

· работа может закончиться невыполнимой командой (стирание несуществующей метки или запись в помеченное поле);

· работа может закончиться командой Stop;

· работа никогда не закончится.

Пример: вычитание натуральных чисел P — Q

Сложение двух чисел тривиально — достаточно поставить 1 между ними и стереть крайний правый символ у Q. Программа вычитания состоит из последовательного затирания крайних левых меток у Q и правых у P:

1. 0 - стираем левый символ у Q

4. Stop - стоп если затерли Q=0

6. ? 7, 5 - цикл поиска P

7. 0 - стираем правый символ у P

Отметим, что номер команды перехода не указывается, если переход происходит на следующую по порядку строку (для наглядности текста). В 6-ой строке возможно зацикливание, если Q > P (вы можете добавить проверку сами)

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

МП-автомат – устройство, имеющие блок управления, входную ленту, считывающую головку и блок внутренней памяти в виде очереди или стека. Схематическое изображение магазинного автомата представлено на рисунке 69.

Рисунок 69. Автомат с магазинной памятью.

Финитные комбинаторные процессы основаны на формальном описании алгоритмов, как общей проблемы, которые должны при решении частной проблемы должны относиться к общей проблеме.

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

Машина Поста обладает следующим набором инструкций:

1. Пометить ячейку, если она пуста;

2. Стереть метку, если она есть;

3. Переместиться влево на одну ячейку;

4. Переместиться вправо на одну ячейку;

5. Определить наличие метки ячейки;

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

Основные требования к машине Поста:

1. Не возникает коллизий в первой и второй инструкциях;

2. Набор инструкций заканчивается за конечное количество шагов;

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

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

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

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

Автомат может выполнить три элементарных действия:

1. Записать в видимую клетку новый символ;

2. Сдвинуться на одну клетку влево или вправо;

3. Перейти в другое состояние или остаться в прежнем.

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

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

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

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

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