Реализация машины Тьюринга

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

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

Другой интересный вывод связан с возможностью реализации машины Тьюринга на языке высокого уровня. С помощью последовательности операторов, выбора (if-then-else), цикла (while) и перехода (goto) любую программу машины Тьюринга можно реализовать. Однако справедливо и более сильное утверждение: оператор перехода в этом наборе лишний. Действительно, пусть state — переменная типа состояние, symbol — переменная типа символ. Пусть элементарными операциями языка являются Читатъ(с) — чтение очередного символа из обозреваемой ячейки входной ленты (или моделирующего ее массива) и помещение его в переменную с, Писатъ(с) — печатать символ с в обозреваемую ячейку входной ленты и Сдвиг (D) — имитация сдвига головки чтения-записи по рабочей ленте МТ (фактически изменение индекса читаемого элемента одномерного массива).

Отсюда следует важный вывод: любую машину Тьюринга (и, следовательно, любой алгоритм) можно реализовать на языке высокого уровня с использованием только трех управляющих конструкций: последовательность, выбор и цикл. Тем самым мы доказали известную основную теорему структурного программирования, доказанную впервые совсем из других соображений Бомом и Якопини. Смысл этой важнейшей теоремы и более широко, структурного программирования как подхода в целом, состоит в том, что для спецификации алгоритмов достаточно очень небольшого числа программных структур — последовательности, выбора и цикла, каждая с одной точкой входа и одной точкой выхода. Использование только этих простых конструкции проясняет соотношение между статическим текстом программы и возможными динамическими путями всех выполнений программы.