Математическая логика и теория алгоритмов

Теорема 6.6 (обратная теореме 6.5). Пусть В - нормальный алгоритм в алфавите^, не содержащем S Q И S. Тогда существует такая машина Тьюринга Т, что алгоритм Тьюринга Л 5} в алфавите обладает следующим свойством: для всякого слова Р в А алгоритм Л применим к Р тогда и только тогда, когда 1С Р применим алгоритм В и при этом А t,a^{So 8} имеет вид S Q B { P ) S Q , гдег И /и-целыенеотрицательные числа, а S Q =S Q S Q ...S Q . к раз Согласно сформулированной теореме значения алгоритмов В и А 7-_^u{So5} формально различны, так как для машины Тьюринга есть символ пустого квадрата, а в нормальном алгоритме В So - буква, равноправная с любой другой буквой. Но с точностью до символов So, которые могут стоять справа и слева от результирующего слова, алгоритмы В и Л вполне эквиваленты. Теорему принимаем без доказательства. С л е д с т в и е 6.2 . Всякая частично вычислимая (вычислимая) по Маркову функция частично вычислима (вычислима) по Тьюрингу. Доказательство следствия сразу получается из теоремы 6.6 и определения вычислимой по Тьюрингу функции. Из теорем 6.5 и 6.6 видим, что различные подходы к понятию алгоритмов Тьюринга и Маркова (нормальные алгоритмы) по сущест­ ву эквивалентны, т.е. то, что можно осуществить с помощью нормаль­ ного алгоритма, можно осуществить с помощью машины Тьюринга, и наоборот. Есть еще многоленточные машины Тьюринга и другие модифи­ кации (варианты) подхода к понятию алгоритма, такие как машины Поста, машины Минского и др. Однако детальный анализ показывает, что все эти понятия равносильны в том смысле, что то, что можно осуществить (вычислить) с помощью одной из этих машин, можно сделать (вычислить) с помощью машины Тьюринга, а следовательно, и с помощью нормального алгоритма, и наоборот. 243