Вирусы и средства борьбы с ними


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


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

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

T = \langle Q, S, I, d, b, q_0, q_f \rangle,

где Q - множество состояний Машины Тьюринга, S - множество символов, которые могут быть записаны на ленте, I - множество символов входящей последовательности, I

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

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

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

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

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

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




- Начало -  - Назад -  - Вперед -