Машины Тьюринга
Основы математической теории цифровых вычислительных машин были разработаны А. М. Тьюрингом в 1936 г. в классическом труде «О вычислимых числах и их применении к проблеме разрешения». Он определил класс вычислительных машин, которые сейчас называются машинами Тьюринга. Эти машины в основном состоят из бесконечной бумажной ленты и вычислительного устройства, которое имеет конечное число внутренних состояний и способно считывать с одной ячейки ленты, писать в этой ячейке и передвигать ленту на одну ячейку вправо или влево. В каждый данный момент времени вычислительное устройство находится в определенном состоянии и считывает то, что записано в данной ячейке ленты. Следующая операция определяется- текущим состоянием и прочитанным символом. Эта операция состоит в принятии нового состояния и в написании нового символа (вместо уже прочитанного) или в смещении ленты вправо или влево. Машины этого типа могут производить операции над числами при наличии соответствующего кода для представления символов. Например, в машине Тьюринга
печатаются окончательные ответы в виде двоичного кода в особых ячейках ленты при использовании других ячеек для промежуточных вычислений.
Можно показать, что такие устройства образуют исключительно большой класс вычислительных машин. Обычные цифровые вычислительные машины, которые не содержат случайных или вероятностных элементов, эквивалентны некоторой машине Тьюринга. Любое число, которое может быть вычислено с помощью этих машин или фактически получено любым обычным способом, может быть вычислено и с помощью соответствующей машины Тьюринга. Однако, как показал Тьюринг, существуют задачи, которые не могут быть решены, и некоторые числа, которые не могут быть вычислены ни на какой машине Тьюринга. Например, невозможно создать такую машину Тьюринга, которая могла бы в случае, если в нее ввести соответствующим образом закодированное описание другой машины этого же типа, всегда давать верный ответ на вопрос: может ли вторая машина продолжать бесконечно печатать символы в соответствующие места ленты, предназначенной для выдачи окончательного ответа. Первая машина может на каком-то этапе сорваться в бесконечный цикл. Существование таких механически неразрешимых проблем весьма интересно для логиков.
Тьюрингом была также высказана интересная мысль об универсальной машине, называемой сейчас универсальной машиной Тьюринга. Эта машина обладает следующим свойством: если на ленте этой машины напечатано соответствующим образом закодированное описание некоторой машины Тьюринга и первая машина пущена в соответствующей точке и в соответствующем состоянии, она действует как вторая машина, т. е. выполняет (обычно с гораздо меньшей скоростью) те же самые операции, которые выполняла бы моделируемая машина. Тьюринг показал, что такая универсальная машина может быть создана. Она может, конечно, вычислить любое вычислимое число. Большинство цифровых вычислительных машин при условии, что они имеют память неограниченной емкости определенного типа, эквивалентны универсальным машинам Тьюринга и могут в принципе моделировать любую другую вычислительную машину и вычислять любое вычислимое число.
Результаты работы Тьюринга были обобщены и переформулированы различным образом. Интересным обобщением является понятие 
-вычислимости. Оно относится к классу таких машин Тьюринга, которые имеют ту дополнительную особенность, что они могут на какой-то стадии расчета задать вопрос второму устройству - «оракулу» и использовать его ответы для дальнейших вычислений. «Оракул» может дать ответы на некоторые вопросы, которые не в состоянии решать обычная машина Тьюринга, и, следовательно, его введение позволяет решать гораздо более широкий класс задач.
