Машина Тьюринга
Большинство теоретических результатов относительно вычислительной способности различных автоматов (к которым относятся RAM и RASPM) получено для Машины Тьюринга. Следовательно, для применения к RASPM уже известных результатов, необходимо установить отношение между этими формальными системами.
Определение 2.5. Машина Тьюринга с одной лентой может быть определена как совокупность семи элементов:
где Q - множество состояний Машины Тьюринга, S - множество символов, которые могут быть записаны на ленте, I - множество символов входящей последовательности, I
Машина начинает свою работу в состоянии q0 и в дальнейшем меняет состояния согласно функциям перехода в зависимости от текущего состояния и значения ячейки ленты. Попутно ячейки ленты перезаписываются новыми значениями согласно тем же функциям перехода.
Машина Тьюринга может содержать и большее количество лент, но вычислительная способность такой машины будет находиться в полиномиальной зависимости от вычислительной способности Машины Тьюринга с одной лентой. Помимо этого имеют место следующая теорема:
Теорема 2.3. Вычислительные способности Машины Тьюринга и RASPM эквивалентны, а их затраты на вычисление полиноминально сравнимы, если стоимость выполнения инструкции является величиной постоянной или находится в логарифмической зависимости от длины операнда
Кроме того доказан фундаментальный результат.
Теорема 2.4. Не существует такой Машины Тьюринга, которая сможет определить остановится ли произвольная Машина Тьюринга на произвольном входе (проблема остановки)
