Машина ТьюрингаTuring machine

Общая информация

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

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

Полнота по Тьюрингу

Полнота по Тьюрингу - это свойство системы реализовать любую вычислимую фукнцию.

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

Универсальная машина Тьюринга

Универсальная машина Тьюринга — машина Тьюринга, которая может моделировать любую другую машину Тьюринга. Получив на вход программу и данные, универсальная машина Тьюринга выдаёт ответ, который выдала бы та машина Тьюринга, чья программа была дана на вход с такими же входными данными.