Машина Тьюринга — математическая абстракция,

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

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

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

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

            Машина Тьюринга была предложена Аланом Тьюрингом в 1936 году для формализации понятия алгоритма.

            Те́зис Чёрча—Тью́ринга: любая интуитивно вычислимая функция является частично вычислимой, или, эквивалентно, может быть вычислена с помощью некоторой машины Тьюринга.

            Физический тезис Чёрча—Тьюринга : любая функция, которая может быть вычислена физическим устройством, может быть вычислена машиной Тьюринга.

Ссылка на основную публикацию
Adblock detector