2.3. Машины Тьюринга

2.3.0. Определение машин Тьюринга

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

Если ЭВМ находится в состоянии и на ее ленте прочитан символ передвинуть читающую головку на шагов вправо (влево, если отрицательно) и записать на ленту символ Затем переключить машину в состояние

Это правило для МТ можно записать в виде

В дальнейшем мы будем предполагать, что нет двух правил перехода с одинаковой левой частью, т. е. что наша машина детерминированная.

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

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

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

Язык называют рекурсивно перечислимым, если можно построить МТ, воспринимающую все цепочки из и никакие другие. Язык называют рекурсивным, если и и его дополнение, т. е. множество рекурсивно перечислимы. Стоит немного подробнее обсудить, что же означают эти свойства. Если — рекурсивный язык, то можно создать МТ, или, что то же самое, программу, распознающую, входит данная цепочка в множество или нет. Программа может требовать очень мощных функций управления динамической памятью. Рассматриваемая МТ в действительности состоит из двух машин, одна из которых распознает цепочки в а другая — в Основная машина просто фиксирует, которая из этой пары машин воспринимает входную цепочку. С другой стороны, допустим, что язык рекурсивно перечислимый, но не рекурсивный. Тогда основную машину нельзя построить, поскольку невозможно реализовать ее часть для распознавания цепочек в Наличия же части, распознающей цепочки из не достаточно, так как, если она будет работать без остановки продолжительное время, мы не узнаем, попала она в цикл при работе с динамической памятью или ей просто нужно больше времени для опознания цепочки.

Эти принципы иллюстрируются в одном очень важном приложении, связанном с искусственным интеллектом. Пусть — множество правильно построенных выражений , которые можно вывести из множества аксиом, применяя правила вывода с логическими связками и, или и не и кванторами некоторые и все. Это множество рекурсивно перечислимо, но не рекурсивно. Ответ на вопрос „Следует ли из фактов S заключение s?“ эквивалентен вопросу „Входит ли s в L?“. Пусть верен ответ „нет“. Тогда — цепочка в , возможно, за конечное время установить этот факт не

удастся. Бисс, Чен и Стал (1971) предложили интересный конкретный пример. Они написали программу доказательства теорем для опознания случаев нарушения правил уличного движения. Аксиомами были дорожные правила, взятые из Illinois Driver’s Manual. Задачей программы было выяснить, запрещают ли эти правила какие-то действия водителей. Абстрактно эта проблема состоит в выяснении того, включено ли действие в язык порождаемый применением законов логического вывода к основному описанию действий, нарушающих правила. В связи с тем, что множество рекурсивно перечислимо, программа не может работать во всех случаях, хотя любое ее положительное заключение было бы верным.