Зачем нужна машина Тьюринга

Щас я вам объясню, для чего нужно прочитать о том, что такое машина Тьюринга. Прочитать, что это такое, можно везде. А вот зачем она была создана, непонятно. Поэтому... ссылаюсь на слова Лешки, пересказываю, так сказать.

Скажем, давным-давно... А на самом деле до создания машины Тьюринга создавались машины для выполнения различных действий. Например, нужно взять логарифм, нука, а давайте-ка склепаем машинку, которая будет считывать число и брать логарифм. Или нужно, скажем, два числа сложить — вот вам и машина для сложения двух чисел. Да и сейчас существуют такие машины, например, калькуляторы. Что они могут делать? Складывать, вычитать, умножать, а инженерные — даже брать косинус или синус. Получается эти тупые машинки, кроме как записанные в них действия, исполнять ничего не могли и не могут.

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

Отступление. Собственно, как работает машина Тьюринга, рассказывать ни к чему, как я уже сказала, это можно найти очень легко. Поэтому будем полагать, что вы уже знаете, как она работает.

Ну какие-то просты алгоритмы машина Тьюринга выполняет, это бесспорно. Но как насчет сложненьких? А, например, как бы организовать цикл с помощью МТ? Или как сообразить ветвление? Оказывается, существуют теоремы, которые доказывают то, что МТ может выполнять циклы и ветвления, что говорит нам, что с помощью очень простого механизма можно составлять программы из простых блоков типа ветвления и циклов, а значит, можно запрограммировать все, что может быть запрограммировано. И тут по идее должен идти кусок объяснения того, что существуют и невычислимые функции, а следовательно, неразрешимые задачи, и эти задачи нельзя решить с помощью МТ. Вот как.

Но круче машины Тьюринга никто ничего не придумал, поэтому все языки программирования, которыми мы сейчас пользуемся могут запрограммировать не больше, чем машина Тьюринга. Отсюда появилось понятие полноты по Тьюрингу, что означает, что язык (или что-либо другое) полный по Тьюрингу в том случае, если на нем можно записать все алгоритмы, работающие на машине Тьюринга. И доказать, что язык — полный по Тьюрингу можно, написав на нем эмулятор машины Тьюринга. Вот такие пироги.

С точки зрения математики пост — фуфло, зато понятно, нафига нам оказалась нужна машина Тьюринга. Ну и вообще-то писать алгоритмы под эту машину — интересная головоломка. Верю тем, кто говорит, что после программирования exp(x) на машине Тьюринга, он действительно понял, что такое алгоритм. Пока не пробовала, но это интересная задачка.

Комментте.