Функции, выполняющие достаточно произвольные алгоритмы

[Sonic86]

Пусть $A$ - конечный алфавит, $A^*$ - множество строк. Будем рассматривать функции из $(A^*)^n$ в $(A^*)^m$, где $n,m\in\mathbb{N}\cup\{0\}$ - произвольны.
Будем говорить, что функция $f(s_1,...,s_n)$ сильнее $g(s_1,...,s_k)$, если $(\forall (s_1,...,s_k))(\exists (t_1,...,t_k))g(s_1,...,s_k)=f(t_1,...,t_k)$. Отношение "сильнее" - отношение частичного порядка на множестве функций. Грубо говоря, $f$ может вычислить больше $g$.
Меня интересует, есть ли литература, в которой рассмотрено такое понятие, если да, как называется хотя бы это понятие, чтобы можно было погуглить. Я собираюсь написать программу, использующую функцию достаточно сильную в этом смысле (что-то типа execute immediate в SQL).
Или просто хочу узнать, какими свойствами обладают достаточно сильные функции? Имеет ли множество сильных функций верхнюю грань (т.е. есть ли универсальная функция). Я, например, знаю, что для универсальная функция для одноместных примитивно рекурсивных функций не примитивно рекурсивная, а универсальная функция для рекурсивных функций тоже рекурсивна. По идее, то же самое должно быть и в случае, если аргументы функций - строки.
Как устроен код таких функций? Верно ли, что в коде любой достаточно сильной функции должно быть явное ли неявное кодирование класса функций Можно ли множество функций разбить на какие-то достаточно крупные классы по отношению "сильный"

Примеры:

int f1(int a, int b){
    return a+b;
}

int f2(int a, int b, int c){
    if(c==0){
        return a+b;
    }
    else{
        return c;
    }
}

здесь $f_2$ сильнее, чем $f_1$.
Если есть функции $f_1,...,f_n$, то используя конструкцию if можно написать функцию $f$, которая сильнее, чем $f_1,...,f_n$. Однако, если $n$ достаточно велико, или если число функций $f_j$ счетно, то проще написать универсальную функцию для всех $f_j$, кодируя простые функции.

[worm2]

Sonic86 писал(а):

Будем говорить, что функция $f(s_1,...,s_n)$ сильнее $g(s_1,...,s_k)$, если $(\forall (s_1,...,s_k))(\exists (t_1,...,t_k))g(s_1,...,s_k)=f(t_1,...,t_k)$.

Что-то непонятно. Каждой функции передаётся кортеж из $n$ строк, и возвращает она тоже кортеж из $m$ строк, так? При этом сравниваются только значения (результаты) функций? Но как можно сравнивать значения функций, одна из которых возвращает кортеж из 2-х строк, а вторая — кортеж из 3-х строк?
Кроме того, в определении универсальной функции наборы аргументов совпадают, за исключением одного аргумента, а у Вас наборы аргументов полностью различны. С этой точки зрения "универсальной функцией" можно назвать любую сюръекцию на область значений (подразумевая, что эта область значений одинакова для всех рассматриваемых функций). В общем, я запутался.

[Sonic86]

worm2 в сообщении #640085 писал(а):

Но как можно сравнивать значения функций, одна из которых возвращает кортеж из 2-х строк, а вторая — кортеж из 3-х строк?

Да, проморгал, можно попробовать ограничиться функциями $(A^*)^n$ в $(A^*)^m$ для $m=\operatorname{const}$, но это неестественно. Надо как-то хорошо определение построить (первые 2 были неудачны), только боюсь, что придется применять какие-то функции кодирования аргументов. Только это сложновато и пока идей нет.
Т.е. я вот могу написать как раз что-то вида execute immediate, у нее будет один входной параметр, но у нее будет сколько выходных параметров? По идее, достаточно одного: записать кортеж значений в виде строки, используя специальный символ-разделитель. Но чтобы связать обычный кортеж и кортеж в виде строки, тоже нужна функция перекодировки аргументов.

Надо еще подумать... Смысл-то почти понятен...

[worm2]

Если я правильно понял, то для всех функций из $(A^*)^n$ (во что-то там) существует универсальная функция из $(A^*)^{n+1}$ (в то же самое): первым аргументом можно описать (на каком-нибудь Тьюринг-полном языке над алфавитом $A$) алгоритм, осуществляемый функцией. То, что в универсальной функции нельзя обойтись $n$ аргументами, очевидно: диагональным процессом такая возможность убивается.