2.3. Машины Тьюринга
2.3.0. Определение машин Тьюринга
Машина Тьюринга (сокращенно МТ) — это автомат, располагающий всеми логическими возможностями, которыми только может обладать реальная вычислительная машина. Поэтому принятое определение вычислимой функции связано лишь с возможностью вычисления ее машиной Тьюринга. МТ состоит из бесконечно длинной ленты, читающей головки, расположенной в некоторой точке ленты, и ЭВМ, которая должна находиться в одном из конечного множества
внутренних состояний. Программа для МТ представляет собой конечное множество правил перехода в форме:
Если ЭВМ находится в состоянии
и на ее ленте прочитан символ
передвинуть читающую головку на
шагов вправо (влево, если
отрицательно) и записать на ленту символ
Затем переключить машину в состояние
Это правило для МТ можно записать в виде
В дальнейшем мы будем предполагать, что нет двух правил перехода с одинаковой левой частью, т. е. что наша машина детерминированная.
МТ можно описать на языке программы с процедурной частью и статической и динамической памятью. Конечное множество правил перехода эквивалентно процедурной части. Внутренние состояния машины эквивалентны возможным состояниям статической памяти. Лента МТ выполняет тройную функцию входа, выхода и динамической памяти. Поскольку МТ может писать на ленте и перемещать ее в обоих направлениях, она может использовать
ленту для хранения любого объема промежуточных результатов. Поскольку направления и величины перемещений ленты не ограничены, любой символ на ленте может быть прочитан МТ без изменения содержимого ленты. Функции чтения и записи машины Тьюринга, таким образом, могут осуществлять извлечение информации из любой ячейки и введение информации в любую ячейку динамической памяти.
Идею восприятия или отвержения цепочки также можно сформулировать на языке действий МТ. Вначале машина находится в состоянии
с пустой лентой, не считая цепочки
первый символ которой располагается непосредственно под читающей головкой. Соответствующие правила перехода применяются до тех пор, пока машина не достигнет состояния
где
как и раньше, есть множество состояний останова. Машина воспринимает
как элемент ее входного языка
если после чтения последнего символа цепочки
машина впервые оказывается в каком-нибудь состоянии из
Число операций с лентой до достижения не ограничено.
Язык
называют рекурсивно перечислимым, если можно построить МТ, воспринимающую все цепочки из
и никакие другие. Язык
называют рекурсивным, если и
и его дополнение, т. е. множество
рекурсивно перечислимы. Стоит немного подробнее обсудить, что же означают эти свойства. Если
— рекурсивный язык, то можно создать МТ, или, что то же самое, программу, распознающую, входит данная цепочка в множество
или нет. Программа может требовать очень мощных функций управления динамической памятью. Рассматриваемая МТ в действительности состоит из двух машин, одна из которых распознает цепочки в
а другая — в
Основная машина просто фиксирует, которая из этой пары машин воспринимает входную цепочку. С другой стороны, допустим, что язык
рекурсивно перечислимый, но не рекурсивный. Тогда основную машину нельзя построить, поскольку невозможно реализовать ее часть для распознавания цепочек в
Наличия же части, распознающей цепочки из
не достаточно, так как, если она будет работать без остановки продолжительное время, мы не узнаем, попала она в цикл при работе с динамической памятью или ей просто нужно больше времени для опознания цепочки.
Эти принципы иллюстрируются в одном очень важном приложении, связанном с искусственным интеллектом. Пусть
— множество правильно построенных выражений
, которые можно вывести из множества
аксиом, применяя правила вывода с логическими связками и, или и не и кванторами некоторые и все. Это множество рекурсивно перечислимо, но не рекурсивно. Ответ на вопрос „Следует ли из фактов S заключение s?“ эквивалентен вопросу „Входит ли s в L?“. Пусть верен ответ „нет“. Тогда
— цепочка в
, возможно, за конечное время установить этот факт не