Лекция по Теории Алгоритмов на тему: «Машина Тьюринга»

Лекция рассчитана на одну пару.

Алгоритм является точным математическим понятием. В качестве формальной модели алгоритма исторически первой была модель машины, предложенная англичанином Аланом Тьюрингом в 40-х годах 20-го века. Именно машины Тьюринга получили наибольшее распространение в теоретической математике при изучении свойств алгоритмов. Прежде всего, машины Тьюринга позволили решить многие важные вопросы, связанные с проблемой алгоритмической разрешимости или неразрешимости той или иной проблемы. К этому вопросу мы обратимся несколько ниже.

Машина Тьюринга представляет собой устройство, содержащее пишущую ленту бесконечной длины, разбитую на ячейки Я1, Я2, …, Яn,… . В каждой ячейке может быть записан один и только один символ из входного алфавита машины Тьюринга. В дальнейшем для простоты будем рассматривать алфавит, состоящий всего из двух символов: 0 и 1. При этом также рассматривается пустой “символ” (именно так следует понимать содержимое ячейки, в которой не записан ни 0, ни 1). Пустой символ обычно обозначают как . В начальный момент на ленту записывается какое-то слово. Обычно это слово представляет собой описание некоторой задачи, на которых специализируется данная машина Тьюринга. Кроме ленты, у машины имеется читающая-пишущая головка, которая позволяется считать символ из ячейки или записать в ячейку, непосредственно находящуюся под головкой, какой-то один символ. Машина Тьюринга работает по тактам. Такты машины Тьюринга никак не привязываются к единицам времени, например, секундам. Но именно в тактах измеряется “время”, затрачиваемое машиной Тьюринга на то, чтобы выполнить обработку входного слова. Разумно и сложность задачи связывать с числом тактов, которую необходимо затратить на Машине Тьюринга для ее решения.