О возможности максимального распараллеливания задач на ассоциативных процессорах

Предложена вычислительная модель ассоциативного типа. Для нее написана программа, которая не содержит циклов и обладает следующими свойствами. Исходными данными для программы являются нормальный алгоритм $A$ (его запись) и слово $a$, а результатами – булевское значение $r$ и слово $R$. Если $A$ применим к слову $a$, то важно указать такую конечную память, что программа, проработав на этой памяти, выдаст в качестве $r$ значение истина, а в качестве $R$ – $A(a)$. Если же $A$ к $a$ неприменим, то, на какой бы памяти (конечной) программа не работала, она всегда будет выдавать в качестве $r$ значение ложь. Если программа работает на бесконечной памяти, то после ее работы $r$ принимает значение истина т. и т.т., когда $A$ к $a$ применим, причем в случае применимости $R$, принимает значение $A(a)$. Настоящая работа содержит более подробное изложение результата, опубликованного в “Зап. научн. семинаров Ленингр. отд. Мат. ин-та АН СССР”, 1977, т. 70. Библ. – 12 назв.