Машина Тьюринга

Большинство теоретических результатов относительно вычислительной способности различных автоматов (к которым относятся RAM и RASPM) получено для Машины Тьюринга. Следовательно, для применения к RASPM уже известных результатов, необходимо установить отношение между этими формальными системами.

Определение 2.5. Машина Тьюринга с одной лентой может быть определена как совокупность семи элементов:

где Q - множество состояний Машины Тьюринга, S - множество символов, которые могут быть записаны на ленте, I - множество символов входящей последовательности, I S, b S | I - пустой символ, q₀ - начальное состояние Машины Тьюринга, q_f - конечное состояние Машины Тьюринга, d: Q × S Q × S × {l, r, s} - множество функций перехода, которые состоянию и символу ленты ставят в соответствие новое состояние, новый символ и перемещение по ленте: на шаг влево, на шаг вправо, остаться на месте

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

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

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

Кроме того доказан фундаментальный результат.

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