"Уточнения" понятия А.

"Уточнения" понятия А. Возможны дальнейшие "уточнения" понятия А.„ приводящие,
строго говоря, к известному сужению этого понятия. Каждое такое уточнение
состоит в том, что для каждого из указанных <7 параметров А.< точно
описывается нек-рый класс, в пределах к-рого этот параметр может меняться.
Выбор этих классов и отличает одно уточнение от другого. Во многих уточнениях
все классы, кроме двух<-класса совокупностей промежуточных результатов
и класса правил непосредств. переработки, <- выбираются единичными,
т. е. все параметры, кроме указанных двух, жёстко фиксируются. Поскольку
<7
параметров однозначно определяют нек-рый А., то выбор <7 классов
изменения этих параметров определяет нек-рый класс А. Однако такой выбор
может претендовать на название "уточнения", лишь если имеется убеждение,
что для произвольного А., имеющего допускаемые данным выбором совокупности
возможных исходных данных и возможных результатов, может быть указан равносильный
ему А. из определённого данным выбором класса А. Это убеждение формулируется
для каждого уточнения в виде основной гипотезы, к-рая <- при современном
уровне наших представлений <- не может быть предметом матем. доказательства.

Первые уточнения
описанного типа предложили в 1936 амер. математик Э. Л. Пост и англ, математик
А. М. Тьюринг (см. Тьюринга машина). Известны также уточнения, сформулированные
сов. математиками А. А. Марковым (см. Нормальный алгоритм) и А. Н. Колмогоровым
(последний предложил трактовать конструктивные объекты как топологич. комплексы
определённого вида, что дало возможность уточнить свойство "локальности"
преобразования). Для каждого из предложенных уточнений соответствующая
осн. гипотеза хорошо согласуется с практикой. В пользу этой гипотезы говорит
и то, что, как можно доказать, все предложенные уточнения в нек-ром естественном
смысле эквивалентны друг другу.

В качестве
примера приведём (в модернизированном виде) уточнение, предложенное Тьюрингом.
Чтобы задать тьюрингов А., надо указать; а) попарно непересекающиеся алфавиты
Б, Д, Ч с выделенной в Д буквой и выделенными
в Ч буквами ) набор пар вида,
где а Т есть один из знаков - , 0, +, причём предполагается,
что в этом наборе (наз. программой) нет 2 пар с одинаковыми первыми членами.
Параметры А. задаются так; возможными исходными данными и возможными результатами
служат слова в Б, а промежуточными результатами - слова в,
содержащие не более одной буквы из Ч. Правило начала: исходное слово Р
переводится в слово. Правило окончания;
заключительным является промежуточный результат, содержащий w. Правило
извлечения результата: результатом объявляется цепочка всех тех букв заключительного
промежуточного результата, которая идёт вслед за со и предшествует первой
букве, не принадлежащей Б. Правило непосредств. переработки, переводящее
А в А', состоит в следующем. Приписываем к А слева и справа букву;
затем в образовавшемся слове часть вида
где заменяем на словопо
следующему правилу: в программе ищется пара с первым членом
пусть второй член этой пары есть nTq; если Т есть

А Б В Г Д Е Ё Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ъ Ы Ь Э Ю Я