Автор Графиня Помподур задал вопрос в разделе Техника
Дискретная математика. как работает машина Тьюринга? объясните подробно. и получил лучший ответ
Ответ от Вова лампочкин[новичек]
В реальности такой машины нет, это абстрактный механизм, представляющий собой бесконечную ленту, разделенную на ячейки и считываютще-записывающую головку. Машина работае в соответствии со своей спецификацией (набором правил) . Которая определяет поведение машины. Например, можно представить машину с двумя правилами:
1) Если в текущей ячейке записан символ "А" и машина находится в состоянии 1, то нужно записать в ячейку Б и переместиться на один шаг вправо, а состояние изменить на 2.
2) Если в текущей ячейке записан символ "А" и машина находится в состоянии3, то нужно записать переместиться на один шаг вправо, а состояние изменить на 1.
Такое правило приведет к тому, что машина заменит на ленте все символы А, стоящие на нечетных местах на Б, а А, стоящие на четных местах оставит без изменения (предполагается, конечно, что в начальном состоянии машина находится в состоянии 1, четность определеняется от текущей позиции и лента заполнена справа символами А) .
То есть, нельзя рассказать подробно, как работает МТ вообще, только конкретные реализации. Поскольку ее работа зависит от начального состояния "головки", состоянием ленты и "программы", представленной в виде правил перехода из состояния в сотсояние. Там есть еще ньюансы, например детерминированность, множество лент и т. п.
Так не обЪяснишь в 2-х словах, возникает много сопутствующих вопросов, требующих обЪяснения, но в принципе как-то так.
В состав машины Тьюринга входит бесконечная в обе стороны лента (возможны машины Тьюринга, которые имеют несколько бесконечных лент) , разделённая на ячейки, и управляющее устройство, способное находиться в одном из множества состояний. Число возможных состояний управляющего устройства конечно и точно задано.
Управляющее устройство может перемещаться влево и вправо по ленте, читать и записывать в ячейки ленты символы некоторого конечного алфавита. Выделяется особый пустой символ, заполняющий все клетки ленты, кроме тех из них (конечного числа) , на которых записаны входные данные.
Управляющее устройство работает согласно правилам перехода, которые представляют алгоритм, реализуемый данной машиной Тьюринга. Каждое правило перехода предписывает машине, в зависимости от текущего состояния и наблюдаемого в текущей клетке символа, записать в эту клетку новый символ, перейти в новое состояние и переместиться на одну клетку влево или вправо. Некоторые состояния машины Тьюринга могут быть помечены как терминальные, и переход в любое из них означает конец работы, остановку алгоритма.
Машина Тьюринга называется детерминированной, если каждой комбинации состояния и ленточного символа в таблице соответствует не более одного правила. Если существует пара «ленточный символ — состояние» , для которой существует 2 и более команд, такая машина Тьюринга называется недетерминированной.